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 */
017 package org.apache.commons.math3.geometry.euclidean.threed;
018
019 import java.awt.geom.AffineTransform;
020 import java.util.Collection;
021
022 import org.apache.commons.math3.geometry.Vector;
023 import org.apache.commons.math3.geometry.euclidean.oned.Euclidean1D;
024 import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
025 import org.apache.commons.math3.geometry.euclidean.twod.SubLine;
026 import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
027 import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
028 import org.apache.commons.math3.geometry.partitioning.BSPTree;
029 import org.apache.commons.math3.geometry.partitioning.BSPTreeVisitor;
030 import org.apache.commons.math3.geometry.partitioning.BoundaryAttribute;
031 import org.apache.commons.math3.geometry.partitioning.Hyperplane;
032 import org.apache.commons.math3.geometry.partitioning.Region;
033 import org.apache.commons.math3.geometry.partitioning.RegionFactory;
034 import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
035 import org.apache.commons.math3.geometry.partitioning.Transform;
036 import org.apache.commons.math3.util.FastMath;
037
038 /** This class represents a 3D region: a set of polyhedrons.
039 * @version $Id: PolyhedronsSet.java 1416643 2012-12-03 19:37:14Z tn $
040 * @since 3.0
041 */
042 public class PolyhedronsSet extends AbstractRegion<Euclidean3D, Euclidean2D> {
043
044 /** Build a polyhedrons set representing the whole real line.
045 */
046 public PolyhedronsSet() {
047 super();
048 }
049
050 /** Build a polyhedrons set from a BSP tree.
051 * <p>The leaf nodes of the BSP tree <em>must</em> have a
052 * {@code Boolean} attribute representing the inside status of
053 * the corresponding cell (true for inside cells, false for outside
054 * cells). In order to avoid building too many small objects, it is
055 * recommended to use the predefined constants
056 * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
057 * @param tree inside/outside BSP tree representing the region
058 */
059 public PolyhedronsSet(final BSPTree<Euclidean3D> tree) {
060 super(tree);
061 }
062
063 /** Build a polyhedrons set from a Boundary REPresentation (B-rep).
064 * <p>The boundary is provided as a collection of {@link
065 * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
066 * interior part of the region on its minus side and the exterior on
067 * its plus side.</p>
068 * <p>The boundary elements can be in any order, and can form
069 * several non-connected sets (like for example polyhedrons with holes
070 * or a set of disjoint polyhedrons considered as a whole). In
071 * fact, the elements do not even need to be connected together
072 * (their topological connections are not used here). However, if the
073 * boundary does not really separate an inside open from an outside
074 * open (open having here its topological meaning), then subsequent
075 * calls to the {@link Region#checkPoint(Vector) checkPoint} method will
076 * not be meaningful anymore.</p>
077 * <p>If the boundary is empty, the region will represent the whole
078 * space.</p>
079 * @param boundary collection of boundary elements, as a
080 * collection of {@link SubHyperplane SubHyperplane} objects
081 */
082 public PolyhedronsSet(final Collection<SubHyperplane<Euclidean3D>> boundary) {
083 super(boundary);
084 }
085
086 /** Build a parallellepipedic box.
087 * @param xMin low bound along the x direction
088 * @param xMax high bound along the x direction
089 * @param yMin low bound along the y direction
090 * @param yMax high bound along the y direction
091 * @param zMin low bound along the z direction
092 * @param zMax high bound along the z direction
093 */
094 public PolyhedronsSet(final double xMin, final double xMax,
095 final double yMin, final double yMax,
096 final double zMin, final double zMax) {
097 super(buildBoundary(xMin, xMax, yMin, yMax, zMin, zMax));
098 }
099
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 }