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 }