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