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.ArrayList;
25 import java.util.Collection;
26 import java.util.Comparator;
27 import java.util.HashMap;
28 import java.util.Iterator;
29 import java.util.Map;
30 import java.util.TreeSet;
31
32 import org.hipparchus.geometry.Point;
33 import org.hipparchus.geometry.Space;
34
35 /** Abstract class for all regions, independently of geometry type or dimension.
36
37 * @param <S> Type of the space.
38 * @param <P> Type of the points in space.
39 * @param <H> Type of the hyperplane.
40 * @param <I> Type of the sub-hyperplane.
41 * @param <T> Type of the sub-space.
42 * @param <Q> Type of the points in sub-space.
43 * @param <F> Type of the hyperplane.
44 * @param <J> Type of the sub-hyperplane.
45
46 */
47 public abstract class AbstractRegion<S extends Space,
48 P extends Point<S, P>,
49 H extends Hyperplane<S, P, H, I>,
50 I extends SubHyperplane<S, P, H, I>,
51 T extends Space, Q extends Point<T, Q>,
52 F extends Hyperplane<T, Q, F, J>,
53 J extends SubHyperplane<T, Q, F, J>>
54 implements Region<S, P, H, I> {
55
56 /** Inside/Outside BSP tree. */
57 private final BSPTree<S, P, H, I> tree;
58
59 /** Tolerance below which points are considered to belong to hyperplanes. */
60 private final double tolerance;
61
62 /** Size of the instance. */
63 private double size;
64
65 /** Barycenter. */
66 private P barycenter;
67
68 /** Build a region representing the whole space.
69 * @param tolerance tolerance below which points are considered identical.
70 */
71 protected AbstractRegion(final double tolerance) {
72 this.tree = new BSPTree<>(Boolean.TRUE);
73 this.tolerance = tolerance;
74 }
75
76 /** Build a region from an inside/outside BSP tree.
77 * <p>The leaf nodes of the BSP tree <em>must</em> have a
78 * {@code Boolean} attribute representing the inside status of
79 * the corresponding cell (true for inside cells, false for outside
80 * cells). In order to avoid building too many small objects, it is
81 * recommended to use the predefined constants
82 * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
83 * tree also <em>must</em> have either null internal nodes or
84 * internal nodes representing the boundary as specified in the
85 * {@link #getTree getTree} method).</p>
86 * @param tree inside/outside BSP tree representing the region
87 * @param tolerance tolerance below which points are considered identical.
88 */
89 protected AbstractRegion(final BSPTree<S, P, H, I> tree, final double tolerance) {
90 this.tree = tree;
91 this.tolerance = tolerance;
92 }
93
94 /** Build a Region from a Boundary REPresentation (B-rep).
95 * <p>The boundary is provided as a collection of {@link
96 * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
97 * interior part of the region on its minus side and the exterior on
98 * its plus side.</p>
99 * <p>The boundary elements can be in any order, and can form
100 * several non-connected sets (like for example polygons with holes
101 * or a set of disjoints polyhedrons considered as a whole). In
102 * fact, the elements do not even need to be connected together
103 * (their topological connections are not used here). However, if the
104 * boundary does not really separate an inside open from an outside
105 * open (open having here its topological meaning), then subsequent
106 * calls to the {@link #checkPoint(Point) checkPoint} method will not be
107 * meaningful anymore.</p>
108 * <p>If the boundary is empty, the region will represent the whole
109 * space.</p>
110 * @param boundary collection of boundary elements, as a
111 * collection of {@link SubHyperplane SubHyperplane} objects
112 * @param tolerance tolerance below which points are considered identical.
113 */
114 protected AbstractRegion(final Collection<I> boundary, final double tolerance) {
115
116 this.tolerance = tolerance;
117
118 if (boundary.isEmpty()) {
119
120 // the tree represents the whole space
121 tree = new BSPTree<>(Boolean.TRUE);
122
123 } else {
124
125 // sort the boundary elements in decreasing size order
126 // (we don't want equal size elements to be removed, so
127 // we use a trick to fool the TreeSet)
128 final TreeSet<I> ordered = new TreeSet<>(new Comparator<I>() {
129 /** {@inheritDoc} */
130 @Override
131 public int compare(final I o1, final I o2) {
132 final double size1 = o1.getSize();
133 final double size2 = o2.getSize();
134 return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
135 }
136 });
137 ordered.addAll(boundary);
138
139 // build the tree top-down
140 tree = new BSPTree<>();
141 insertCuts(tree, ordered);
142
143 // set up the inside/outside flags
144 tree.visit(new BSPTreeVisitor<S, P, H, I>() {
145
146 /** {@inheritDoc} */
147 @Override
148 public Order visitOrder(final BSPTree<S, P, H, I> node) {
149 return Order.PLUS_SUB_MINUS;
150 }
151
152 /** {@inheritDoc} */
153 @Override
154 public void visitInternalNode(final BSPTree<S, P, H, I> node) {
155 }
156
157 /** {@inheritDoc} */
158 @Override
159 public void visitLeafNode(final BSPTree<S, P, H, I> node) {
160 if (node.getParent() == null || node == node.getParent().getMinus()) {
161 node.setAttribute(Boolean.TRUE);
162 } else {
163 node.setAttribute(Boolean.FALSE);
164 }
165 }
166 });
167
168 }
169
170 }
171
172 /** Build a convex region from an array of bounding hyperplanes.
173 * @param hyperplanes array of bounding hyperplanes (if null, an
174 * empty region will be built)
175 * @param tolerance tolerance below which points are considered identical.
176 */
177 public AbstractRegion(final H[] hyperplanes, final double tolerance) {
178 this.tolerance = tolerance;
179 if ((hyperplanes == null) || (hyperplanes.length == 0)) {
180 tree = new BSPTree<>(Boolean.FALSE);
181 } else {
182
183 // use the first hyperplane to build the right class
184 tree = hyperplanes[0].wholeSpace().getTree(false);
185
186 // chop off parts of the space
187 BSPTree<S, P, H, I> node = tree;
188 node.setAttribute(Boolean.TRUE);
189 for (final H hyperplane : hyperplanes) {
190 if (node.insertCut(hyperplane)) {
191 node.setAttribute(null);
192 node.getPlus().setAttribute(Boolean.FALSE);
193 node = node.getMinus();
194 node.setAttribute(Boolean.TRUE);
195 }
196 }
197
198 }
199
200 }
201
202 /** {@inheritDoc} */
203 @Override
204 public abstract AbstractRegion<S, P, H, I, T, Q, F, J> buildNew(BSPTree<S, P, H, I> newTree);
205
206 /** Get the tolerance below which points are considered to belong to hyperplanes.
207 * @return tolerance below which points are considered to belong to hyperplanes
208 */
209 public double getTolerance() {
210 return tolerance;
211 }
212
213 /** Recursively build a tree by inserting cut sub-hyperplanes.
214 * @param node current tree node (it is a leaf node at the beginning
215 * of the call)
216 * @param boundary collection of edges belonging to the cell defined
217 * by the node
218 */
219 private void insertCuts(final BSPTree<S, P, H, I> node, final Collection<I> boundary) {
220
221 final Iterator<I> iterator = boundary.iterator();
222
223 // build the current level
224 H inserted = null;
225 while ((inserted == null) && iterator.hasNext()) {
226 inserted = iterator.next().getHyperplane();
227 if (!node.insertCut(inserted.copySelf())) {
228 inserted = null;
229 }
230 }
231
232 if (!iterator.hasNext()) {
233 return;
234 }
235
236 // distribute the remaining edges in the two sub-trees
237 final ArrayList<I> plusList = new ArrayList<>();
238 final ArrayList<I> minusList = new ArrayList<>();
239 while (iterator.hasNext()) {
240 final I other = iterator.next();
241 final SubHyperplane.SplitSubHyperplane<S, P, H, I> split = other.split(inserted);
242 switch (split.getSide()) {
243 case PLUS:
244 plusList.add(other);
245 break;
246 case MINUS:
247 minusList.add(other);
248 break;
249 case BOTH:
250 plusList.add(split.getPlus());
251 minusList.add(split.getMinus());
252 break;
253 default:
254 // ignore the sub-hyperplanes belonging to the cut hyperplane
255 }
256 }
257
258 // recurse through lower levels
259 insertCuts(node.getPlus(), plusList);
260 insertCuts(node.getMinus(), minusList);
261
262 }
263
264 /** {@inheritDoc} */
265 @Override
266 public AbstractRegion<S, P, H, I, T, Q, F, J> copySelf() {
267 return buildNew(tree.copySelf());
268 }
269
270 /** {@inheritDoc} */
271 @Override
272 public boolean isEmpty() {
273 return isEmpty(tree);
274 }
275
276 /** {@inheritDoc} */
277 @Override
278 public boolean isEmpty(final BSPTree<S, P, H, I> node) {
279
280 // we use a recursive function rather than the BSPTreeVisitor
281 // interface because we can stop visiting the tree as soon as we
282 // have found an inside cell
283
284 if (node.getCut() == null) {
285 // if we find an inside node, the region is not empty
286 return !((Boolean) node.getAttribute());
287 }
288
289 // check both sides of the sub-tree
290 return isEmpty(node.getMinus()) && isEmpty(node.getPlus());
291
292 }
293
294 /** {@inheritDoc} */
295 @Override
296 public boolean isFull() {
297 return isFull(tree);
298 }
299
300 /** {@inheritDoc} */
301 @Override
302 public boolean isFull(final BSPTree<S, P, H, I> node) {
303
304 // we use a recursive function rather than the BSPTreeVisitor
305 // interface because we can stop visiting the tree as soon as we
306 // have found an outside cell
307
308 if (node.getCut() == null) {
309 // if we find an outside node, the region does not cover full space
310 return (Boolean) node.getAttribute();
311 }
312
313 // check both sides of the sub-tree
314 return isFull(node.getMinus()) && isFull(node.getPlus());
315
316 }
317
318 /** {@inheritDoc} */
319 @Override
320 public boolean contains(final Region<S, P, H, I> region) {
321 return new RegionFactory<S, P, H, I>().difference(region, this).isEmpty();
322 }
323
324 /** {@inheritDoc}
325 */
326 @Override
327 public BoundaryProjection<S, P> projectToBoundary(final P point) {
328 final BoundaryProjector<S, P, H, I, T, Q, F, J> projector = new BoundaryProjector<>(point);
329 getTree(true).visit(projector);
330 return projector.getProjection();
331 }
332
333 /** {@inheritDoc} */
334 @Override
335 public Location checkPoint(final P point) {
336 return checkPoint(tree, point);
337 }
338
339 /** Check a point with respect to the region starting at a given node.
340 * @param node root node of the region
341 * @param point point to check
342 * @return a code representing the point status: either {@link
343 * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE
344 * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY}
345 */
346 protected Location checkPoint(final BSPTree<S, P, H, I> node, final P point) {
347 final BSPTree<S, P, H, I> cell = node.getCell(point, tolerance);
348 if (cell.getCut() == null) {
349 // the point is in the interior of a cell, just check the attribute
350 return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE;
351 }
352
353 // the point is on a cut-sub-hyperplane, is it on a boundary ?
354 final Location minusCode = checkPoint(cell.getMinus(), point);
355 final Location plusCode = checkPoint(cell.getPlus(), point);
356 return (minusCode == plusCode) ? minusCode : Location.BOUNDARY;
357
358 }
359
360 /** {@inheritDoc} */
361 @Override
362 public BSPTree<S, P, H, I> getTree(final boolean includeBoundaryAttributes) {
363 if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
364 // compute the boundary attributes
365 tree.visit(new BoundaryBuilder<>());
366 }
367 return tree;
368 }
369
370 /** {@inheritDoc} */
371 @Override
372 public double getBoundarySize() {
373 final BoundarySizeVisitor<S, P, H, I> visitor = new BoundarySizeVisitor<>();
374 getTree(true).visit(visitor);
375 return visitor.getSize();
376 }
377
378 /** {@inheritDoc} */
379 @Override
380 public double getSize() {
381 if (barycenter == null) {
382 computeGeometricalProperties();
383 }
384 return size;
385 }
386
387 /** Set the size of the instance.
388 * @param size size of the instance
389 */
390 protected void setSize(final double size) {
391 this.size = size;
392 }
393
394 /** {@inheritDoc} */
395 @Override
396 public P getBarycenter() {
397 if (barycenter == null) {
398 computeGeometricalProperties();
399 }
400 return barycenter;
401 }
402
403 /** Set the barycenter of the instance.
404 * @param barycenter barycenter of the instance
405 */
406 protected void setBarycenter(final P barycenter) {
407 this.barycenter = barycenter;
408 }
409
410 /** Compute some geometrical properties.
411 * <p>The properties to compute are the barycenter and the size.</p>
412 */
413 protected abstract void computeGeometricalProperties();
414
415 /** {@inheritDoc} */
416 @Override
417 public I intersection(final I sub) {
418 return recurseIntersection(tree, sub);
419 }
420
421 /** Recursively compute the parts of a sub-hyperplane that are
422 * contained in the region.
423 * @param node current BSP tree node
424 * @param sub sub-hyperplane traversing the region
425 * @return filtered sub-hyperplane
426 */
427 private I recurseIntersection(final BSPTree<S, P, H, I> node, final I sub) {
428
429 if (node.getCut() == null) {
430 return (Boolean) node.getAttribute() ? sub.copySelf() : null;
431 }
432
433 final H hyperplane = node.getCut().getHyperplane();
434 final SubHyperplane.SplitSubHyperplane<S, P, H, I> split = sub.split(hyperplane);
435 if (split.getPlus() != null) {
436 if (split.getMinus() != null) {
437 // both sides
438 final I plus = recurseIntersection(node.getPlus(), split.getPlus());
439 final I minus = recurseIntersection(node.getMinus(), split.getMinus());
440 if (plus == null) {
441 return minus;
442 } else if (minus == null) {
443 return plus;
444 } else {
445 return plus.reunite(minus);
446 }
447 } else {
448 // only on plus side
449 return recurseIntersection(node.getPlus(), sub);
450 }
451 } else if (split.getMinus() != null) {
452 // only on minus side
453 return recurseIntersection(node.getMinus(), sub);
454 } else {
455 // on hyperplane
456 return recurseIntersection(node.getPlus(),
457 recurseIntersection(node.getMinus(), sub));
458 }
459
460 }
461
462 /** Transform a region.
463 * <p>Applying a transform to a region consist in applying the
464 * transform to all the hyperplanes of the underlying BSP tree and
465 * of the boundary (and also to the sub-hyperplanes embedded in
466 * these hyperplanes) and to the barycenter. The instance is not
467 * modified, a new instance is built.</p>
468 * @param transform transform to apply
469 * @return a new region, resulting from the application of the
470 * transform to the instance
471 */
472 public AbstractRegion<S, P, H, I, T, Q, F, J> applyTransform(final Transform<S, P, H, I, T, Q, F, J> transform) {
473
474 // transform the tree, except for boundary attribute splitters
475 final Map<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> map = new HashMap<>();
476 final BSPTree<S, P, H, I> transformedTree = recurseTransform(getTree(false), transform, map);
477
478 // set up the boundary attributes splitters
479 for (final Map.Entry<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> entry : map.entrySet()) {
480 if (entry.getKey().getCut() != null) {
481 @SuppressWarnings("unchecked")
482 BoundaryAttribute<S, P, H, I> original = (BoundaryAttribute<S, P, H, I>) entry.getKey().getAttribute();
483 if (original != null) {
484 @SuppressWarnings("unchecked")
485 BoundaryAttribute<S, P, H, I> transformed = (BoundaryAttribute<S, P, H, I>) entry.getValue().getAttribute();
486 for (final BSPTree<S, P, H, I> splitter : original.getSplitters()) {
487 transformed.getSplitters().add(map.get(splitter));
488 }
489 }
490 }
491 }
492
493 return buildNew(transformedTree);
494
495 }
496
497 /** Recursively transform an inside/outside BSP-tree.
498 * @param node current BSP tree node
499 * @param transform transform to apply
500 * @param map transformed nodes map
501 * @return a new tree
502 */
503 @SuppressWarnings("unchecked")
504 private BSPTree<S, P, H, I> recurseTransform(final BSPTree<S, P, H, I> node, final Transform<S, P, H, I, T, Q, F, J> transform,
505 final Map<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> map) {
506
507 final BSPTree<S, P, H, I> transformedNode;
508 if (node.getCut() == null) {
509 transformedNode = new BSPTree<>(node.getAttribute());
510 } else {
511
512 final I sub = node.getCut();
513 final I tSub = ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) sub).applyTransform(transform);
514 BoundaryAttribute<S, P, H, I> attribute = (BoundaryAttribute<S, P, H, I>) node.getAttribute();
515 if (attribute != null) {
516 final I tPO = (attribute.getPlusOutside() == null) ?
517 null : ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) attribute.getPlusOutside()).applyTransform(transform);
518 final I tPI = (attribute.getPlusInside() == null) ?
519 null : ((AbstractSubHyperplane<S, P, H, I, T, Q, F, J>) attribute.getPlusInside()).applyTransform(transform);
520 // we start with an empty list of splitters, it will be filled in out of recursion
521 attribute = new BoundaryAttribute<>(tPO, tPI, new NodesSet<>());
522 }
523
524 transformedNode = new BSPTree<>(tSub,
525 recurseTransform(node.getPlus(), transform, map),
526 recurseTransform(node.getMinus(), transform, map),
527 attribute);
528 }
529
530 map.put(node, transformedNode);
531 return transformedNode;
532
533 }
534
535 }