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 java.util.HashMap;
25 import java.util.Map;
26
27 import org.hipparchus.exception.MathIllegalArgumentException;
28 import org.hipparchus.geometry.LocalizedGeometryFormats;
29 import org.hipparchus.geometry.Point;
30 import org.hipparchus.geometry.Space;
31 import org.hipparchus.geometry.partitioning.BSPTree.VanishingCutHandler;
32 import org.hipparchus.geometry.partitioning.Region.Location;
33 import org.hipparchus.geometry.partitioning.SubHyperplane.SplitSubHyperplane;
34
35 /** This class is a factory for {@link Region}.
36
37 * @param <S> Type of the space.
38
39 */
40 public class RegionFactory<S extends Space> {
41
42 /** Visitor removing internal nodes attributes. */
43 private final NodesCleaner nodeCleaner;
44
45 /** Simple constructor.
46 */
47 public RegionFactory() {
48 nodeCleaner = new NodesCleaner();
49 }
50
51 /** Build a convex region from a collection of bounding hyperplanes.
52 * @param hyperplanes collection of bounding hyperplanes
53 * @return a new convex region, or null if the collection is empty
54 */
55 @SafeVarargs
56 public final Region<S> buildConvex(final Hyperplane<S> ... hyperplanes) {
57 if ((hyperplanes == null) || (hyperplanes.length == 0)) {
58 return null;
59 }
60
61 // use the first hyperplane to build the right class
62 final Region<S> region = hyperplanes[0].wholeSpace();
63
64 // chop off parts of the space
65 BSPTree<S> node = region.getTree(false);
66 node.setAttribute(Boolean.TRUE);
67 for (final Hyperplane<S> hyperplane : hyperplanes) {
68 if (node.insertCut(hyperplane)) {
69 node.setAttribute(null);
70 node.getPlus().setAttribute(Boolean.FALSE);
71 node = node.getMinus();
72 node.setAttribute(Boolean.TRUE);
73 } else {
74 // the hyperplane could not be inserted in the current leaf node
75 // either it is completely outside (which means the input hyperplanes
76 // are wrong), or it is parallel to a previous hyperplane
77 SubHyperplane<S> s = hyperplane.wholeHyperplane();
78 for (BSPTree<S> tree = node; tree.getParent() != null && s != null; tree = tree.getParent()) {
79 final Hyperplane<S> other = tree.getParent().getCut().getHyperplane();
80 final SplitSubHyperplane<S> split = s.split(other);
81 switch (split.getSide()) {
82 case HYPER :
83 // the hyperplane is parallel to a previous hyperplane
84 if (!hyperplane.sameOrientationAs(other)) {
85 // this hyperplane is opposite to the other one,
86 // the region is thinner than the tolerance, we consider it empty
87 return getComplement(hyperplanes[0].wholeSpace());
88 }
89 // the hyperplane is an extension of an already known hyperplane, we just ignore it
90 break;
91 case PLUS :
92 // the hyperplane is outside of the current convex zone,
93 // the input hyperplanes are inconsistent
94 throw new MathIllegalArgumentException(LocalizedGeometryFormats.NOT_CONVEX_HYPERPLANES);
95 default :
96 s = split.getMinus();
97 }
98 }
99 }
100 }
101
102 return region;
103
104 }
105
106 /** Compute the union of two regions.
107 * @param region1 first region (will be unusable after the operation as
108 * parts of it will be reused in the new region)
109 * @param region2 second region (will be unusable after the operation as
110 * parts of it will be reused in the new region)
111 * @return a new region, result of {@code region1 union region2}
112 */
113 public Region<S> union(final Region<S> region1, final Region<S> region2) {
114 final BSPTree<S> tree =
115 region1.getTree(false).merge(region2.getTree(false), new UnionMerger());
116 tree.visit(nodeCleaner);
117 return region1.buildNew(tree);
118 }
119
120 /** Compute the intersection of two regions.
121 * @param region1 first region (will be unusable after the operation as
122 * parts of it will be reused in the new region)
123 * @param region2 second region (will be unusable after the operation as
124 * parts of it will be reused in the new region)
125 * @return a new region, result of {@code region1 intersection region2}
126 */
127 public Region<S> intersection(final Region<S> region1, final Region<S> region2) {
128 final BSPTree<S> tree =
129 region1.getTree(false).merge(region2.getTree(false), new IntersectionMerger());
130 tree.visit(nodeCleaner);
131 return region1.buildNew(tree);
132 }
133
134 /** Compute the symmetric difference (exclusive or) of two regions.
135 * @param region1 first region (will be unusable after the operation as
136 * parts of it will be reused in the new region)
137 * @param region2 second region (will be unusable after the operation as
138 * parts of it will be reused in the new region)
139 * @return a new region, result of {@code region1 xor region2}
140 */
141 public Region<S> xor(final Region<S> region1, final Region<S> region2) {
142 final BSPTree<S> tree =
143 region1.getTree(false).merge(region2.getTree(false), new XorMerger());
144 tree.visit(nodeCleaner);
145 return region1.buildNew(tree);
146 }
147
148 /** Compute the difference of two regions.
149 * @param region1 first region (will be unusable after the operation as
150 * parts of it will be reused in the new region)
151 * @param region2 second region (will be unusable after the operation as
152 * parts of it will be reused in the new region)
153 * @return a new region, result of {@code region1 minus region2}
154 */
155 public Region<S> difference(final Region<S> region1, final Region<S> region2) {
156 final BSPTree<S> tree =
157 region1.getTree(false).merge(region2.getTree(false), new DifferenceMerger(region1, region2));
158 tree.visit(nodeCleaner);
159 return region1.buildNew(tree);
160 }
161
162 /** Get the complement of the region (exchanged interior/exterior).
163 * @param region region to complement, it will not modified, a new
164 * region independent region will be built
165 * @return a new region, complement of the specified one
166 */
167 /** Get the complement of the region (exchanged interior/exterior).
168 * @param region region to complement, it will not modified, a new
169 * region independent region will be built
170 * @return a new region, complement of the specified one
171 */
172 public Region<S> getComplement(final Region<S> region) {
173 return region.buildNew(recurseComplement(region.getTree(false)));
174 }
175
176 /** Recursively build the complement of a BSP tree.
177 * @param node current node of the original tree
178 * @return new tree, complement of the node
179 */
180 private BSPTree<S> recurseComplement(final BSPTree<S> node) {
181
182 // transform the tree, except for boundary attribute splitters
183 final Map<BSPTree<S>, BSPTree<S>> map = new HashMap<>();
184 final BSPTree<S> transformedTree = recurseComplement(node, map);
185
186 // set up the boundary attributes splitters
187 for (final Map.Entry<BSPTree<S>, BSPTree<S>> entry : map.entrySet()) {
188 if (entry.getKey().getCut() != null) {
189 @SuppressWarnings("unchecked")
190 BoundaryAttribute<S> original = (BoundaryAttribute<S>) entry.getKey().getAttribute();
191 if (original != null) {
192 @SuppressWarnings("unchecked")
193 BoundaryAttribute<S> transformed = (BoundaryAttribute<S>) entry.getValue().getAttribute();
194 for (final BSPTree<S> splitter : original.getSplitters()) {
195 transformed.getSplitters().add(map.get(splitter));
196 }
197 }
198 }
199 }
200
201 return transformedTree;
202
203 }
204
205 /** Recursively build the complement of a BSP tree.
206 * @param node current node of the original tree
207 * @param map transformed nodes map
208 * @return new tree, complement of the node
209 */
210 private BSPTree<S> recurseComplement(final BSPTree<S> node,
211 final Map<BSPTree<S>, BSPTree<S>> map) {
212
213 final BSPTree<S> transformedNode;
214 if (node.getCut() == null) {
215 transformedNode = new BSPTree<>(((Boolean) node.getAttribute()) ? Boolean.FALSE : Boolean.TRUE);
216 } else {
217
218 @SuppressWarnings("unchecked")
219 BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute();
220 if (attribute != null) {
221 final SubHyperplane<S> plusOutside =
222 (attribute.getPlusInside() == null) ? null : attribute.getPlusInside().copySelf();
223 final SubHyperplane<S> plusInside =
224 (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().copySelf();
225 // we start with an empty list of splitters, it will be filled in out of recursion
226 attribute = new BoundaryAttribute<>(plusOutside, plusInside, new NodesSet<S>());
227 }
228
229 transformedNode = new BSPTree<>(node.getCut().copySelf(),
230 recurseComplement(node.getPlus(), map),
231 recurseComplement(node.getMinus(), map),
232 attribute);
233 }
234
235 map.put(node, transformedNode);
236 return transformedNode;
237
238 }
239
240 /** BSP tree leaf merger computing union of two regions. */
241 private class UnionMerger implements BSPTree.LeafMerger<S> {
242 /** {@inheritDoc} */
243 @Override
244 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree,
245 final BSPTree<S> parentTree,
246 final boolean isPlusChild, final boolean leafFromInstance) {
247 if ((Boolean) leaf.getAttribute()) {
248 // the leaf node represents an inside cell
249 leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true));
250 return leaf;
251 }
252 // the leaf node represents an outside cell
253 tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false));
254 return tree;
255 }
256 }
257
258 /** BSP tree leaf merger computing intersection of two regions. */
259 private class IntersectionMerger implements BSPTree.LeafMerger<S> {
260 /** {@inheritDoc} */
261 @Override
262 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree,
263 final BSPTree<S> parentTree,
264 final boolean isPlusChild, final boolean leafFromInstance) {
265 if ((Boolean) leaf.getAttribute()) {
266 // the leaf node represents an inside cell
267 tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true));
268 return tree;
269 }
270 // the leaf node represents an outside cell
271 leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false));
272 return leaf;
273 }
274 }
275
276 /** BSP tree leaf merger computing symmetric difference (exclusive or) of two regions. */
277 private class XorMerger implements BSPTree.LeafMerger<S> {
278 /** {@inheritDoc} */
279 @Override
280 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree,
281 final BSPTree<S> parentTree, final boolean isPlusChild,
282 final boolean leafFromInstance) {
283 BSPTree<S> t = tree;
284 if ((Boolean) leaf.getAttribute()) {
285 // the leaf node represents an inside cell
286 t = recurseComplement(t);
287 }
288 t.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true));
289 return t;
290 }
291 }
292
293 /** BSP tree leaf merger computing difference of two regions. */
294 private class DifferenceMerger implements BSPTree.LeafMerger<S>, VanishingCutHandler<S> {
295
296 /** Region to subtract from. */
297 private final Region<S> region1;
298
299 /** Region to subtract. */
300 private final Region<S> region2;
301
302 /** Simple constructor.
303 * @param region1 region to subtract from
304 * @param region2 region to subtract
305 */
306 DifferenceMerger(final Region<S> region1, final Region<S> region2) {
307 this.region1 = region1.copySelf();
308 this.region2 = region2.copySelf();
309 }
310
311 /** {@inheritDoc} */
312 @Override
313 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree,
314 final BSPTree<S> parentTree, final boolean isPlusChild,
315 final boolean leafFromInstance) {
316 if ((Boolean) leaf.getAttribute()) {
317 // the leaf node represents an inside cell
318 final BSPTree<S> argTree =
319 recurseComplement(leafFromInstance ? tree : leaf);
320 argTree.insertInTree(parentTree, isPlusChild, this);
321 return argTree;
322 }
323 // the leaf node represents an outside cell
324 final BSPTree<S> instanceTree =
325 leafFromInstance ? leaf : tree;
326 instanceTree.insertInTree(parentTree, isPlusChild, this);
327 return instanceTree;
328 }
329
330 /** {@inheritDoc} */
331 @Override
332 public BSPTree<S> fixNode(final BSPTree<S> node) {
333 // get a representative point in the degenerate cell
334 final BSPTree<S> cell = node.pruneAroundConvexCell(Boolean.TRUE, Boolean.FALSE, null);
335 final Region<S> r = region1.buildNew(cell);
336 final Point<S> p = r.getBarycenter();
337 return new BSPTree<S>(region1.checkPoint(p) == Location.INSIDE &&
338 region2.checkPoint(p) == Location.OUTSIDE);
339 }
340
341 }
342
343 /** Visitor removing internal nodes attributes. */
344 private class NodesCleaner implements BSPTreeVisitor<S> {
345
346 /** {@inheritDoc} */
347 @Override
348 public Order visitOrder(final BSPTree<S> node) {
349 return Order.PLUS_SUB_MINUS;
350 }
351
352 /** {@inheritDoc} */
353 @Override
354 public void visitInternalNode(final BSPTree<S> node) {
355 node.setAttribute(null);
356 }
357
358 /** {@inheritDoc} */
359 @Override
360 public void visitLeafNode(final BSPTree<S> node) {
361 }
362
363 }
364
365 /** Handler replacing nodes with vanishing cuts with leaf nodes. */
366 private class VanishingToLeaf implements VanishingCutHandler<S> {
367
368 /** Inside/outside indocator to use for ambiguous nodes. */
369 private final boolean inside;
370
371 /** Simple constructor.
372 * @param inside inside/outside indicator to use for ambiguous nodes
373 */
374 VanishingToLeaf(final boolean inside) {
375 this.inside = inside;
376 }
377
378 /** {@inheritDoc} */
379 @Override
380 public BSPTree<S> fixNode(final BSPTree<S> node) {
381 if (node.getPlus().getAttribute().equals(node.getMinus().getAttribute())) {
382 // no ambiguity
383 return new BSPTree<S>(node.getPlus().getAttribute());
384 } else {
385 // ambiguous node
386 return new BSPTree<S>(inside);
387 }
388 }
389
390 }
391
392 }