View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math3.geometry.euclidean.threed;
18  
19  import java.awt.geom.AffineTransform;
20  import java.util.Collection;
21  
22  import org.apache.commons.math3.geometry.Vector;
23  import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
24  import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
25  import org.apache.commons.math3.geometry.euclidean.twod.SubLine;
26  import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
27  import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
28  import org.apache.commons.math3.geometry.partitioning.BSPTree;
29  import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
30  import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute;
31  import org.apache.commons.math3.geometry.partitioning.Hyperplane;
32  import org.apache.commons.math3.geometry.partitioning.Region;
33  import org.apache.commons.math3.geometry.partitioning.RegionFactory;
34  import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
35  import org.apache.commons.math3.geometry.partitioning.Transform;
36  import org.apache.commons.math3.util.FastMath;
37  
38  /** This class represents a 3D region: a set of polyhedrons.
39   * @version $Id: PolyhedronsSet.java 1416643 2012-12-03 19:37:14Z tn $
40   * @since 3.0
41   */
42  public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
43  
44      /** Build a polyhedrons set representing the whole real line.
45       */
46      public PolyhedronsSet() {
47          super();
48      }
49  
50      /** Build a polyhedrons set from a BSP tree.
51       * <p>The leaf nodes of the BSP tree <em>must</em> have a
52       * {@code Boolean} attribute representing the inside status of
53       * the corresponding cell (true for inside cells, false for outside
54       * cells). In order to avoid building too many small objects, it is
55       * recommended to use the predefined constants
56       * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
57       * @param tree inside/outside BSP tree representing the region
58       */
59      public PolyhedronsSet(final BSPTree<Euclidean3D> tree) {
60          super(tree);
61      }
62  
63      /** Build a polyhedrons set from a Boundary REPresentation (B-rep).
64       * <p>The boundary is provided as a collection of {@link
65       * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
66       * interior part of the region on its minus side and the exterior on
67       * its plus side.</p>
68       * <p>The boundary elements can be in any order, and can form
69       * several non-connected sets (like for example polyhedrons with holes
70       * or a set of disjoint polyhedrons considered as a whole). In
71       * fact, the elements do not even need to be connected together
72       * (their topological connections are not used here). However, if the
73       * boundary does not really separate an inside open from an outside
74       * open (open having here its topological meaning), then subsequent
75       * calls to the {@link Region#checkPoint(Vector) checkPoint} method will
76       * not be meaningful anymore.</p>
77       * <p>If the boundary is empty, the region will represent the whole
78       * space.</p>
79       * @param boundary collection of boundary elements, as a
80       * collection of {@link SubHyperplane SubHyperplane} objects
81       */
82      public PolyhedronsSet(final Collection<SubHyperplane<Euclidean3D>> boundary) {
83          super(boundary);
84      }
85  
86      /** Build a parallellepipedic box.
87       * @param xMin low bound along the x direction
88       * @param xMax high bound along the x direction
89       * @param yMin low bound along the y direction
90       * @param yMax high bound along the y direction
91       * @param zMin low bound along the z direction
92       * @param zMax high bound along the z direction
93       */
94      public PolyhedronsSet(final double xMin, final double xMax,
95                            final double yMin, final double yMax,
96                            final double zMin, final double zMax) {
97          super(buildBoundary(xMin, xMax, yMin, yMax, zMin, zMax));
98      }
99  
100     /** Build a parallellepipedic box boundary.
101      * @param xMin low bound along the x direction
102      * @param xMax high bound along the x direction
103      * @param yMin low bound along the y direction
104      * @param yMax high bound along the y direction
105      * @param zMin low bound along the z direction
106      * @param zMax high bound along the z direction
107      * @return boundary tree
108      */
109     private static BSPTree<Euclidean3D> buildBoundary(final double xMin, final double xMax,
110                                                       final double yMin, final double yMax,
111                                                       final double zMin, final double zMax) {
112         final Plane pxMin = new Plane(new Vector3D(xMin, 0,    0),   Vector3D.MINUS_I);
113         final Plane pxMax = new Plane(new Vector3D(xMax, 0,    0),   Vector3D.PLUS_I);
114         final Plane pyMin = new Plane(new Vector3D(0,    yMin, 0),   Vector3D.MINUS_J);
115         final Plane pyMax = new Plane(new Vector3D(0,    yMax, 0),   Vector3D.PLUS_J);
116         final Plane pzMin = new Plane(new Vector3D(0,    0,   zMin), Vector3D.MINUS_K);
117         final Plane pzMax = new Plane(new Vector3D(0,    0,   zMax), Vector3D.PLUS_K);
118         @SuppressWarnings("unchecked")
119         final Region<Euclidean3D> boundary =
120         new RegionFactory<Euclidean3D>().buildConvex(pxMin, pxMax, pyMin, pyMax, pzMin, pzMax);
121         return boundary.getTree(false);
122     }
123 
124     /** {@inheritDoc} */
125     @Override
126     public PolyhedronsSet buildNew(final BSPTree<Euclidean3D> tree) {
127         return new PolyhedronsSet(tree);
128     }
129 
130     /** {@inheritDoc} */
131     @Override
132     protected void computeGeometricalProperties() {
133 
134         // compute the contribution of all boundary facets
135         getTree(true).visit(new FacetsContributionVisitor());
136 
137         if (getSize() < 0) {
138             // the polyhedrons set as a finite outside
139             // surrounded by an infinite inside
140             setSize(Double.POSITIVE_INFINITY);
141             setBarycenter(Vector3D.NaN);
142         } else {
143             // the polyhedrons set is finite, apply the remaining scaling factors
144             setSize(getSize() / 3.0);
145             setBarycenter(new Vector3D(1.0 / (4 * getSize()), (Vector3D) getBarycenter()));
146         }
147 
148     }
149 
150     /** Visitor computing geometrical properties. */
151     private class FacetsContributionVisitor implements BSPTreeVisitor<Euclidean3D> {
152 
153         /** Simple constructor. */
154         public FacetsContributionVisitor() {
155             setSize(0);
156             setBarycenter(new Vector3D(0, 0, 0));
157         }
158 
159         /** {@inheritDoc} */
160         public Order visitOrder(final BSPTree<Euclidean3D> node) {
161             return Order.MINUS_SUB_PLUS;
162         }
163 
164         /** {@inheritDoc} */
165         public void visitInternalNode(final BSPTree<Euclidean3D> node) {
166             @SuppressWarnings("unchecked")
167             final BoundaryAttribute<Euclidean3D> attribute =
168                 (BoundaryAttribute<Euclidean3D>) node.getAttribute();
169             if (attribute.getPlusOutside() != null) {
170                 addContribution(attribute.getPlusOutside(), false);
171             }
172             if (attribute.getPlusInside() != null) {
173                 addContribution(attribute.getPlusInside(), true);
174             }
175         }
176 
177         /** {@inheritDoc} */
178         public void visitLeafNode(final BSPTree<Euclidean3D> node) {
179         }
180 
181         /** Add he contribution of a boundary facet.
182          * @param facet boundary facet
183          * @param reversed if true, the facet has the inside on its plus side
184          */
185         private void addContribution(final SubHyperplane<Euclidean3D> facet, final boolean reversed) {
186 
187             final Region<Euclidean2D> polygon = ((SubPlane) facet).getRemainingRegion();
188             final double area    = polygon.getSize();
189 
190             if (Double.isInfinite(area)) {
191                 setSize(Double.POSITIVE_INFINITY);
192                 setBarycenter(Vector3D.NaN);
193             } else {
194 
195                 final Plane    plane  = (Plane) facet.getHyperplane();
196                 final Vector3D facetB = plane.toSpace(polygon.getBarycenter());
197                 double   scaled = area * facetB.dotProduct(plane.getNormal());
198                 if (reversed) {
199                     scaled = -scaled;
200                 }
201 
202                 setSize(getSize() + scaled);
203                 setBarycenter(new Vector3D(1.0, (Vector3D) getBarycenter(), scaled, facetB));
204 
205             }
206 
207         }
208 
209     }
210 
211     /** Get the first sub-hyperplane crossed by a semi-infinite line.
212      * @param point start point of the part of the line considered
213      * @param line line to consider (contains point)
214      * @return the first sub-hyperplaned crossed by the line after the
215      * given point, or null if the line does not intersect any
216      * sub-hyperplaned
217      */
218     public SubHyperplane<Euclidean3D> firstIntersection(final Vector3D point, final Line line) {
219         return recurseFirstIntersection(getTree(true), point, line);
220     }
221 
222     /** Get the first sub-hyperplane crossed by a semi-infinite line.
223      * @param node current node
224      * @param point start point of the part of the line considered
225      * @param line line to consider (contains point)
226      * @return the first sub-hyperplaned crossed by the line after the
227      * given point, or null if the line does not intersect any
228      * sub-hyperplaned
229      */
230     private SubHyperplane<Euclidean3D> recurseFirstIntersection(final BSPTree<Euclidean3D> node,
231                                                                 final Vector3D point,
232                                                                 final Line line) {
233 
234         final SubHyperplane<Euclidean3D> cut = node.getCut();
235         if (cut == null) {
236             return null;
237         }
238         final BSPTree<Euclidean3D> minus = node.getMinus();
239         final BSPTree<Euclidean3D> plus  = node.getPlus();
240         final Plane               plane = (Plane) cut.getHyperplane();
241 
242         // establish search order
243         final double offset = plane.getOffset(point);
244         final boolean in    = FastMath.abs(offset) < 1.0e-10;
245         final BSPTree<Euclidean3D> near;
246         final BSPTree<Euclidean3D> far;
247         if (offset < 0) {
248             near = minus;
249             far  = plus;
250         } else {
251             near = plus;
252             far  = minus;
253         }
254 
255         if (in) {
256             // search in the cut hyperplane
257             final SubHyperplane<Euclidean3D> facet = boundaryFacet(point, node);
258             if (facet != null) {
259                 return facet;
260             }
261         }
262 
263         // search in the near branch
264         final SubHyperplane<Euclidean3D> crossed = recurseFirstIntersection(near, point, line);
265         if (crossed != null) {
266             return crossed;
267         }
268 
269         if (!in) {
270             // search in the cut hyperplane
271             final Vector3D hit3D = plane.intersection(line);
272             if (hit3D != null) {
273                 final SubHyperplane<Euclidean3D> facet = boundaryFacet(hit3D, node);
274                 if (facet != null) {
275                     return facet;
276                 }
277             }
278         }
279 
280         // search in the far branch
281         return recurseFirstIntersection(far, point, line);
282 
283     }
284 
285     /** Check if a point belongs to the boundary part of a node.
286      * @param point point to check
287      * @param node node containing the boundary facet to check
288      * @return the boundary facet this points belongs to (or null if it
289      * does not belong to any boundary facet)
290      */
291     private SubHyperplane<Euclidean3D> boundaryFacet(final Vector3D point,
292                                                      final BSPTree<Euclidean3D> node) {
293         final Vector2D point2D = ((Plane) node.getCut().getHyperplane()).toSubSpace(point);
294         @SuppressWarnings("unchecked")
295         final BoundaryAttribute<Euclidean3D> attribute =
296             (BoundaryAttribute<Euclidean3D>) node.getAttribute();
297         if ((attribute.getPlusOutside() != null) &&
298             (((SubPlane) attribute.getPlusOutside()).getRemainingRegion().checkPoint(point2D) == Location.INSIDE)) {
299             return attribute.getPlusOutside();
300         }
301         if ((attribute.getPlusInside() != null) &&
302             (((SubPlane) attribute.getPlusInside()).getRemainingRegion().checkPoint(point2D) == Location.INSIDE)) {
303             return attribute.getPlusInside();
304         }
305         return null;
306     }
307 
308     /** Rotate the region around the specified point.
309      * <p>The instance is not modified, a new instance is created.</p>
310      * @param center rotation center
311      * @param rotation vectorial rotation operator
312      * @return a new instance representing the rotated region
313      */
314     public PolyhedronsSet rotate(final Vector3D center, final Rotation rotation) {
315         return (PolyhedronsSet) applyTransform(new RotationTransform(center, rotation));
316     }
317 
318     /** 3D rotation as a Transform. */
319     private static class RotationTransform implements Transform<Euclidean3D, Euclidean2D> {
320 
321         /** Center point of the rotation. */
322         private Vector3D   center;
323 
324         /** Vectorial rotation. */
325         private Rotation   rotation;
326 
327         /** Cached original hyperplane. */
328         private Plane cachedOriginal;
329 
330         /** Cached 2D transform valid inside the cached original hyperplane. */
331         private Transform<Euclidean2D, Euclidean1D>  cachedTransform;
332 
333         /** Build a rotation transform.
334          * @param center center point of the rotation
335          * @param rotation vectorial rotation
336          */
337         public RotationTransform(final Vector3D center, final Rotation rotation) {
338             this.center   = center;
339             this.rotation = rotation;
340         }
341 
342         /** {@inheritDoc} */
343         public Vector3D apply(final Vector<Euclidean3D> point) {
344             final Vector3D delta = ((Vector3D) point).subtract(center);
345             return new Vector3D(1.0, center, 1.0, rotation.applyTo(delta));
346         }
347 
348         /** {@inheritDoc} */
349         public Plane apply(final Hyperplane<Euclidean3D> hyperplane) {
350             return ((Plane) hyperplane).rotate(center, rotation);
351         }
352 
353         /** {@inheritDoc} */
354         public SubHyperplane<Euclidean2D> apply(final SubHyperplane<Euclidean2D> sub,
355                                                 final Hyperplane<Euclidean3D> original,
356                                                 final Hyperplane<Euclidean3D> transformed) {
357             if (original != cachedOriginal) {
358                 // we have changed hyperplane, reset the in-hyperplane transform
359 
360                 final Plane    oPlane = (Plane) original;
361                 final Plane    tPlane = (Plane) transformed;
362                 final Vector3D p00    = oPlane.getOrigin();
363                 final Vector3D p10    = oPlane.toSpace(new Vector2D(1.0, 0.0));
364                 final Vector3D p01    = oPlane.toSpace(new Vector2D(0.0, 1.0));
365                 final Vector2D tP00   = tPlane.toSubSpace(apply(p00));
366                 final Vector2D tP10   = tPlane.toSubSpace(apply(p10));
367                 final Vector2D tP01   = tPlane.toSubSpace(apply(p01));
368                 final AffineTransform at =
369                     new AffineTransform(tP10.getX() - tP00.getX(), tP10.getY() - tP00.getY(),
370                                         tP01.getX() - tP00.getX(), tP01.getY() - tP00.getY(),
371                                         tP00.getX(), tP00.getY());
372 
373                 cachedOriginal  = (Plane) original;
374                 cachedTransform = org.apache.commons.math3.geometry.euclidean.twod.Line.getTransform(at);
375 
376             }
377             return ((SubLine) sub).applyTransform(cachedTransform);
378         }
379 
380     }
381 
382     /** Translate the region by the specified amount.
383      * <p>The instance is not modified, a new instance is created.</p>
384      * @param translation translation to apply
385      * @return a new instance representing the translated region
386      */
387     public PolyhedronsSet translate(final Vector3D translation) {
388         return (PolyhedronsSet) applyTransform(new TranslationTransform(translation));
389     }
390 
391     /** 3D translation as a transform. */
392     private static class TranslationTransform implements Transform<Euclidean3D, Euclidean2D> {
393 
394         /** Translation vector. */
395         private Vector3D   translation;
396 
397         /** Cached original hyperplane. */
398         private Plane cachedOriginal;
399 
400         /** Cached 2D transform valid inside the cached original hyperplane. */
401         private Transform<Euclidean2D, Euclidean1D>  cachedTransform;
402 
403         /** Build a translation transform.
404          * @param translation translation vector
405          */
406         public TranslationTransform(final Vector3D translation) {
407             this.translation = translation;
408         }
409 
410         /** {@inheritDoc} */
411         public Vector3D apply(final Vector<Euclidean3D> point) {
412             return new Vector3D(1.0, (Vector3D) point, 1.0, translation);
413         }
414 
415         /** {@inheritDoc} */
416         public Plane apply(final Hyperplane<Euclidean3D> hyperplane) {
417             return ((Plane) hyperplane).translate(translation);
418         }
419 
420         /** {@inheritDoc} */
421         public SubHyperplane<Euclidean2D> apply(final SubHyperplane<Euclidean2D> sub,
422                                                 final Hyperplane<Euclidean3D> original,
423                                                 final Hyperplane<Euclidean3D> transformed) {
424             if (original != cachedOriginal) {
425                 // we have changed hyperplane, reset the in-hyperplane transform
426 
427                 final Plane   oPlane = (Plane) original;
428                 final Plane   tPlane = (Plane) transformed;
429                 final Vector2D shift  = tPlane.toSubSpace(apply(oPlane.getOrigin()));
430                 final AffineTransform at =
431                     AffineTransform.getTranslateInstance(shift.getX(), shift.getY());
432 
433                 cachedOriginal  = (Plane) original;
434                 cachedTransform =
435                         org.apache.commons.math3.geometry.euclidean.twod.Line.getTransform(at);
436 
437             }
438 
439             return ((SubLine) sub).applyTransform(cachedTransform);
440 
441         }
442 
443     }
444 
445 }