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.awt.geom.AffineTransform;
020import java.util.ArrayList;
021import java.util.Arrays;
022import java.util.Collection;
023import java.util.List;
024
025import org.apache.commons.math3.exception.MathIllegalArgumentException;
026import org.apache.commons.math3.exception.NumberIsTooSmallException;
027import org.apache.commons.math3.exception.util.LocalizedFormats;
028import org.apache.commons.math3.geometry.Point;
029import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
030import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
031import org.apache.commons.math3.geometry.euclidean.twod.PolygonsSet;
032import org.apache.commons.math3.geometry.euclidean.twod.SubLine;
033import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
034import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
035import org.apache.commons.math3.geometry.partitioning.BSPTree;
036import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
037import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute;
038import org.apache.commons.math3.geometry.partitioning.Hyperplane;
039import org.apache.commons.math3.geometry.partitioning.Region;
040import org.apache.commons.math3.geometry.partitioning.RegionFactory;
041import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
042import org.apache.commons.math3.geometry.partitioning.Transform;
043import org.apache.commons.math3.util.FastMath;
044
045/** This class represents a 3D region: a set of polyhedrons.
046 * @since 3.0
047 */
048public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
049
050    /** Default value for tolerance. */
051    private static final double DEFAULT_TOLERANCE = 1.0e-10;
052
053    /** Build a polyhedrons set representing the whole real line.
054     * @param tolerance tolerance below which points are considered identical
055     * @since 3.3
056     */
057    public PolyhedronsSet(final double tolerance) {
058        super(tolerance);
059    }
060
061    /** Build a polyhedrons set from a BSP tree.
062     * <p>The leaf nodes of the BSP tree <em>must</em> have a
063     * {@code Boolean} attribute representing the inside status of
064     * the corresponding cell (true for inside cells, false for outside
065     * cells). In order to avoid building too many small objects, it is
066     * recommended to use the predefined constants
067     * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
068     * <p>
069     * This constructor is aimed at expert use, as building the tree may
070     * be a difficult task. It is not intended for general use and for
071     * performances reasons does not check thoroughly its input, as this would
072     * require walking the full tree each time. Failing to provide a tree with
073     * the proper attributes, <em>will</em> therefore generate problems like
074     * {@link NullPointerException} or {@link ClassCastException} only later on.
075     * This limitation is known and explains why this constructor is for expert
076     * use only. The caller does have the responsibility to provided correct arguments.
077     * </p>
078     * @param tree inside/outside BSP tree representing the region
079     * @param tolerance tolerance below which points are considered identical
080     * @since 3.3
081     */
082    public PolyhedronsSet(final BSPTree<Euclidean3D> tree, final double tolerance) {
083        super(tree, tolerance);
084    }
085
086    /** Build a polyhedrons set from a Boundary REPresentation (B-rep) specified by sub-hyperplanes.
087     * <p>The boundary is provided as a collection of {@link
088     * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
089     * interior part of the region on its minus side and the exterior on
090     * its plus side.</p>
091     * <p>The boundary elements can be in any order, and can form
092     * several non-connected sets (like for example polyhedrons with holes
093     * or a set of disjoint polyhedrons considered as a whole). In
094     * fact, the elements do not even need to be connected together
095     * (their topological connections are not used here). However, if the
096     * boundary does not really separate an inside open from an outside
097     * open (open having here its topological meaning), then subsequent
098     * calls to the {@link Region#checkPoint(Point) checkPoint} method will
099     * 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}