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