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
56 */
57 public interface Region<S extends Space> {
58
59 /** Enumerate for the location of a point with respect to the region. */
60 enum Location {
61 /** Code for points inside the partition. */
62 INSIDE,
63
64 /** Code for points outside of the partition. */
65 OUTSIDE,
66
67 /** Code for points on the partition boundary. */
68 BOUNDARY;
69 }
70
71 /** Build a region using the instance as a prototype.
72 * <p>This method allow to create new instances without knowing
73 * exactly the type of the region. It is an application of the
74 * prototype design pattern.</p>
75 * <p>The leaf nodes of the BSP tree <em>must</em> have a
76 * {@code Boolean} attribute representing the inside status of
77 * the corresponding cell (true for inside cells, false for outside
78 * cells). In order to avoid building too many small objects, it is
79 * recommended to use the predefined constants
80 * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
81 * tree also <em>must</em> have either null internal nodes or
82 * internal nodes representing the boundary as specified in the
83 * {@link #getTree getTree} method).</p>
84 * @param newTree inside/outside BSP tree representing the new region
85 * @return the built region
86 */
87 Region<S> buildNew(BSPTree<S> newTree);
88
89 /** Copy the instance.
90 * <p>The instance created is completely independant of the original
91 * one. A deep copy is used, none of the underlying objects are
92 * shared (except for the underlying tree {@code Boolean}
93 * attributes and immutable objects).</p>
94 * @return a new region, copy of the instance
95 */
96 Region<S> copySelf();
97
98 /** Check if the instance is empty.
99 * @return true if the instance is empty
100 */
101 boolean isEmpty();
102
103 /** Check if the sub-tree starting at a given node is empty.
104 * @param node root node of the sub-tree (<em>must</em> have {@link
105 * Region Region} tree semantics, i.e. the leaf nodes must have
106 * {@code Boolean} attributes representing an inside/outside
107 * property)
108 * @return true if the sub-tree starting at the given node is empty
109 */
110 boolean isEmpty(BSPTree<S> node);
111
112 /** Check if the instance covers the full space.
113 * @return true if the instance covers the full space
114 */
115 boolean isFull();
116
117 /** Check if the sub-tree starting at a given node covers the full space.
118 * @param node root node of the sub-tree (<em>must</em> have {@link
119 * Region Region} tree semantics, i.e. the leaf nodes must have
120 * {@code Boolean} attributes representing an inside/outside
121 * property)
122 * @return true if the sub-tree starting at the given node covers the full space
123 */
124 boolean isFull(BSPTree<S> node);
125
126 /** Check if the instance entirely contains another region.
127 * @param region region to check against the instance
128 * @return true if the instance contains the specified tree
129 */
130 boolean contains(Region<S> region);
131
132 /** Check a point with respect to the region.
133 * @param point point to check
134 * @return a code representing the point status: either {@link
135 * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY}
136 */
137 Location checkPoint(Point<S> point);
138
139 /** Project a point on the boundary of the region.
140 * @param point point to check
141 * @return projection of the point on the boundary
142 */
143 BoundaryProjection<S> projectToBoundary(Point<S> point);
144
145 /** Get the underlying BSP tree.
146
147 * <p>Regions are represented by an underlying inside/outside BSP
148 * tree whose leaf attributes are {@code Boolean} instances
149 * representing inside leaf cells if the attribute value is
150 * {@code true} and outside leaf cells if the attribute is
151 * {@code false}. These leaf attributes are always present and
152 * guaranteed to be non null.</p>
153
154 * <p>In addition to the leaf attributes, the internal nodes which
155 * correspond to cells split by cut sub-hyperplanes may contain
156 * {@link BoundaryAttribute BoundaryAttribute} objects representing
157 * the parts of the corresponding cut sub-hyperplane that belong to
158 * the boundary. When the boundary attributes have been computed,
159 * all internal nodes are guaranteed to have non-null
160 * attributes, however some {@link BoundaryAttribute
161 * BoundaryAttribute} instances may have their {@link
162 * BoundaryAttribute#getPlusInside() getPlusInside} and {@link
163 * BoundaryAttribute#getPlusOutside() getPlusOutside} methods both
164 * returning null if the corresponding cut sub-hyperplane does not
165 * have any parts belonging to the boundary.</p>
166
167 * <p>Since computing the boundary is not always required and can be
168 * time-consuming for large trees, these internal nodes attributes
169 * are computed using lazy evaluation only when required by setting
170 * the {@code includeBoundaryAttributes} argument to
171 * {@code true}. Once computed, these attributes remain in the
172 * tree, which implies that in this case, further calls to the
173 * method for the same region will always include these attributes
174 * regardless of the value of the
175 * {@code includeBoundaryAttributes} argument.</p>
176
177 * @param includeBoundaryAttributes if true, the boundary attributes
178 * at internal nodes are guaranteed to be included (they may be
179 * included even if the argument is false, if they have already been
180 * computed due to a previous call)
181 * @return underlying BSP tree
182 * @see BoundaryAttribute
183 */
184 BSPTree<S> getTree(boolean includeBoundaryAttributes);
185
186 /** Get the size of the boundary.
187 * @return the size of the boundary (this is 0 in 1D, a length in
188 * 2D, an area in 3D ...)
189 */
190 double getBoundarySize();
191
192 /** Get the size of the instance.
193 * @return the size of the instance (this is a length in 1D, an area
194 * in 2D, a volume in 3D ...)
195 */
196 double getSize();
197
198 /** Get the barycenter of the instance.
199 * @return an object representing the barycenter
200 */
201 Point<S> getBarycenter();
202
203 /** Get the parts of a sub-hyperplane that are contained in the region.
204 * <p>The parts of the sub-hyperplane that belong to the boundary are
205 * <em>not</em> included in the resulting parts.</p>
206 * @param sub sub-hyperplane traversing the region
207 * @return filtered sub-hyperplane
208 */
209 SubHyperplane<S> intersection(SubHyperplane<S> sub);
210
211 }