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  package org.apache.commons.math3.geometry.euclidean.threed;
18  
19  import java.awt.geom.AffineTransform;
20  import java.util.ArrayList;
21  import java.util.Arrays;
22  import java.util.Collection;
23  import java.util.List;
24  
25  import org.apache.commons.math3.exception.MathIllegalArgumentException;
26  import org.apache.commons.math3.exception.NumberIsTooSmallException;
27  import org.apache.commons.math3.exception.util.LocalizedFormats;
28  import org.apache.commons.math3.geometry.Point;
29  import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
30  import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
31  import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet;
32  import org.apache.commons.math3.geometry.euclidean.twod.SubLine;
33  import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
34  import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
35  import org.apache.commons.math3.geometry.partitioning.BSPTree;
36  import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
37  import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute;
38  import org.apache.commons.math3.geometry.partitioning.Hyperplane;
39  import org.apache.commons.math3.geometry.partitioning.Region;
40  import org.apache.commons.math3.geometry.partitioning.RegionFactory;
41  import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
42  import org.apache.commons.math3.geometry.partitioning.Transform;
43  import org.apache.commons.math3.util.FastMath;
44  
45  /** This class represents a 3D region: a set of polyhedrons.
46   * @since 3.0
47   */
48  public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
49  
50      /** Default value for tolerance. */
51      private static final double DEFAULT_TOLERANCE = 1.0e-10;
52  
53      /** Build a polyhedrons set representing the whole real line.
54       * @param tolerance tolerance below which points are considered identical
55       * @since 3.3
56       */
57      public PolyhedronsSet(final double tolerance) {
58          super(tolerance);
59      }
60  
61      /** Build a polyhedrons set from a BSP tree.
62       * <p>The leaf nodes of the BSP tree <em>must</em> have a
63       * {@code Boolean} attribute representing the inside status of
64       * the corresponding cell (true for inside cells, false for outside
65       * cells). In order to avoid building too many small objects, it is
66       * recommended to use the predefined constants
67       * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
68       * <p>
69       * This constructor is aimed at expert use, as building the tree may
70       * be a difficult task. It is not intended for general use and for
71       * performances reasons does not check thoroughly its input, as this would
72       * require walking the full tree each time. Failing to provide a tree with
73       * the proper attributes, <em>will</em> therefore generate problems like
74       * {@link NullPointerException} or {@link ClassCastException} only later on.
75       * This limitation is known and explains why this constructor is for expert
76       * use only. The caller does have the responsibility to provided correct arguments.
77       * </p>
78       * @param tree inside/outside BSP tree representing the region
79       * @param tolerance tolerance below which points are considered identical
80       * @since 3.3
81       */
82      public PolyhedronsSet(final BSPTree<Euclidean3D> tree, final double tolerance) {
83          super(tree, tolerance);
84      }
85  
86      /** Build a polyhedrons set from a Boundary REPresentation (B-rep) specified by sub-hyperplanes.
87       * <p>The boundary is provided as a collection of {@link
88       * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
89       * interior part of the region on its minus side and the exterior on
90       * its plus side.</p>
91       * <p>The boundary elements can be in any order, and can form
92       * several non-connected sets (like for example polyhedrons with holes
93       * or a set of disjoint polyhedrons considered as a whole). In
94       * fact, the elements do not even need to be connected together
95       * (their topological connections are not used here). However, if the
96       * boundary does not really separate an inside open from an outside
97       * open (open having here its topological meaning), then subsequent
98       * calls to the {@link Region#checkPoint(Point) checkPoint} method will
99       * not be meaningful anymore.</p>
100      * <p>If the boundary is empty, the region will represent the whole
101      * space.</p>
102      * @param boundary collection of boundary elements, as a
103      * collection of {@link SubHyperplane SubHyperplane} objects
104      * @param tolerance tolerance below which points are considered identical
105      * @since 3.3
106      */
107     public PolyhedronsSet(final Collection<SubHyperplane<Euclidean3D>> boundary,
108                           final double tolerance) {
109         super(boundary, tolerance);
110     }
111 
112     /** Build a polyhedrons set from a Boundary REPresentation (B-rep) specified by connected vertices.
113      * <p>
114      * The boundary is provided as a list of vertices and a list of facets.
115      * Each facet is specified as an integer array containing the arrays vertices
116      * indices in the vertices list. Each facet normal is oriented by right hand
117      * rule to the facet vertices list.
118      * </p>
119      * <p>
120      * Some basic sanity checks are performed but not everything is thoroughly
121      * assessed, so it remains under caller responsibility to ensure the vertices
122      * and facets are consistent and properly define a polyhedrons set.
123      * </p>
124      * @param vertices list of polyhedrons set vertices
125      * @param facets list of facets, as vertices indices in the vertices list
126      * @param tolerance tolerance below which points are considered identical
127      * @exception MathIllegalArgumentException if some basic sanity checks fail
128      * @since 3.5
129      */
130     public PolyhedronsSet(final List<Vector3D> vertices, final List<int[]> facets,
131                           final double tolerance) {
132         super(buildBoundary(vertices, facets, tolerance), tolerance);
133     }
134 
135     /** Build a parallellepipedic box.
136      * @param xMin low bound along the x direction
137      * @param xMax high bound along the x direction
138      * @param yMin low bound along the y direction
139      * @param yMax high bound along the y direction
140      * @param zMin low bound along the z direction
141      * @param zMax high bound along the z direction
142      * @param tolerance tolerance below which points are considered identical
143      * @since 3.3
144      */
145     public PolyhedronsSet(final double xMin, final double xMax,
146                           final double yMin, final double yMax,
147                           final double zMin, final double zMax,
148                           final double tolerance) {
149         super(buildBoundary(xMin, xMax, yMin, yMax, zMin, zMax, tolerance), tolerance);
150     }
151 
152     /** Build a polyhedrons set representing the whole real line.
153      * @deprecated as of 3.3, replaced with {@link #PolyhedronsSet(double)}
154      */
155     @Deprecated
156     public PolyhedronsSet() {
157         this(DEFAULT_TOLERANCE);
158     }
159 
160     /** Build a polyhedrons set from a BSP tree.
161      * <p>The leaf nodes of the BSP tree <em>must</em> have a
162      * {@code Boolean} attribute representing the inside status of
163      * the corresponding cell (true for inside cells, false for outside
164      * cells). In order to avoid building too many small objects, it is
165      * recommended to use the predefined constants
166      * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
167      * @param tree inside/outside BSP tree representing the region
168      * @deprecated as of 3.3, replaced with {@link #PolyhedronsSet(BSPTree, double)}
169      */
170     @Deprecated
171     public PolyhedronsSet(final BSPTree<Euclidean3D> tree) {
172         this(tree, DEFAULT_TOLERANCE);
173     }
174 
175     /** Build a polyhedrons set from a Boundary REPresentation (B-rep).
176      * <p>The boundary is provided as a collection of {@link
177      * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
178      * interior part of the region on its minus side and the exterior on
179      * its plus side.</p>
180      * <p>The boundary elements can be in any order, and can form
181      * several non-connected sets (like for example polyhedrons with holes
182      * or a set of disjoint polyhedrons considered as a whole). In
183      * fact, the elements do not even need to be connected together
184      * (their topological connections are not used here). However, if the
185      * boundary does not really separate an inside open from an outside
186      * open (open having here its topological meaning), then subsequent
187      * calls to the {@link Region#checkPoint(Point) checkPoint} method will
188      * not be meaningful anymore.</p>
189      * <p>If the boundary is empty, the region will represent the whole
190      * space.</p>
191      * @param boundary collection of boundary elements, as a
192      * collection of {@link SubHyperplane SubHyperplane} objects
193      * @deprecated as of 3.3, replaced with {@link #PolyhedronsSet(Collection, double)}
194      */
195     @Deprecated
196     public PolyhedronsSet(final Collection<SubHyperplane<Euclidean3D>> boundary) {
197         this(boundary, DEFAULT_TOLERANCE);
198     }
199 
200     /** Build a parallellepipedic box.
201      * @param xMin low bound along the x direction
202      * @param xMax high bound along the x direction
203      * @param yMin low bound along the y direction
204      * @param yMax high bound along the y direction
205      * @param zMin low bound along the z direction
206      * @param zMax high bound along the z direction
207      * @deprecated as of 3.3, replaced with {@link #PolyhedronsSet(double, double,
208      * double, double, double, double, double)}
209      */
210     @Deprecated
211     public PolyhedronsSet(final double xMin, final double xMax,
212                           final double yMin, final double yMax,
213                           final double zMin, final double zMax) {
214         this(xMin, xMax, yMin, yMax, zMin, zMax, DEFAULT_TOLERANCE);
215     }
216 
217     /** Build a parallellepipedic box boundary.
218      * @param xMin low bound along the x direction
219      * @param xMax high bound along the x direction
220      * @param yMin low bound along the y direction
221      * @param yMax high bound along the y direction
222      * @param zMin low bound along the z direction
223      * @param zMax high bound along the z direction
224      * @param tolerance tolerance below which points are considered identical
225      * @return boundary tree
226      * @since 3.3
227      */
228     private static BSPTree<Euclidean3D> buildBoundary(final double xMin, final double xMax,
229                                                       final double yMin, final double yMax,
230                                                       final double zMin, final double zMax,
231                                                       final double tolerance) {
232         if ((xMin >= xMax - tolerance) || (yMin >= yMax - tolerance) || (zMin >= zMax - tolerance)) {
233             // too thin box, build an empty polygons set
234             return new BSPTree<Euclidean3D>(Boolean.FALSE);
235         }
236         final Plane pxMin = new Plane(new Vector3D(xMin, 0,    0),   Vector3D.MINUS_I, tolerance);
237         final Plane pxMax = new Plane(new Vector3D(xMax, 0,    0),   Vector3D.PLUS_I,  tolerance);
238         final Plane pyMin = new Plane(new Vector3D(0,    yMin, 0),   Vector3D.MINUS_J, tolerance);
239         final Plane pyMax = new Plane(new Vector3D(0,    yMax, 0),   Vector3D.PLUS_J,  tolerance);
240         final Plane pzMin = new Plane(new Vector3D(0,    0,   zMin), Vector3D.MINUS_K, tolerance);
241         final Plane pzMax = new Plane(new Vector3D(0,    0,   zMax), Vector3D.PLUS_K,  tolerance);
242         @SuppressWarnings("unchecked")
243         final Region<Euclidean3D> boundary =
244         new RegionFactory<Euclidean3D>().buildConvex(pxMin, pxMax, pyMin, pyMax, pzMin, pzMax);
245         return boundary.getTree(false);
246     }
247 
248     /** Build boundary from vertices and facets.
249      * @param vertices list of polyhedrons set vertices
250      * @param facets list of facets, as vertices indices in the vertices list
251      * @param tolerance tolerance below which points are considered identical
252      * @return boundary as a list of sub-hyperplanes
253      * @exception MathIllegalArgumentException if some basic sanity checks fail
254      * @since 3.5
255      */
256     private static List<SubHyperplane<Euclidean3D>> buildBoundary(final List<Vector3D> vertices,
257                                                                   final List<int[]> facets,
258                                                                   final double tolerance) {
259 
260         // check vertices distances
261         for (int i = 0; i < vertices.size() - 1; ++i) {
262             final Vector3D vi = vertices.get(i);
263             for (int j = i + 1; j < vertices.size(); ++j) {
264                 if (Vector3D.distance(vi, vertices.get(j)) <= tolerance) {
265                     throw new MathIllegalArgumentException(LocalizedFormats.CLOSE_VERTICES,
266                                                            vi.getX(), vi.getY(), vi.getZ());
267                 }
268             }
269         }
270 
271         // find how vertices are referenced by facets
272         final int[][] references = findReferences(vertices, facets);
273 
274         // find how vertices are linked together by edges along the facets they belong to
275         final int[][] successors = successors(vertices, facets, references);
276 
277         // check edges orientations
278         for (int vA = 0; vA < vertices.size(); ++vA) {
279             for (final int vB : successors[vA]) {
280 
281                 if (vB >= 0) {
282                     // when facets are properly oriented, if vB is the successor of vA on facet f1,
283                     // then there must be an adjacent facet f2 where vA is the successor of vB
284                     boolean found = false;
285                     for (final int v : successors[vB]) {
286                         found = found || (v == vA);
287                     }
288                     if (!found) {
289                         final Vector3D start = vertices.get(vA);
290                         final Vector3D end   = vertices.get(vB);
291                         throw new MathIllegalArgumentException(LocalizedFormats.EDGE_CONNECTED_TO_ONE_FACET,
292                                                                start.getX(), start.getY(), start.getZ(),
293                                                                end.getX(),   end.getY(),   end.getZ());
294                     }
295                 }
296             }
297         }
298 
299         final List<SubHyperplane<Euclidean3D>> boundary = new ArrayList<SubHyperplane<Euclidean3D>>();
300 
301         for (final int[] facet : facets) {
302 
303             // define facet plane from the first 3 points
304             Plane plane = new Plane(vertices.get(facet[0]), vertices.get(facet[1]), vertices.get(facet[2]),
305                                     tolerance);
306 
307             // check all points are in the plane
308             final Vector2D[] two2Points = new Vector2D[facet.length];
309             for (int i = 0 ; i < facet.length; ++i) {
310                 final Vector3D v = vertices.get(facet[i]);
311                 if (!plane.contains(v)) {
312                     throw new MathIllegalArgumentException(LocalizedFormats.OUT_OF_PLANE,
313                                                            v.getX(), v.getY(), v.getZ());
314                 }
315                 two2Points[i] = plane.toSubSpace(v);
316             }
317 
318             // create the polygonal facet
319             boundary.add(new SubPlane(plane, new PolygonsSet(tolerance, two2Points)));
320 
321         }
322 
323         return boundary;
324 
325     }
326 
327     /** Find the facets that reference each edges.
328      * @param vertices list of polyhedrons set vertices
329      * @param facets list of facets, as vertices indices in the vertices list
330      * @return references array such that r[v][k] = f for some k if facet f contains vertex v
331      * @exception MathIllegalArgumentException if some facets have fewer than 3 vertices
332      * @since 3.5
333      */
334     private static int[][] findReferences(final List<Vector3D> vertices, final List<int[]> facets) {
335 
336         // find the maximum number of facets a vertex belongs to
337         final int[] nbFacets = new int[vertices.size()];
338         int maxFacets  = 0;
339         for (final int[] facet : facets) {
340             if (facet.length < 3) {
341                 throw new NumberIsTooSmallException(LocalizedFormats.WRONG_NUMBER_OF_POINTS,
342                                                     3, facet.length, true);
343             }
344             for (final int index : facet) {
345                 maxFacets = FastMath.max(maxFacets, ++nbFacets[index]);
346             }
347         }
348 
349         // set up the references array
350         final int[][] references = new int[vertices.size()][maxFacets];
351         for (int[] r : references) {
352             Arrays.fill(r, -1);
353         }
354         for (int f = 0; f < facets.size(); ++f) {
355             for (final int v : facets.get(f)) {
356                 // vertex v is referenced by facet f
357                 int k = 0;
358                 while (k < maxFacets && references[v][k] >= 0) {
359                     ++k;
360                 }
361                 references[v][k] = f;
362             }
363         }
364 
365         return references;
366 
367     }
368 
369     /** Find the successors of all vertices among all facets they belong to.
370      * @param vertices list of polyhedrons set vertices
371      * @param facets list of facets, as vertices indices in the vertices list
372      * @param references facets references array
373      * @return indices of vertices that follow vertex v in some facet (the array
374      * may contain extra entries at the end, set to negative indices)
375      * @exception MathIllegalArgumentException if the same vertex appears more than
376      * once in the successors list (which means one facet orientation is wrong)
377      * @since 3.5
378      */
379     private static int[][] successors(final List<Vector3D> vertices, final List<int[]> facets,
380                                       final int[][] references) {
381 
382         // create an array large enough
383         final int[][] successors = new int[vertices.size()][references[0].length];
384         for (final int[] s : successors) {
385             Arrays.fill(s, -1);
386         }
387 
388         for (int v = 0; v < vertices.size(); ++v) {
389             for (int k = 0; k < successors[v].length && references[v][k] >= 0; ++k) {
390 
391                 // look for vertex v
392                 final int[] facet = facets.get(references[v][k]);
393                 int i = 0;
394                 while (i < facet.length && facet[i] != v) {
395                     ++i;
396                 }
397 
398                 // we have found vertex v, we deduce its successor on current facet
399                 successors[v][k] = facet[(i + 1) % facet.length];
400                 for (int l = 0; l < k; ++l) {
401                     if (successors[v][l] == successors[v][k]) {
402                         final Vector3D start = vertices.get(v);
403                         final Vector3D end   = vertices.get(successors[v][k]);
404                         throw new MathIllegalArgumentException(LocalizedFormats.FACET_ORIENTATION_MISMATCH,
405                                                                start.getX(), start.getY(), start.getZ(),
406                                                                end.getX(),   end.getY(),   end.getZ());
407                     }
408                 }
409 
410             }
411         }
412 
413         return successors;
414 
415     }
416 
417     /** {@inheritDoc} */
418     @Override
419     public PolyhedronsSet buildNew(final BSPTree<Euclidean3D> tree) {
420         return new PolyhedronsSet(tree, getTolerance());
421     }
422 
423     /** {@inheritDoc} */
424     @Override
425     protected void computeGeometricalProperties() {
426 
427         // compute the contribution of all boundary facets
428         getTree(true).visit(new FacetsContributionVisitor());
429 
430         if (getSize() < 0) {
431             // the polyhedrons set as a finite outside
432             // surrounded by an infinite inside
433             setSize(Double.POSITIVE_INFINITY);
434             setBarycenter((Point<Euclidean3D>) Vector3D.NaN);
435         } else {
436             // the polyhedrons set is finite, apply the remaining scaling factors
437             setSize(getSize() / 3.0);
438             setBarycenter((Point<Euclidean3D>) new Vector3D(1.0 / (4 * getSize()), (Vector3D) getBarycenter()));
439         }
440 
441     }
442 
443     /** Visitor computing geometrical properties. */
444     private class FacetsContributionVisitor implements BSPTreeVisitor<Euclidean3D> {
445 
446         /** Simple constructor. */
447         public FacetsContributionVisitor() {
448             setSize(0);
449             setBarycenter((Point<Euclidean3D>) new Vector3D(0, 0, 0));
450         }
451 
452         /** {@inheritDoc} */
453         public Order visitOrder(final BSPTree<Euclidean3D> node) {
454             return Order.MINUS_SUB_PLUS;
455         }
456 
457         /** {@inheritDoc} */
458         public void visitInternalNode(final BSPTree<Euclidean3D> node) {
459             @SuppressWarnings("unchecked")
460             final BoundaryAttribute<Euclidean3D> attribute =
461                 (BoundaryAttribute<Euclidean3D>) node.getAttribute();
462             if (attribute.getPlusOutside() != null) {
463                 addContribution(attribute.getPlusOutside(), false);
464             }
465             if (attribute.getPlusInside() != null) {
466                 addContribution(attribute.getPlusInside(), true);
467             }
468         }
469 
470         /** {@inheritDoc} */
471         public void visitLeafNode(final BSPTree<Euclidean3D> node) {
472         }
473 
474         /** Add he contribution of a boundary facet.
475          * @param facet boundary facet
476          * @param reversed if true, the facet has the inside on its plus side
477          */
478         private void addContribution(final SubHyperplane<Euclidean3D> facet, final boolean reversed) {
479 
480             final Region<Euclidean2D> polygon = ((SubPlane) facet).getRemainingRegion();
481             final double area    = polygon.getSize();
482 
483             if (Double.isInfinite(area)) {
484                 setSize(Double.POSITIVE_INFINITY);
485                 setBarycenter((Point<Euclidean3D>) Vector3D.NaN);
486             } else {
487 
488                 final Plane    plane  = (Plane) facet.getHyperplane();
489                 final Vector3D facetB = plane.toSpace(polygon.getBarycenter());
490                 double   scaled = area * facetB.dotProduct(plane.getNormal());
491                 if (reversed) {
492                     scaled = -scaled;
493                 }
494 
495                 setSize(getSize() + scaled);
496                 setBarycenter((Point<Euclidean3D>) new Vector3D(1.0, (Vector3D) getBarycenter(), scaled, facetB));
497 
498             }
499 
500         }
501 
502     }
503 
504     /** Get the first sub-hyperplane crossed by a semi-infinite line.
505      * @param point start point of the part of the line considered
506      * @param line line to consider (contains point)
507      * @return the first sub-hyperplane crossed by the line after the
508      * given point, or null if the line does not intersect any
509      * sub-hyperplane
510      */
511     public SubHyperplane<Euclidean3D> firstIntersection(final Vector3D point, final Line line) {
512         return recurseFirstIntersection(getTree(true), point, line);
513     }
514 
515     /** Get the first sub-hyperplane crossed by a semi-infinite line.
516      * @param node current node
517      * @param point start point of the part of the line considered
518      * @param line line to consider (contains point)
519      * @return the first sub-hyperplane crossed by the line after the
520      * given point, or null if the line does not intersect any
521      * sub-hyperplane
522      */
523     private SubHyperplane<Euclidean3D> recurseFirstIntersection(final BSPTree<Euclidean3D> node,
524                                                                 final Vector3D point,
525                                                                 final Line line) {
526 
527         final SubHyperplane<Euclidean3D> cut = node.getCut();
528         if (cut == null) {
529             return null;
530         }
531         final BSPTree<Euclidean3D> minus = node.getMinus();
532         final BSPTree<Euclidean3D> plus  = node.getPlus();
533         final Plane                plane = (Plane) cut.getHyperplane();
534 
535         // establish search order
536         final double offset = plane.getOffset((Point<Euclidean3D>) point);
537         final boolean in    = FastMath.abs(offset) < getTolerance();
538         final BSPTree<Euclidean3D> near;
539         final BSPTree<Euclidean3D> far;
540         if (offset < 0) {
541             near = minus;
542             far  = plus;
543         } else {
544             near = plus;
545             far  = minus;
546         }
547 
548         if (in) {
549             // search in the cut hyperplane
550             final SubHyperplane<Euclidean3D> facet = boundaryFacet(point, node);
551             if (facet != null) {
552                 return facet;
553             }
554         }
555 
556         // search in the near branch
557         final SubHyperplane<Euclidean3D> crossed = recurseFirstIntersection(near, point, line);
558         if (crossed != null) {
559             return crossed;
560         }
561 
562         if (!in) {
563             // search in the cut hyperplane
564             final Vector3D hit3D = plane.intersection(line);
565             if (hit3D != null && line.getAbscissa(hit3D) > line.getAbscissa(point)) {
566                 final SubHyperplane<Euclidean3D> facet = boundaryFacet(hit3D, node);
567                 if (facet != null) {
568                     return facet;
569                 }
570             }
571         }
572 
573         // search in the far branch
574         return recurseFirstIntersection(far, point, line);
575 
576     }
577 
578     /** Check if a point belongs to the boundary part of a node.
579      * @param point point to check
580      * @param node node containing the boundary facet to check
581      * @return the boundary facet this points belongs to (or null if it
582      * does not belong to any boundary facet)
583      */
584     private SubHyperplane<Euclidean3D> boundaryFacet(final Vector3D point,
585                                                      final BSPTree<Euclidean3D> node) {
586         final Vector2D point2D = ((Plane) node.getCut().getHyperplane()).toSubSpace((Point<Euclidean3D>) point);
587         @SuppressWarnings("unchecked")
588         final BoundaryAttribute<Euclidean3D> attribute =
589             (BoundaryAttribute<Euclidean3D>) node.getAttribute();
590         if ((attribute.getPlusOutside() != null) &&
591             (((SubPlane) attribute.getPlusOutside()).getRemainingRegion().checkPoint(point2D) == Location.INSIDE)) {
592             return attribute.getPlusOutside();
593         }
594         if ((attribute.getPlusInside() != null) &&
595             (((SubPlane) attribute.getPlusInside()).getRemainingRegion().checkPoint(point2D) == Location.INSIDE)) {
596             return attribute.getPlusInside();
597         }
598         return null;
599     }
600 
601     /** Rotate the region around the specified point.
602      * <p>The instance is not modified, a new instance is created.</p>
603      * @param center rotation center
604      * @param rotation vectorial rotation operator
605      * @return a new instance representing the rotated region
606      */
607     public PolyhedronsSet rotate(final Vector3D center, final Rotation rotation) {
608         return (PolyhedronsSet) applyTransform(new RotationTransform(center, rotation));
609     }
610 
611     /** 3D rotation as a Transform. */
612     private static class RotationTransform implements Transform<Euclidean3D, Euclidean2D> {
613 
614         /** Center point of the rotation. */
615         private Vector3D   center;
616 
617         /** Vectorial rotation. */
618         private Rotation   rotation;
619 
620         /** Cached original hyperplane. */
621         private Plane cachedOriginal;
622 
623         /** Cached 2D transform valid inside the cached original hyperplane. */
624         private Transform<Euclidean2D, Euclidean1D>  cachedTransform;
625 
626         /** Build a rotation transform.
627          * @param center center point of the rotation
628          * @param rotation vectorial rotation
629          */
630         public RotationTransform(final Vector3D center, final Rotation rotation) {
631             this.center   = center;
632             this.rotation = rotation;
633         }
634 
635         /** {@inheritDoc} */
636         public Vector3D apply(final Point<Euclidean3D> point) {
637             final Vector3D delta = ((Vector3D) point).subtract(center);
638             return new Vector3D(1.0, center, 1.0, rotation.applyTo(delta));
639         }
640 
641         /** {@inheritDoc} */
642         public Plane apply(final Hyperplane<Euclidean3D> hyperplane) {
643             return ((Plane) hyperplane).rotate(center, rotation);
644         }
645 
646         /** {@inheritDoc} */
647         public SubHyperplane<Euclidean2D> apply(final SubHyperplane<Euclidean2D> sub,
648                                                 final Hyperplane<Euclidean3D> original,
649                                                 final Hyperplane<Euclidean3D> transformed) {
650             if (original != cachedOriginal) {
651                 // we have changed hyperplane, reset the in-hyperplane transform
652 
653                 final Plane    oPlane = (Plane) original;
654                 final Plane    tPlane = (Plane) transformed;
655                 final Vector3D p00    = oPlane.getOrigin();
656                 final Vector3D p10    = oPlane.toSpace((Point<Euclidean2D>) new Vector2D(1.0, 0.0));
657                 final Vector3D p01    = oPlane.toSpace((Point<Euclidean2D>) new Vector2D(0.0, 1.0));
658                 final Vector2D tP00   = tPlane.toSubSpace((Point<Euclidean3D>) apply(p00));
659                 final Vector2D tP10   = tPlane.toSubSpace((Point<Euclidean3D>) apply(p10));
660                 final Vector2D tP01   = tPlane.toSubSpace((Point<Euclidean3D>) apply(p01));
661                 final AffineTransform at =
662                     new AffineTransform(tP10.getX() - tP00.getX(), tP10.getY() - tP00.getY(),
663                                         tP01.getX() - tP00.getX(), tP01.getY() - tP00.getY(),
664                                         tP00.getX(), tP00.getY());
665 
666                 cachedOriginal  = (Plane) original;
667                 cachedTransform = org.apache.commons.math3.geometry.euclidean.twod.Line.getTransform(at);
668 
669             }
670             return ((SubLine) sub).applyTransform(cachedTransform);
671         }
672 
673     }
674 
675     /** Translate the region by the specified amount.
676      * <p>The instance is not modified, a new instance is created.</p>
677      * @param translation translation to apply
678      * @return a new instance representing the translated region
679      */
680     public PolyhedronsSet translate(final Vector3D translation) {
681         return (PolyhedronsSet) applyTransform(new TranslationTransform(translation));
682     }
683 
684     /** 3D translation as a transform. */
685     private static class TranslationTransform implements Transform<Euclidean3D, Euclidean2D> {
686 
687         /** Translation vector. */
688         private Vector3D   translation;
689 
690         /** Cached original hyperplane. */
691         private Plane cachedOriginal;
692 
693         /** Cached 2D transform valid inside the cached original hyperplane. */
694         private Transform<Euclidean2D, Euclidean1D>  cachedTransform;
695 
696         /** Build a translation transform.
697          * @param translation translation vector
698          */
699         public TranslationTransform(final Vector3D translation) {
700             this.translation = translation;
701         }
702 
703         /** {@inheritDoc} */
704         public Vector3D apply(final Point<Euclidean3D> point) {
705             return new Vector3D(1.0, (Vector3D) point, 1.0, translation);
706         }
707 
708         /** {@inheritDoc} */
709         public Plane apply(final Hyperplane<Euclidean3D> hyperplane) {
710             return ((Plane) hyperplane).translate(translation);
711         }
712 
713         /** {@inheritDoc} */
714         public SubHyperplane<Euclidean2D> apply(final SubHyperplane<Euclidean2D> sub,
715                                                 final Hyperplane<Euclidean3D> original,
716                                                 final Hyperplane<Euclidean3D> transformed) {
717             if (original != cachedOriginal) {
718                 // we have changed hyperplane, reset the in-hyperplane transform
719 
720                 final Plane   oPlane = (Plane) original;
721                 final Plane   tPlane = (Plane) transformed;
722                 final Vector2D shift  = tPlane.toSubSpace((Point<Euclidean3D>) apply(oPlane.getOrigin()));
723                 final AffineTransform at =
724                     AffineTransform.getTranslateInstance(shift.getX(), shift.getY());
725 
726                 cachedOriginal  = (Plane) original;
727                 cachedTransform =
728                         org.apache.commons.math3.geometry.euclidean.twod.Line.getTransform(at);
729 
730             }
731 
732             return ((SubLine) sub).applyTransform(cachedTransform);
733 
734         }
735 
736     }
737 
738 }