001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.geometry.euclidean.threed;
018
019import java.util.ArrayList;
020import java.util.Arrays;
021import java.util.Collection;
022import java.util.List;
023
024import org.apache.commons.math3.exception.MathIllegalArgumentException;
025import org.apache.commons.math3.exception.NumberIsTooSmallException;
026import org.apache.commons.math3.exception.util.LocalizedFormats;
027import org.apache.commons.math3.geometry.Point;
028import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
029import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
030import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet;
031import org.apache.commons.math3.geometry.euclidean.twod.SubLine;
032import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
033import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
034import org.apache.commons.math3.geometry.partitioning.BSPTree;
035import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
036import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute;
037import org.apache.commons.math3.geometry.partitioning.Hyperplane;
038import org.apache.commons.math3.geometry.partitioning.Region;
039import org.apache.commons.math3.geometry.partitioning.RegionFactory;
040import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
041import org.apache.commons.math3.geometry.partitioning.Transform;
042import org.apache.commons.math3.util.FastMath;
043
044/** This class represents a 3D region: a set of polyhedrons.
045 * @since 3.0
046 */
047public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
048
049    /** Default value for tolerance. */
050    private static final double DEFAULT_TOLERANCE = 1.0e-10;
051
052    /** Build a polyhedrons set representing the whole real line.
053     * @param tolerance tolerance below which points are considered identical
054     * @since 3.3
055     */
056    public PolyhedronsSet(final double tolerance) {
057        super(tolerance);
058    }
059
060    /** Build a polyhedrons set from a BSP tree.
061     * <p>The leaf nodes of the BSP tree <em>must</em> have a
062     * {@code Boolean} attribute representing the inside status of
063     * the corresponding cell (true for inside cells, false for outside
064     * cells). In order to avoid building too many small objects, it is
065     * recommended to use the predefined constants
066     * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
067     * <p>
068     * This constructor is aimed at expert use, as building the tree may
069     * be a difficult task. It is not intended for general use and for
070     * performances reasons does not check thoroughly its input, as this would
071     * require walking the full tree each time. Failing to provide a tree with
072     * the proper attributes, <em>will</em> therefore generate problems like
073     * {@link NullPointerException} or {@link ClassCastException} only later on.
074     * This limitation is known and explains why this constructor is for expert
075     * use only. The caller does have the responsibility to provided correct arguments.
076     * </p>
077     * @param tree inside/outside BSP tree representing the region
078     * @param tolerance tolerance below which points are considered identical
079     * @since 3.3
080     */
081    public PolyhedronsSet(final BSPTree<Euclidean3D> tree, final double tolerance) {
082        super(tree, tolerance);
083    }
084
085    /** Build a polyhedrons set from a Boundary REPresentation (B-rep) specified by sub-hyperplanes.
086     * <p>The boundary is provided as a collection of {@link
087     * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
088     * interior part of the region on its minus side and the exterior on
089     * its plus side.</p>
090     * <p>The boundary elements can be in any order, and can form
091     * several non-connected sets (like for example polyhedrons with holes
092     * or a set of disjoint polyhedrons considered as a whole). In
093     * fact, the elements do not even need to be connected together
094     * (their topological connections are not used here). However, if the
095     * boundary does not really separate an inside open from an outside
096     * open (open having here its topological meaning), then subsequent
097     * calls to the {@link Region#checkPoint(Point) checkPoint} method will
098     * not be meaningful anymore.</p>
099     * <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}