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.geometry.euclidean.threed;
18  
19  import java.text.MessageFormat;
20  import java.util.ArrayList;
21  import java.util.Arrays;
22  import java.util.Collection;
23  import java.util.List;
24  import java.util.function.BiFunction;
25  
26  import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
27  import org.apache.commons.geometry.core.partitioning.Split;
28  import org.apache.commons.geometry.core.partitioning.SplitLocation;
29  import org.apache.commons.geometry.euclidean.internal.EuclideanUtils;
30  import org.apache.commons.geometry.euclidean.threed.line.Line3D;
31  import org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D;
32  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
33  import org.apache.commons.geometry.euclidean.twod.Line;
34  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
35  import org.apache.commons.geometry.euclidean.twod.Lines;
36  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
37  import org.apache.commons.geometry.euclidean.twod.Vector2D;
38  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
39  import org.apache.commons.numbers.core.Precision;
40  
41  /** Class containing factory methods for constructing {@link Plane} and {@link PlaneSubset} instances.
42   */
43  public final class Planes {
44  
45      /** Utility class; no instantiation. */
46      private Planes() {
47      }
48  
49      /** Build a plane from a point and two (on plane) vectors.
50       * @param p the provided point (on plane)
51       * @param u u vector (on plane)
52       * @param v v vector (on plane)
53       * @param precision precision context used to compare floating point values
54       * @return a new plane
55       * @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
56       */
57      public static EmbeddingPlane fromPointAndPlaneVectors(final Vector3D p, final Vector3D u, final Vector3D v,
58              final Precision.DoubleEquivalence precision) {
59          final Vector3D.Unit uNorm = u.normalize();
60          final Vector3D.Unit vNorm = uNorm.orthogonal(v);
61          final Vector3D.Unit wNorm = uNorm.cross(vNorm).normalize();
62          final double originOffset = -p.dot(wNorm);
63  
64          return new EmbeddingPlane(uNorm, vNorm, wNorm, originOffset, precision);
65      }
66  
67      /** Build a plane from a normal.
68       * Chooses origin as point on plane.
69       * @param normal normal direction to the plane
70       * @param precision precision context used to compare floating point values
71       * @return a new plane
72       * @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
73       */
74      public static Plane fromNormal(final Vector3D normal, final Precision.DoubleEquivalence precision) {
75          return fromPointAndNormal(Vector3D.ZERO, normal, precision);
76      }
77  
78      /** Build a plane from a point and a normal.
79       *
80       * @param p point belonging to the plane
81       * @param normal normal direction to the plane
82       * @param precision precision context used to compare floating point values
83       * @return a new plane
84       * @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
85       */
86      public static Plane fromPointAndNormal(final Vector3D p, final Vector3D normal,
87              final Precision.DoubleEquivalence precision) {
88          final Vector3D.Unit unitNormal = normal.normalize();
89          final double originOffset = -p.dot(unitNormal);
90  
91          return new Plane(unitNormal, originOffset, precision);
92      }
93  
94      /** Build a plane from three points.
95       * <p>
96       * The plane is oriented in the direction of {@code (p2-p1) ^ (p3-p1)}
97       * </p>
98       *
99       * @param p1 first point belonging to the plane
100      * @param p2 second point belonging to the plane
101      * @param p3 third point belonging to the plane
102      * @param precision precision context used to compare floating point values
103      * @return a new plane
104      * @throws IllegalArgumentException if the points do not define a unique plane
105      */
106     public static Plane fromPoints(final Vector3D p1, final Vector3D p2, final Vector3D p3,
107             final Precision.DoubleEquivalence precision) {
108         return fromPoints(Arrays.asList(p1, p2, p3), precision);
109     }
110 
111     /** Construct a plane from a collection of points lying on the plane. The plane orientation is
112      * determined by the overall orientation of the point sequence. For example, if the points wind
113      * around the z-axis in a counter-clockwise direction, then the plane normal will point up the
114      * +z axis. If the points wind in the opposite direction, then the plane normal will point down
115      * the -z axis. The {@code u} vector for the plane is set to the first non-zero vector between
116      * points in the sequence (ie, the first direction in the path).
117      *
118      * @param pts collection of sequenced points lying on the plane
119      * @param precision precision context used to compare floating point values
120      * @return a new plane containing the given points
121      * @throws IllegalArgumentException if the given collection does not contain at least 3 points or the
122      *      points do not define a unique plane
123      */
124     public static Plane fromPoints(final Collection<Vector3D> pts, final Precision.DoubleEquivalence precision) {
125         return new PlaneBuilder(pts, precision).build();
126     }
127 
128     /** Create a new plane subset from a plane and an embedded convex subspace area.
129      * @param plane embedding plane for the area
130      * @param area area embedded in the plane
131      * @return a new convex sub plane instance
132      */
133     public static PlaneConvexSubset subsetFromConvexArea(final EmbeddingPlane plane, final ConvexArea area) {
134         if (area.isFinite()) {
135             // prefer a vertex-based representation for finite areas
136             final List<Vector3D> vertices = plane.toSpace(area.getVertices());
137             return fromConvexPlanarVertices(plane, vertices);
138         }
139 
140         return new EmbeddedAreaPlaneConvexSubset(plane, area);
141     }
142 
143     /** Create a new convex polygon from the given sequence of vertices. The vertices must define a unique
144      * plane, meaning that at least 3 unique vertices must be given. The given sequence is assumed to be closed,
145      * ie that an edge exists between the last vertex and the first.
146      * @param pts collection of points defining the convex polygon
147      * @param precision precision context used to compare floating point values
148      * @return a new convex polygon defined by the given sequence of vertices
149      * @throws IllegalArgumentException if fewer than 3 vertices are given or the vertices do not define a
150      *       unique plane
151      * @see #fromPoints(Collection, Precision.DoubleEquivalence)
152      */
153     public static ConvexPolygon3D convexPolygonFromVertices(final Collection<Vector3D> pts,
154             final Precision.DoubleEquivalence precision) {
155         final List<Vector3D> vertices = new ArrayList<>(pts.size());
156         final Plane plane = new PlaneBuilder(pts, precision).buildForConvexPolygon(vertices);
157 
158         // make sure that the first point is not repeated at the end
159         final Vector3D firstPt = vertices.get(0);
160         final Vector3D lastPt = vertices.get(vertices.size() - 1);
161         if (firstPt.eq(lastPt, precision)) {
162             vertices.remove(vertices.size() - 1);
163         }
164 
165         if (vertices.size() == EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
166             return new SimpleTriangle3D(plane, vertices.get(0), vertices.get(1), vertices.get(2));
167         }
168         return new VertexListConvexPolygon3D(plane, vertices);
169     }
170 
171     /** Construct a triangle from three vertices. The triangle plane is oriented such that the points
172      * are arranged in a counter-clockwise order when looking down the plane normal.
173      * @param p1 first vertex
174      * @param p2 second vertex
175      * @param p3 third vertex
176      * @param precision precision context used for floating point comparisons
177      * @return a triangle constructed from the three vertices
178      * @throws IllegalArgumentException if the points do not define a unique plane
179      */
180     public static Triangle3D triangleFromVertices(final Vector3D p1, final Vector3D p2, final Vector3D p3,
181             final Precision.DoubleEquivalence precision) {
182         final Plane plane = fromPoints(p1, p2, p3, precision);
183         return new SimpleTriangle3D(plane, p1, p2, p3);
184     }
185 
186     /** Construct a list of {@link Triangle3D} instances from a set of vertices and arrays of face indices.
187      * For example, the following code constructs a list of triangles forming a square pyramid.
188      * <pre>
189      * Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
190      *
191      * Vector3D[] vertices = {
192      *      Vector3D.ZERO,
193      *      Vector3D.of(1, 0, 0),
194      *      Vector3D.of(1, 1, 0),
195      *      Vector3D.of(0, 1, 0),
196      *      Vector3D.of(0.5, 0.5, 4)
197      * };
198      *
199      * int[][] faceIndices = {
200      *      {0, 2, 1},
201      *      {0, 3, 2},
202      *      {0, 1, 4},
203      *      {1, 2, 4},
204      *      {2, 3, 4},
205      *      {3, 0, 4}
206      * };
207      *
208      * List&lt;Triangle3D&gt; triangles = Planes.indexedTriangles(vertices, faceIndices, TEST_PRECISION);
209      * </pre>
210      * @param vertices vertices available for use in triangle construction
211      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
212      *      3 index values into {@code vertices}, defining the 3 vertices that will be used to construct the
213      *      triangle
214      * @param precision precision context used for floating point comparisons
215      * @return a list of triangles constructed from the set of vertices and face indices
216      * @throws IllegalArgumentException if any face index array does not contain exactly 3 elements or a set
217      *      of 3 vertices do not define a plane
218      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
219      */
220     public static List<Triangle3D> indexedTriangles(final Vector3D[] vertices, final int[][] faceIndices,
221             final Precision.DoubleEquivalence precision) {
222         return indexedTriangles(Arrays.asList(vertices), faceIndices, precision);
223     }
224 
225     /** Construct a list of {@link Triangle3D} instances from a set of vertices and arrays of face indices.
226      * @param vertices vertices available for use in triangle construction
227      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
228      *      3 index values into {@code vertices}, defining the 3 vertices that will be used to construct the
229      *      triangle
230      * @param precision precision context used for floating point comparisons
231      * @return a list of triangles constructed from the set of vertices and face indices
232      * @throws IllegalArgumentException if any face index array does not contain exactly 3 elements or a set
233      *      of 3 vertices do not define a plane
234      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
235      * @see #indexedTriangles(Vector3D[], int[][], Precision.DoubleEquivalence)
236      */
237     public static List<Triangle3D> indexedTriangles(final List<? extends Vector3D> vertices, final int[][] faceIndices,
238             final Precision.DoubleEquivalence precision) {
239 
240         final int numFaces = faceIndices.length;
241         final List<Triangle3D> triangles = new ArrayList<>(numFaces);
242 
243         int[] face;
244         for (int i = 0; i < numFaces; ++i) {
245             face = faceIndices[i];
246             if (face.length != EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
247                 throw new IllegalArgumentException(MessageFormat.format(
248                         "Invalid number of vertex indices for face at index {0}: expected {1} but found {2}",
249                         i, EuclideanUtils.TRIANGLE_VERTEX_COUNT, face.length));
250             }
251 
252             triangles.add(triangleFromVertices(
253                         vertices.get(face[0]),
254                         vertices.get(face[1]),
255                         vertices.get(face[2]),
256                         precision
257                     ));
258         }
259 
260         return triangles;
261     }
262 
263     /** Construct a list of {@link ConvexPolygon3D} instances from a set of vertices and arrays of face indices. Each
264      * face must contain at least 3 vertices but the number of vertices per face does not need to be constant.
265      * For example, the following code constructs a list of convex polygons forming a square pyramid.
266      * Note that the first face (the pyramid base) uses a different number of vertices than the other faces.
267      * <pre>
268      * Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
269      *
270      * Vector3D[] vertices = {
271      *      Vector3D.ZERO,
272      *      Vector3D.of(1, 0, 0),
273      *      Vector3D.of(1, 1, 0),
274      *      Vector3D.of(0, 1, 0),
275      *      Vector3D.of(0.5, 0.5, 4)
276      * };
277      *
278      * int[][] faceIndices = {
279      *      {0, 3, 2, 1}, // square base
280      *      {0, 1, 4},
281      *      {1, 2, 4},
282      *      {2, 3, 4},
283      *      {3, 0, 4}
284      * };
285      *
286      * List&lt;ConvexPolygon3D&gt; polygons = Planes.indexedConvexPolygons(vertices, faceIndices, precision);
287      * </pre>
288      * @param vertices vertices available for use in convex polygon construction
289      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
290      *      at least 3 index values into {@code vertices}, defining the vertices that will be used to construct the
291      *      convex polygon
292      * @param precision precision context used for floating point comparisons
293      * @return a list of convex polygons constructed from the set of vertices and face indices
294      * @throws IllegalArgumentException if any face index array does not contain at least 3 elements or a set
295      *      of vertices do not define a planar convex polygon
296      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
297      */
298     public static List<ConvexPolygon3D> indexedConvexPolygons(final Vector3D[] vertices, final int[][] faceIndices,
299             final Precision.DoubleEquivalence precision) {
300         return indexedConvexPolygons(Arrays.asList(vertices), faceIndices, precision);
301     }
302 
303     /** Construct a list of {@link ConvexPolygon3D} instances from a set of vertices and arrays of face indices. Each
304      * face must contain at least 3 vertices but the number of vertices per face does not need to be constant.
305      * @param vertices vertices available for use in convex polygon construction
306      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
307      *      at least 3 index values into {@code vertices}, defining the vertices that will be used to construct the
308      *      convex polygon
309      * @param precision precision context used for floating point comparisons
310      * @return a list of convex polygons constructed from the set of vertices and face indices
311      * @throws IllegalArgumentException if any face index array does not contain at least 3 elements or a set
312      *      of vertices do not define a planar convex polygon
313      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
314      * @see #indexedConvexPolygons(Vector3D[], int[][], Precision.DoubleEquivalence)
315      */
316     public static List<ConvexPolygon3D> indexedConvexPolygons(final List<? extends Vector3D> vertices,
317             final int[][] faceIndices, final Precision.DoubleEquivalence precision) {
318         final int numFaces = faceIndices.length;
319         final List<ConvexPolygon3D> polygons = new ArrayList<>(numFaces);
320         final List<Vector3D> faceVertices = new ArrayList<>();
321 
322         int[] face;
323         for (int i = 0; i < numFaces; ++i) {
324             face = faceIndices[i];
325             if (face.length < EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
326                 throw new IllegalArgumentException(MessageFormat.format(
327                         "Invalid number of vertex indices for face at index {0}: required at least {1} but found {2}",
328                         i, EuclideanUtils.TRIANGLE_VERTEX_COUNT, face.length));
329             }
330 
331             for (final int vertexIndex : face) {
332                 faceVertices.add(vertices.get(vertexIndex));
333             }
334 
335             polygons.add(convexPolygonFromVertices(
336                         faceVertices,
337                         precision
338                     ));
339 
340             faceVertices.clear();
341         }
342 
343         return polygons;
344     }
345 
346     /** Get the boundaries of a 3D region created by extruding a polygon defined by a list of vertices. The ends
347      * ("top" and "bottom") of the extruded 3D region are flat while the sides follow the boundaries of the original
348      * 2D region.
349      * @param vertices vertices forming the 2D polygon to extrude
350      * @param plane plane to extrude the 2D polygon from
351      * @param extrusionVector vector to extrude the polygon vertices through
352      * @param precision precision context used to construct the 3D region boundaries
353      * @return the boundaries of the extruded 3D region
354      * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
355      * @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
356      *      given plane and extrusion vector. This occurs when the extrusion vector has zero length
357      *      or is orthogonal to the plane normal
358      * @see LinePath#fromVertexLoop(Collection, Precision.DoubleEquivalence)
359      * @see #extrude(LinePath, EmbeddingPlane, Vector3D, Precision.DoubleEquivalence)
360      */
361     public static List<PlaneConvexSubset> extrudeVertexLoop(final List<Vector2D> vertices,
362             final EmbeddingPlane plane, final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
363         final LinePath path = LinePath.fromVertexLoop(vertices, precision);
364         return extrude(path, plane, extrusionVector, precision);
365     }
366 
367     /** Get the boundaries of the 3D region created by extruding a 2D line path. The ends ("top" and "bottom") of
368      * the extruded 3D region are flat while the sides follow the boundaries of the original 2D region. The path is
369      * converted to a BSP tree before extrusion.
370      * @param path path to extrude
371      * @param plane plane to extrude the path from
372      * @param extrusionVector vector to extrude the polygon points through
373      * @param precision precision precision context used to construct the 3D region boundaries
374      * @return the boundaries of the extruded 3D region
375      * @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
376      *      given plane and extrusion vector. This occurs when the extrusion vector has zero length
377      *      or is orthogonal to the plane normal
378      * @see #extrude(RegionBSPTree2D, EmbeddingPlane, Vector3D, Precision.DoubleEquivalence)
379      */
380     public static List<PlaneConvexSubset> extrude(final LinePath path, final EmbeddingPlane plane,
381             final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
382         return extrude(path.toTree(), plane, extrusionVector, precision);
383     }
384 
385     /** Get the boundaries of the 3D region created by extruding a 2D region. The ends ("top" and "bottom") of
386      * the extruded 3D region are flat while the sides follow the boundaries of the original 2D region.
387      * @param region region to extrude
388      * @param plane plane to extrude the region from
389      * @param extrusionVector vector to extrude the region points through
390      * @param precision precision precision context used to construct the 3D region boundaries
391      * @return the boundaries of the extruded 3D region
392      * @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
393      *      given plane and extrusion vector. This occurs when the extrusion vector has zero length
394      *      or is orthogonal to the plane normal
395      */
396     public static List<PlaneConvexSubset> extrude(final RegionBSPTree2D region, final EmbeddingPlane plane,
397             final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
398         return new PlaneRegionExtruder(plane, extrusionVector, precision).extrude(region);
399     }
400 
401     /** Get the unique intersection of the plane subset with the given line. Null is
402      * returned if no unique intersection point exists (ie, the line and plane are
403      * parallel or coincident) or the line does not intersect the plane subset.
404      * @param planeSubset plane subset to intersect with
405      * @param line line to intersect with this plane subset
406      * @return the unique intersection point between the line and this plane subset
407      *      or null if no such point exists.
408      */
409     static Vector3D intersection(final PlaneSubset planeSubset, final Line3D line) {
410         final Vector3D pt = planeSubset.getPlane().intersection(line);
411         return (pt != null && planeSubset.contains(pt)) ? pt : null;
412     }
413 
414     /** Get the unique intersection of the plane subset with the given line subset. Null
415      * is returned if the underlying line and plane do not have a unique intersection
416      * point (ie, they are parallel or coincident) or the intersection point is unique
417      * but is not contained in both the line subset and plane subset.
418      * @param planeSubset plane subset to intersect with
419      * @param lineSubset line subset to intersect with
420      * @return the unique intersection point between this plane subset and the argument or
421      *      null if no such point exists.
422      */
423     static Vector3D intersection(final PlaneSubset planeSubset, final LineConvexSubset3D lineSubset) {
424         final Vector3D pt = intersection(planeSubset, lineSubset.getLine());
425         return (pt != null && lineSubset.contains(pt)) ? pt : null;
426     }
427 
428     /** Validate that the actual plane contains the same points as the expected plane, throwing an exception if not.
429      * The subspace orientations of embedding planes are not considered.
430      * @param expected the expected plane
431      * @param actual the actual plane
432      * @throws IllegalArgumentException if the actual plane is not equivalent to the expected plane
433      */
434     static void validatePlanesEquivalent(final Plane expected, final Plane actual) {
435         if (!expected.eq(actual, expected.getPrecision())) {
436             throw new IllegalArgumentException("Arguments do not represent the same plane. Expected " +
437                     expected + " but was " + actual + ".");
438         }
439     }
440 
441     /** Generic split method that uses performs the split using the subspace region of the plane subset.
442      * @param splitter splitting hyperplane
443      * @param subset the plane subset being split
444      * @param factory function used to create new plane subset instances
445      * @param <T> Plane subset implementation type
446      * @return the result of the split operation
447      */
448     static <T extends PlaneSubset> Split<T> subspaceSplit(final Plane splitter, final T subset,
449             final BiFunction<? super EmbeddingPlane, ? super HyperplaneBoundedRegion<Vector2D>, T> factory) {
450 
451         final EmbeddingPlane thisPlane = subset.getPlane().getEmbedding();
452 
453         final Line3D intersection = thisPlane.intersection(splitter);
454         if (intersection == null) {
455             return getNonIntersectingSplitResult(splitter, subset);
456         } else {
457             final EmbeddingPlane embeddingPlane = subset.getPlane().getEmbedding();
458 
459             // the lines intersect; split the subregion
460             final Vector3D intersectionOrigin = intersection.getOrigin();
461             final Vector2D subspaceP1 = embeddingPlane.toSubspace(intersectionOrigin);
462             final Vector2D subspaceP2 = embeddingPlane.toSubspace(intersectionOrigin.add(intersection.getDirection()));
463 
464             final Line subspaceSplitter = Lines.fromPoints(subspaceP1, subspaceP2, thisPlane.getPrecision());
465 
466             final Split<? extends HyperplaneBoundedRegion<Vector2D>> split =
467                     subset.getEmbedded().getSubspaceRegion().split(subspaceSplitter);
468             final SplitLocation subspaceSplitLoc = split.getLocation();
469 
470             if (SplitLocation.MINUS == subspaceSplitLoc) {
471                 return new Split<>(subset, null);
472             } else if (SplitLocation.PLUS == subspaceSplitLoc) {
473                 return new Split<>(null, subset);
474             }
475 
476             final T minus = (split.getMinus() != null) ? factory.apply(thisPlane, split.getMinus()) : null;
477             final T plus = (split.getPlus() != null) ? factory.apply(thisPlane, split.getPlus()) : null;
478 
479             return new Split<>(minus, plus);
480         }
481     }
482 
483     /** Get a split result for cases where the splitting plane and the plane containing the subset being split
484      * do not intersect. Callers are responsible for ensuring that the planes involved do not actually intersect.
485      * @param <T> Plane subset implementation type
486      * @param splitter plane performing the splitting
487      * @param subset subset being split
488      * @return the split result for the non-intersecting split
489      */
490     private static <T extends PlaneSubset> Split<T> getNonIntersectingSplitResult(
491             final Plane splitter, final T subset) {
492         final Plane plane = subset.getPlane();
493 
494         final double offset = splitter.offset(plane);
495         final int comp = plane.getPrecision().compare(offset, 0.0);
496 
497         if (comp < 0) {
498             return new Split<>(subset, null);
499         } else if (comp > 0) {
500             return new Split<>(null, subset);
501         } else {
502             return new Split<>(null, null);
503         }
504     }
505 
506     /** Construct a convex polygon 3D from a plane and a list of vertices lying in the plane. Callers are
507      * responsible for ensuring that the vertices lie in the plane and define a convex polygon.
508      * @param plane the plane containing the convex polygon
509      * @param vertices vertices defining the closed, convex polygon. The must must contain at least 3 unique
510      *      vertices and should not include the start vertex at the end of the list.
511      * @return a new convex polygon instance
512      * @throws IllegalArgumentException if the size of {@code vertices} if less than 3
513      */
514     static ConvexPolygon3D fromConvexPlanarVertices(final Plane plane, final List<Vector3D> vertices) {
515         final int size = vertices.size();
516 
517         if (size == EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
518             return new SimpleTriangle3D(plane, vertices.get(0), vertices.get(1), vertices.get(2));
519         }
520 
521         return new VertexListConvexPolygon3D(plane, vertices);
522     }
523 
524     /** Convert a convex polygon defined by a plane and list of points into a triangle fan.
525      * @param plane plane containing the convex polygon
526      * @param vertices vertices defining the convex polygon
527      * @return a triangle fan representing the same area as the convex polygon
528      * @throws IllegalArgumentException if fewer than 3 vertices are given
529      */
530     static List<Triangle3D> convexPolygonToTriangleFan(final Plane plane, final List<Vector3D> vertices) {
531         return EuclideanUtils.convexPolygonToTriangleFan(vertices,
532                 tri -> new SimpleTriangle3D(plane, tri.get(0), tri.get(1), tri.get(2)));
533     }
534 
535     /** Internal helper class used to construct planes from sequences of points. Instances can be also be
536      * configured to collect lists of unique points found during plane construction and validate that the
537      * defined region is convex.
538      */
539     private static final class PlaneBuilder {
540 
541         /** The point sequence to build a plane for. */
542         private final Collection<? extends Vector3D> pts;
543 
544         /** Precision context used for floating point comparisons. */
545         private final Precision.DoubleEquivalence precision;
546 
547         /** The start point from the point sequence. */
548         private Vector3D startPt;
549 
550         /** The previous point from the point sequence. */
551         private Vector3D prevPt;
552 
553         /** The previous vector from the point sequence, preceding from the {@code startPt} to {@code prevPt}. */
554         private Vector3D prevVector;
555 
556         /** The computed {@code normal} vector for the plane. */
557         private Vector3D.Unit normal;
558 
559         /** The x component of the sum of all cross products from adjacent vectors in the point sequence. */
560         private double crossSumX;
561 
562         /** The y component of the sum of all cross products from adjacent vectors in the point sequence. */
563         private double crossSumY;
564 
565         /** The z component of the sum of all cross products from adjacent vectors in the point sequence. */
566         private double crossSumZ;
567 
568         /** If true, an exception will be thrown if the point sequence is discovered to be non-convex. */
569         private boolean requireConvex;
570 
571         /** List that unique vertices discovered in the input sequence will be added to. */
572         private List<? super Vector3D> uniqueVertexOutput;
573 
574         /** Construct a new build instance for the given point sequence and precision context.
575          * @param pts point sequence
576          * @param precision precision context used to perform floating point comparisons
577          */
578         PlaneBuilder(final Collection<? extends Vector3D> pts, final Precision.DoubleEquivalence precision) {
579             this.pts = pts;
580             this.precision = precision;
581         }
582 
583         /** Build a plane from the configured point sequence.
584          * @return a plane built from the configured point sequence
585          * @throws IllegalArgumentException if the points do not define a plane
586          */
587         Plane build() {
588             if (pts.size() < EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
589                 throw nonPlanar();
590             }
591 
592             pts.forEach(this::processPoint);
593 
594             return createPlane();
595         }
596 
597         /** Build a plane from the configured point sequence, validating that the points form a convex region
598          * and adding all discovered unique points to the given list.
599          * @param vertexOutput list that unique points discovered in the point sequence will be added to
600          * @return a plane created from the configured point sequence
601          * @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
602          *      flag is true and the points do not define a convex area
603          */
604         Plane buildForConvexPolygon(final List<? super Vector3D> vertexOutput) {
605             this.requireConvex = true;
606             this.uniqueVertexOutput = vertexOutput;
607 
608             return build();
609         }
610 
611         /** Process a point from the point sequence.
612          * @param pt
613          * @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
614          *      flag is true and the points do not define a convex area
615          */
616         private void processPoint(final Vector3D pt) {
617             if (prevPt == null) {
618                 startPt = pt;
619                 prevPt = pt;
620 
621                 if (uniqueVertexOutput != null) {
622                     uniqueVertexOutput.add(pt);
623                 }
624 
625             } else if (!prevPt.eq(pt, precision)) { // skip duplicate points
626                 final Vector3D vec = startPt.vectorTo(pt);
627 
628                 if (prevVector != null) {
629                     processCrossProduct(prevVector.cross(vec));
630                 }
631 
632                 if (uniqueVertexOutput != null) {
633                     uniqueVertexOutput.add(pt);
634                 }
635 
636                 prevPt = pt;
637                 prevVector = vec;
638             }
639         }
640 
641         /** Process the computed cross product of two vectors from the input point sequence. The vectors
642          * start at the first point in the sequence and point to adjacent points later in the sequence.
643          * @param cross the cross product of two vectors from the input point sequence
644          * @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
645          *      flag is true and the points do not define a convex area
646          */
647         private void processCrossProduct(final Vector3D cross) {
648             crossSumX += cross.getX();
649             crossSumY += cross.getY();
650             crossSumZ += cross.getZ();
651 
652             final double crossNorm = cross.norm();
653 
654             if (!precision.eqZero(crossNorm)) {
655                 // the cross product has non-zero magnitude
656                 if (normal == null) {
657                     // save the first non-zero cross product as our normal
658                     normal = cross.normalize();
659                 } else {
660                     final double crossDot = normal.dot(cross) / crossNorm;
661 
662                     // check non-planar before non-convex since the former is a more general type
663                     // of issue
664                     if (!precision.eq(1.0, Math.abs(crossDot))) {
665                         throw nonPlanar();
666                     } else if (requireConvex && crossDot < 0) {
667                         throw nonConvex();
668                     }
669                 }
670             }
671         }
672 
673         /** Construct the plane instance using the value gathered during point processing.
674          * @return the created plane instance
675          * @throws IllegalArgumentException if the point do not define a plane
676          */
677         private Plane createPlane() {
678             if (normal == null) {
679                 throw nonPlanar();
680             }
681 
682             // flip the normal if needed to match the overall orientation of the points
683             if (normal.dot(Vector3D.of(crossSumX, crossSumY, crossSumZ)) < 0) {
684                 normal = normal.negate();
685             }
686 
687             // construct the plane
688             final double originOffset = -startPt.dot(normal);
689 
690             return new Plane(normal, originOffset, precision);
691         }
692 
693         /** Return an exception with a message stating that the points given to this builder do not
694          * define a plane.
695          * @return an exception stating that the points do not define a plane
696          */
697         private IllegalArgumentException nonPlanar() {
698             return new IllegalArgumentException("Points do not define a plane: " + pts);
699         }
700 
701         /** Return an exception with a message stating that the points given to this builder do not
702          * define a convex region.
703          * @return an exception stating that the points do not define a plane
704          */
705         private IllegalArgumentException nonConvex() {
706             return new IllegalArgumentException("Points do not define a convex region: " + pts);
707         }
708     }
709 
710     /** Class designed to create 3D regions by taking a 2D region and extruding from a base plane
711      * through an extrusion vector. The ends ("top" and "bottom") of the extruded 3D region are flat
712      * while the sides follow the boundaries of the original 2D region.
713      */
714     private static final class PlaneRegionExtruder {
715         /** Base plane to extrude from. */
716         private final EmbeddingPlane basePlane;
717 
718         /** Vector to extrude along; the extruded plane is translated from the base plane by this amount. */
719         private final Vector3D extrusionVector;
720 
721         /** True if the extrusion vector points to the plus side of the base plane. */
722         private final boolean extrudingOnPlusSide;
723 
724         /** Precision context used to create boundaries. */
725         private final Precision.DoubleEquivalence precision;
726 
727         /** Construct a new instance that performs extrusions from {@code basePlane} along {@code extrusionVector}.
728          * @param basePlane base plane to extrude from
729          * @param extrusionVector vector to extrude along
730          * @param precision precision context used to construct boundaries
731          * @throws IllegalArgumentException if the given extrusion vector and plane produce regions
732          *      of zero size
733          */
734         PlaneRegionExtruder(final EmbeddingPlane basePlane, final Vector3D extrusionVector,
735                 final Precision.DoubleEquivalence precision) {
736 
737             this.basePlane = basePlane;
738 
739             // Extruded plane; this forms the end of the 3D region opposite the base plane.
740             final EmbeddingPlane extrudedPlane = basePlane.translate(extrusionVector);
741 
742             if (basePlane.contains(extrudedPlane)) {
743                 throw new IllegalArgumentException(
744                         "Extrusion vector produces regions of zero size: extrusionVector= " +
745                                 extrusionVector + ",  plane= " + basePlane);
746             }
747 
748             this.extrusionVector = extrusionVector;
749             this.extrudingOnPlusSide = basePlane.getNormal().dot(extrusionVector) > 0;
750 
751             this.precision = precision;
752         }
753 
754         /** Extrude the given 2D BSP tree using the configured base plane and extrusion vector.
755          * @param subspaceRegion region to extrude
756          * @return the boundaries of the extruded region
757          */
758         public List<PlaneConvexSubset> extrude(final RegionBSPTree2D subspaceRegion) {
759             final List<PlaneConvexSubset> extrudedBoundaries = new ArrayList<>();
760 
761             // add the boundaries
762             addEnds(subspaceRegion, extrudedBoundaries);
763             addSides(subspaceRegion, extrudedBoundaries);
764 
765             return extrudedBoundaries;
766         }
767 
768         /** Add the end ("top" and "bottom") of the extruded subspace region to the result list.
769          * @param subspaceRegion subspace region being extruded.
770          * @param result list to add the boundary results to
771          */
772         private void addEnds(final RegionBSPTree2D subspaceRegion, final List<? super PlaneConvexSubset> result) {
773             // add the base boundaries
774             final List<ConvexArea> baseAreas = subspaceRegion.toConvex();
775 
776             final List<PlaneConvexSubset> baseList = new ArrayList<>(baseAreas.size());
777             final List<PlaneConvexSubset> extrudedList = new ArrayList<>(baseAreas.size());
778 
779             final AffineTransformMatrix3D extrudeTransform = AffineTransformMatrix3D.createTranslation(extrusionVector);
780 
781             PlaneConvexSubset base;
782             for (final ConvexArea area : baseAreas) {
783                 base = subsetFromConvexArea(basePlane, area);
784                 if (extrudingOnPlusSide) {
785                     base = base.reverse();
786                 }
787 
788                 baseList.add(base);
789                 extrudedList.add(base.transform(extrudeTransform).reverse());
790             }
791 
792             result.addAll(baseList);
793             result.addAll(extrudedList);
794         }
795 
796         /** Add the side boundaries of the extruded region to the result list.
797          * @param subspaceRegion subspace region being extruded.
798          * @param result list to add the boundary results to
799          */
800         private void addSides(final RegionBSPTree2D subspaceRegion, final List<? super PlaneConvexSubset> result) {
801             Vector2D subStartPt;
802             Vector2D subEndPt;
803 
804             PlaneConvexSubset boundary;
805             for (final LinePath path : subspaceRegion.getBoundaryPaths()) {
806                 for (final LineConvexSubset lineSubset : path.getElements()) {
807                     subStartPt = lineSubset.getStartPoint();
808                     subEndPt = lineSubset.getEndPoint();
809 
810                     boundary = (subStartPt != null && subEndPt != null) ?
811                             extrudeSideFinite(basePlane.toSpace(subStartPt), basePlane.toSpace(subEndPt)) :
812                             extrudeSideInfinite(lineSubset);
813 
814                     result.add(boundary);
815                 }
816             }
817         }
818 
819         /** Extrude a single, finite boundary forming one of the sides of the extruded region.
820          * @param startPt start point of the boundary
821          * @param endPt end point of the boundary
822          * @return the extruded region side boundary
823          */
824         private ConvexPolygon3D extrudeSideFinite(final Vector3D startPt, final Vector3D endPt) {
825             final Vector3D extrudedStartPt = startPt.add(extrusionVector);
826             final Vector3D extrudedEndPt = endPt.add(extrusionVector);
827 
828             final List<Vector3D> vertices = extrudingOnPlusSide ?
829                     Arrays.asList(startPt, endPt, extrudedEndPt, extrudedStartPt) :
830                     Arrays.asList(startPt, extrudedStartPt, extrudedEndPt, endPt);
831 
832             return convexPolygonFromVertices(vertices, precision);
833         }
834 
835         /** Extrude a single, infinite boundary forming one of the sides of the extruded region.
836          * @param lineSubset line subset to extrude
837          * @return the extruded region side boundary
838          */
839         private PlaneConvexSubset extrudeSideInfinite(final LineConvexSubset lineSubset) {
840             final Vector2D subLinePt = lineSubset.getLine().getOrigin();
841             final Vector2D subLineDir = lineSubset.getLine().getDirection();
842 
843             final Vector3D linePt = basePlane.toSpace(subLinePt);
844             final Vector3D lineDir = linePt.vectorTo(basePlane.toSpace(subLinePt.add(subLineDir)));
845 
846             final EmbeddingPlane sidePlane;
847             if (extrudingOnPlusSide) {
848                 sidePlane = fromPointAndPlaneVectors(linePt, lineDir, extrusionVector, precision);
849             } else {
850                 sidePlane = fromPointAndPlaneVectors(linePt, extrusionVector, lineDir, precision);
851             }
852 
853             final Vector2D sideLineOrigin = sidePlane.toSubspace(linePt);
854             final Vector2D sideLineDir = sideLineOrigin.vectorTo(sidePlane.toSubspace(linePt.add(lineDir)));
855 
856             final Vector2D extrudedSideLineOrigin = sidePlane.toSubspace(linePt.add(extrusionVector));
857 
858             final Vector2D sideExtrusionDir = sidePlane.toSubspace(sidePlane.getOrigin().add(extrusionVector))
859                     .normalize();
860 
861             // construct a list of lines forming the bounds of the extruded subspace region
862             final List<Line> lines = new ArrayList<>();
863 
864             // add the top and bottom lines (original and extruded)
865             if (extrudingOnPlusSide) {
866                 lines.add(Lines.fromPointAndDirection(sideLineOrigin, sideLineDir, precision));
867                 lines.add(Lines.fromPointAndDirection(extrudedSideLineOrigin, sideLineDir.negate(), precision));
868             } else {
869                 lines.add(Lines.fromPointAndDirection(sideLineOrigin, sideLineDir.negate(), precision));
870                 lines.add(Lines.fromPointAndDirection(extrudedSideLineOrigin, sideLineDir, precision));
871             }
872 
873             // if we have a point on the original line, then connect the two
874             final Vector2D startPt = lineSubset.getStartPoint();
875             final Vector2D endPt = lineSubset.getEndPoint();
876             if (startPt != null) {
877                 lines.add(Lines.fromPointAndDirection(
878                         sidePlane.toSubspace(basePlane.toSpace(startPt)),
879                         extrudingOnPlusSide ? sideExtrusionDir.negate() : sideExtrusionDir,
880                         precision));
881             } else if (endPt != null) {
882                 lines.add(Lines.fromPointAndDirection(
883                         sidePlane.toSubspace(basePlane.toSpace(endPt)),
884                         extrudingOnPlusSide ? sideExtrusionDir : sideExtrusionDir.negate(),
885                         precision));
886             }
887 
888             return subsetFromConvexArea(sidePlane, ConvexArea.fromBounds(lines));
889         }
890     }
891 }