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    *      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  
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 }