View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      https://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  package org.hipparchus.geometry.partitioning;
23  
24  import org.hipparchus.geometry.Point;
25  import org.hipparchus.geometry.Space;
26  
27  /** This interface represents a region of a space as a partition.
28  
29   * <p>Region are subsets of a space, they can be infinite (whole
30   * space, half space, infinite stripe ...) or finite (polygons in 2D,
31   * polyhedrons in 3D ...). Their main characteristic is to separate
32   * points that are considered to be <em>inside</em> the region from
33   * points considered to be <em>outside</em> of it. In between, there
34   * may be points on the <em>boundary</em> of the region.</p>
35  
36   * <p>This implementation is limited to regions for which the boundary
37   * is composed of several {@link SubHyperplane sub-hyperplanes},
38   * including regions with no boundary at all: the whole space and the
39   * empty region. They are not necessarily finite and not necessarily
40   * path-connected. They can contain holes.</p>
41  
42   * <p>Regions can be combined using the traditional sets operations :
43   * union, intersection, difference and symetric difference (exclusive
44   * or) for the binary operations, complement for the unary
45   * operation.</p>
46  
47   * <p>
48   * Note that this interface is <em>not</em> intended to be implemented
49   * by Hipparchus users, it is only intended to be implemented
50   * within the library itself. New methods may be added even for minor
51   * versions, which breaks compatibility for external implementations.
52   * </p>
53  
54   * @param <S> Type of the space.
55   * @param <P> Type of the points in the space.
56   * @param <H> Type of the hyperplane.
57   * @param <I> Type of the sub-hyperplane.
58  
59   */
60  public interface Region<S extends Space, P extends Point<S, P>, H extends Hyperplane<S, P, H, I>, I extends SubHyperplane<S, P, H, I>> {
61  
62      /** Enumerate for the location of a point with respect to the region. */
63      enum Location {
64          /** Code for points inside the partition. */
65          INSIDE,
66  
67          /** Code for points outside of the partition. */
68          OUTSIDE,
69  
70          /** Code for points on the partition boundary. */
71          BOUNDARY
72      }
73  
74      /** Build a region using the instance as a prototype.
75       * <p>This method allow to create new instances without knowing
76       * exactly the type of the region. It is an application of the
77       * prototype design pattern.</p>
78       * <p>The leaf nodes of the BSP tree <em>must</em> have a
79       * {@code Boolean} attribute representing the inside status of
80       * the corresponding cell (true for inside cells, false for outside
81       * cells). In order to avoid building too many small objects, it is
82       * recommended to use the predefined constants
83       * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
84       * tree also <em>must</em> have either null internal nodes or
85       * internal nodes representing the boundary as specified in the
86       * {@link #getTree getTree} method).</p>
87       * @param newTree inside/outside BSP tree representing the new region
88       * @return the built region
89       */
90      Region<S, P, H, I> buildNew(BSPTree<S, P, H, I> newTree);
91  
92      /** Copy the instance.
93       * <p>The instance created is completely independant of the original
94       * one. A deep copy is used, none of the underlying objects are
95       * shared (except for the underlying tree {@code Boolean}
96       * attributes and immutable objects).</p>
97       * @return a new region, copy of the instance
98       */
99      Region<S, P, H, I> copySelf();
100 
101     /** Check if the instance is empty.
102      * @return true if the instance is empty
103      */
104     boolean isEmpty();
105 
106     /** Check if the sub-tree starting at a given node is empty.
107      * @param node root node of the sub-tree (<em>must</em> have {@link
108      * Region Region} tree semantics, i.e. the leaf nodes must have
109      * {@code Boolean} attributes representing an inside/outside
110      * property)
111      * @return true if the sub-tree starting at the given node is empty
112      */
113     boolean isEmpty(BSPTree<S, P, H, I> node);
114 
115     /** Check if the instance covers the full space.
116      * @return true if the instance covers the full space
117      */
118     boolean isFull();
119 
120     /** Check if the sub-tree starting at a given node covers the full space.
121      * @param node root node of the sub-tree (<em>must</em> have {@link
122      * Region Region} tree semantics, i.e. the leaf nodes must have
123      * {@code Boolean} attributes representing an inside/outside
124      * property)
125      * @return true if the sub-tree starting at the given node covers the full space
126      */
127     boolean isFull(BSPTree<S, P, H, I> node);
128 
129     /** Check if the instance entirely contains another region.
130      * @param region region to check against the instance
131      * @return true if the instance contains the specified tree
132      */
133     boolean contains(Region<S, P, H, I> region);
134 
135     /** Check a point with respect to the region.
136      * @param point point to check
137      * @return a code representing the point status: either {@link
138      * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY}
139      */
140     Location checkPoint(P point);
141 
142     /** Project a point on the boundary of the region.
143      * @param point point to check
144      * @return projection of the point on the boundary
145      */
146     BoundaryProjection<S, P> projectToBoundary(P point);
147 
148     /** Get the underlying BSP tree.
149 
150      * <p>Regions are represented by an underlying inside/outside BSP
151      * tree whose leaf attributes are {@code Boolean} instances
152      * representing inside leaf cells if the attribute value is
153      * {@code true} and outside leaf cells if the attribute is
154      * {@code false}. These leaf attributes are always present and
155      * guaranteed to be non null.</p>
156 
157      * <p>In addition to the leaf attributes, the internal nodes which
158      * correspond to cells split by cut sub-hyperplanes may contain
159      * {@link BoundaryAttribute BoundaryAttribute} objects representing
160      * the parts of the corresponding cut sub-hyperplane that belong to
161      * the boundary. When the boundary attributes have been computed,
162      * all internal nodes are guaranteed to have non-null
163      * attributes, however some {@link BoundaryAttribute
164      * BoundaryAttribute} instances may have their {@link
165      * BoundaryAttribute#getPlusInside() getPlusInside} and {@link
166      * BoundaryAttribute#getPlusOutside() getPlusOutside} methods both
167      * returning null if the corresponding cut sub-hyperplane does not
168      * have any parts belonging to the boundary.</p>
169 
170      * <p>Since computing the boundary is not always required and can be
171      * time-consuming for large trees, these internal nodes attributes
172      * are computed using lazy evaluation only when required by setting
173      * the {@code includeBoundaryAttributes} argument to
174      * {@code true}. Once computed, these attributes remain in the
175      * tree, which implies that in this case, further calls to the
176      * method for the same region will always include these attributes
177      * regardless of the value of the
178      * {@code includeBoundaryAttributes} argument.</p>
179 
180      * @param includeBoundaryAttributes if true, the boundary attributes
181      * at internal nodes are guaranteed to be included (they may be
182      * included even if the argument is false, if they have already been
183      * computed due to a previous call)
184      * @return underlying BSP tree
185      * @see BoundaryAttribute
186      */
187     BSPTree<S, P, H, I> getTree(boolean includeBoundaryAttributes);
188 
189     /** Get the size of the boundary.
190      * @return the size of the boundary (this is 0 in 1D, a length in
191      * 2D, an area in 3D ...)
192      */
193     double getBoundarySize();
194 
195     /** Get the size of the instance.
196      * @return the size of the instance (this is a length in 1D, an area
197      * in 2D, a volume in 3D ...)
198      */
199     double getSize();
200 
201     /** Get the barycenter of the instance.
202      * @return an object representing the barycenter
203      */
204     P getBarycenter();
205 
206     /** Get an interior point.
207      * @return an arbitrary interior point, or null if region is empty
208      * @since 4.0
209      */
210     P getInteriorPoint();
211 
212     /** Get the parts of a sub-hyperplane that are contained in the region.
213      * <p>The parts of the sub-hyperplane that belong to the boundary are
214      * <em>not</em> included in the resulting parts.</p>
215      * @param sub sub-hyperplane traversing the region
216      * @return filtered sub-hyperplane
217      */
218     I intersection(I sub);
219 
220 }