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