Planes.java

  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. import java.text.MessageFormat;
  19. import java.util.ArrayList;
  20. import java.util.Arrays;
  21. import java.util.Collection;
  22. import java.util.List;
  23. import java.util.function.BiFunction;

  24. import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
  25. import org.apache.commons.geometry.core.partitioning.Split;
  26. import org.apache.commons.geometry.core.partitioning.SplitLocation;
  27. import org.apache.commons.geometry.euclidean.internal.EuclideanUtils;
  28. import org.apache.commons.geometry.euclidean.threed.line.Line3D;
  29. import org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D;
  30. import org.apache.commons.geometry.euclidean.twod.ConvexArea;
  31. import org.apache.commons.geometry.euclidean.twod.Line;
  32. import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
  33. import org.apache.commons.geometry.euclidean.twod.Lines;
  34. import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
  35. import org.apache.commons.geometry.euclidean.twod.Vector2D;
  36. import org.apache.commons.geometry.euclidean.twod.path.LinePath;
  37. import org.apache.commons.numbers.core.Precision;

  38. /** Class containing factory methods for constructing {@link Plane} and {@link PlaneSubset} instances.
  39.  */
  40. public final class Planes {

  41.     /** Utility class; no instantiation. */
  42.     private Planes() {
  43.     }

  44.     /** Build a plane from a point and two (on plane) vectors.
  45.      * @param p the provided point (on plane)
  46.      * @param u u vector (on plane)
  47.      * @param v v vector (on plane)
  48.      * @param precision precision context used to compare floating point values
  49.      * @return a new plane
  50.      * @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
  51.      */
  52.     public static EmbeddingPlane fromPointAndPlaneVectors(final Vector3D p, final Vector3D u, final Vector3D v,
  53.             final Precision.DoubleEquivalence precision) {
  54.         final Vector3D.Unit uNorm = u.normalize();
  55.         final Vector3D.Unit vNorm = uNorm.orthogonal(v);
  56.         final Vector3D.Unit wNorm = uNorm.cross(vNorm).normalize();
  57.         final double originOffset = -p.dot(wNorm);

  58.         return new EmbeddingPlane(uNorm, vNorm, wNorm, originOffset, precision);
  59.     }

  60.     /** Build a plane from a normal.
  61.      * Chooses origin as point on plane.
  62.      * @param normal normal direction to the plane
  63.      * @param precision precision context used to compare floating point values
  64.      * @return a new plane
  65.      * @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
  66.      */
  67.     public static Plane fromNormal(final Vector3D normal, final Precision.DoubleEquivalence precision) {
  68.         return fromPointAndNormal(Vector3D.ZERO, normal, precision);
  69.     }

  70.     /** Build a plane from a point and a normal.
  71.      *
  72.      * @param p point belonging to the plane
  73.      * @param normal normal direction to the plane
  74.      * @param precision precision context used to compare floating point values
  75.      * @return a new plane
  76.      * @throws IllegalArgumentException if the norm of the given values is zero, NaN, or infinite.
  77.      */
  78.     public static Plane fromPointAndNormal(final Vector3D p, final Vector3D normal,
  79.             final Precision.DoubleEquivalence precision) {
  80.         final Vector3D.Unit unitNormal = normal.normalize();
  81.         final double originOffset = -p.dot(unitNormal);

  82.         return new Plane(unitNormal, originOffset, precision);
  83.     }

  84.     /** Build a plane from three points.
  85.      * <p>
  86.      * The plane is oriented in the direction of {@code (p2-p1) ^ (p3-p1)}
  87.      * </p>
  88.      *
  89.      * @param p1 first point belonging to the plane
  90.      * @param p2 second point belonging to the plane
  91.      * @param p3 third point belonging to the plane
  92.      * @param precision precision context used to compare floating point values
  93.      * @return a new plane
  94.      * @throws IllegalArgumentException if the points do not define a unique plane
  95.      */
  96.     public static Plane fromPoints(final Vector3D p1, final Vector3D p2, final Vector3D p3,
  97.             final Precision.DoubleEquivalence precision) {
  98.         return fromPoints(Arrays.asList(p1, p2, p3), precision);
  99.     }

  100.     /** Construct a plane from a collection of points lying on the plane. The plane orientation is
  101.      * determined by the overall orientation of the point sequence. For example, if the points wind
  102.      * around the z-axis in a counter-clockwise direction, then the plane normal will point up the
  103.      * +z axis. If the points wind in the opposite direction, then the plane normal will point down
  104.      * the -z axis. The {@code u} vector for the plane is set to the first non-zero vector between
  105.      * points in the sequence (ie, the first direction in the path).
  106.      *
  107.      * @param pts collection of sequenced points lying on the plane
  108.      * @param precision precision context used to compare floating point values
  109.      * @return a new plane containing the given points
  110.      * @throws IllegalArgumentException if the given collection does not contain at least 3 points or the
  111.      *      points do not define a unique plane
  112.      */
  113.     public static Plane fromPoints(final Collection<Vector3D> pts, final Precision.DoubleEquivalence precision) {
  114.         return new PlaneBuilder(pts, precision).build();
  115.     }

  116.     /** Create a new plane subset from a plane and an embedded convex subspace area.
  117.      * @param plane embedding plane for the area
  118.      * @param area area embedded in the plane
  119.      * @return a new convex sub plane instance
  120.      */
  121.     public static PlaneConvexSubset subsetFromConvexArea(final EmbeddingPlane plane, final ConvexArea area) {
  122.         if (area.isFinite()) {
  123.             // prefer a vertex-based representation for finite areas
  124.             final List<Vector3D> vertices = plane.toSpace(area.getVertices());
  125.             return fromConvexPlanarVertices(plane, vertices);
  126.         }

  127.         return new EmbeddedAreaPlaneConvexSubset(plane, area);
  128.     }

  129.     /** Create a new convex polygon from the given sequence of vertices. The vertices must define a unique
  130.      * plane, meaning that at least 3 unique vertices must be given. The given sequence is assumed to be closed,
  131.      * ie that an edge exists between the last vertex and the first.
  132.      * @param pts collection of points defining the convex polygon
  133.      * @param precision precision context used to compare floating point values
  134.      * @return a new convex polygon defined by the given sequence of vertices
  135.      * @throws IllegalArgumentException if fewer than 3 vertices are given or the vertices do not define a
  136.      *       unique plane
  137.      * @see #fromPoints(Collection, Precision.DoubleEquivalence)
  138.      */
  139.     public static ConvexPolygon3D convexPolygonFromVertices(final Collection<Vector3D> pts,
  140.             final Precision.DoubleEquivalence precision) {
  141.         final List<Vector3D> vertices = new ArrayList<>(pts.size());
  142.         final Plane plane = new PlaneBuilder(pts, precision).buildForConvexPolygon(vertices);

  143.         // make sure that the first point is not repeated at the end
  144.         final Vector3D firstPt = vertices.get(0);
  145.         final Vector3D lastPt = vertices.get(vertices.size() - 1);
  146.         if (firstPt.eq(lastPt, precision)) {
  147.             vertices.remove(vertices.size() - 1);
  148.         }

  149.         if (vertices.size() == EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
  150.             return new SimpleTriangle3D(plane, vertices.get(0), vertices.get(1), vertices.get(2));
  151.         }
  152.         return new VertexListConvexPolygon3D(plane, vertices);
  153.     }

  154.     /** Construct a triangle from three vertices. The triangle plane is oriented such that the points
  155.      * are arranged in a counter-clockwise order when looking down the plane normal.
  156.      * @param p1 first vertex
  157.      * @param p2 second vertex
  158.      * @param p3 third vertex
  159.      * @param precision precision context used for floating point comparisons
  160.      * @return a triangle constructed from the three vertices
  161.      * @throws IllegalArgumentException if the points do not define a unique plane
  162.      */
  163.     public static Triangle3D triangleFromVertices(final Vector3D p1, final Vector3D p2, final Vector3D p3,
  164.             final Precision.DoubleEquivalence precision) {
  165.         final Plane plane = fromPoints(p1, p2, p3, precision);
  166.         return new SimpleTriangle3D(plane, p1, p2, p3);
  167.     }

  168.     /** Construct a list of {@link Triangle3D} instances from a set of vertices and arrays of face indices.
  169.      * For example, the following code constructs a list of triangles forming a square pyramid.
  170.      * <pre>
  171.      * Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
  172.      *
  173.      * Vector3D[] vertices = {
  174.      *      Vector3D.ZERO,
  175.      *      Vector3D.of(1, 0, 0),
  176.      *      Vector3D.of(1, 1, 0),
  177.      *      Vector3D.of(0, 1, 0),
  178.      *      Vector3D.of(0.5, 0.5, 4)
  179.      * };
  180.      *
  181.      * int[][] faceIndices = {
  182.      *      {0, 2, 1},
  183.      *      {0, 3, 2},
  184.      *      {0, 1, 4},
  185.      *      {1, 2, 4},
  186.      *      {2, 3, 4},
  187.      *      {3, 0, 4}
  188.      * };
  189.      *
  190.      * List&lt;Triangle3D&gt; triangles = Planes.indexedTriangles(vertices, faceIndices, TEST_PRECISION);
  191.      * </pre>
  192.      * @param vertices vertices available for use in triangle construction
  193.      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
  194.      *      3 index values into {@code vertices}, defining the 3 vertices that will be used to construct the
  195.      *      triangle
  196.      * @param precision precision context used for floating point comparisons
  197.      * @return a list of triangles constructed from the set of vertices and face indices
  198.      * @throws IllegalArgumentException if any face index array does not contain exactly 3 elements or a set
  199.      *      of 3 vertices do not define a plane
  200.      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
  201.      */
  202.     public static List<Triangle3D> indexedTriangles(final Vector3D[] vertices, final int[][] faceIndices,
  203.             final Precision.DoubleEquivalence precision) {
  204.         return indexedTriangles(Arrays.asList(vertices), faceIndices, precision);
  205.     }

  206.     /** Construct a list of {@link Triangle3D} instances from a set of vertices and arrays of face indices.
  207.      * @param vertices vertices available for use in triangle construction
  208.      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
  209.      *      3 index values into {@code vertices}, defining the 3 vertices that will be used to construct the
  210.      *      triangle
  211.      * @param precision precision context used for floating point comparisons
  212.      * @return a list of triangles constructed from the set of vertices and face indices
  213.      * @throws IllegalArgumentException if any face index array does not contain exactly 3 elements or a set
  214.      *      of 3 vertices do not define a plane
  215.      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
  216.      * @see #indexedTriangles(Vector3D[], int[][], Precision.DoubleEquivalence)
  217.      */
  218.     public static List<Triangle3D> indexedTriangles(final List<? extends Vector3D> vertices, final int[][] faceIndices,
  219.             final Precision.DoubleEquivalence precision) {

  220.         final int numFaces = faceIndices.length;
  221.         final List<Triangle3D> triangles = new ArrayList<>(numFaces);

  222.         int[] face;
  223.         for (int i = 0; i < numFaces; ++i) {
  224.             face = faceIndices[i];
  225.             if (face.length != EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
  226.                 throw new IllegalArgumentException(MessageFormat.format(
  227.                         "Invalid number of vertex indices for face at index {0}: expected {1} but found {2}",
  228.                         i, EuclideanUtils.TRIANGLE_VERTEX_COUNT, face.length));
  229.             }

  230.             triangles.add(triangleFromVertices(
  231.                         vertices.get(face[0]),
  232.                         vertices.get(face[1]),
  233.                         vertices.get(face[2]),
  234.                         precision
  235.                     ));
  236.         }

  237.         return triangles;
  238.     }

  239.     /** Construct a list of {@link ConvexPolygon3D} instances from a set of vertices and arrays of face indices. Each
  240.      * face must contain at least 3 vertices but the number of vertices per face does not need to be constant.
  241.      * For example, the following code constructs a list of convex polygons forming a square pyramid.
  242.      * Note that the first face (the pyramid base) uses a different number of vertices than the other faces.
  243.      * <pre>
  244.      * Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
  245.      *
  246.      * Vector3D[] vertices = {
  247.      *      Vector3D.ZERO,
  248.      *      Vector3D.of(1, 0, 0),
  249.      *      Vector3D.of(1, 1, 0),
  250.      *      Vector3D.of(0, 1, 0),
  251.      *      Vector3D.of(0.5, 0.5, 4)
  252.      * };
  253.      *
  254.      * int[][] faceIndices = {
  255.      *      {0, 3, 2, 1}, // square base
  256.      *      {0, 1, 4},
  257.      *      {1, 2, 4},
  258.      *      {2, 3, 4},
  259.      *      {3, 0, 4}
  260.      * };
  261.      *
  262.      * List&lt;ConvexPolygon3D&gt; polygons = Planes.indexedConvexPolygons(vertices, faceIndices, precision);
  263.      * </pre>
  264.      * @param vertices vertices available for use in convex polygon construction
  265.      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
  266.      *      at least 3 index values into {@code vertices}, defining the vertices that will be used to construct the
  267.      *      convex polygon
  268.      * @param precision precision context used for floating point comparisons
  269.      * @return a list of convex polygons constructed from the set of vertices and face indices
  270.      * @throws IllegalArgumentException if any face index array does not contain at least 3 elements or a set
  271.      *      of vertices do not define a planar convex polygon
  272.      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
  273.      */
  274.     public static List<ConvexPolygon3D> indexedConvexPolygons(final Vector3D[] vertices, final int[][] faceIndices,
  275.             final Precision.DoubleEquivalence precision) {
  276.         return indexedConvexPolygons(Arrays.asList(vertices), faceIndices, precision);
  277.     }

  278.     /** Construct a list of {@link ConvexPolygon3D} instances from a set of vertices and arrays of face indices. Each
  279.      * face must contain at least 3 vertices but the number of vertices per face does not need to be constant.
  280.      * @param vertices vertices available for use in convex polygon construction
  281.      * @param faceIndices array of indices for each triangular face; each entry in the array is an array of
  282.      *      at least 3 index values into {@code vertices}, defining the vertices that will be used to construct the
  283.      *      convex polygon
  284.      * @param precision precision context used for floating point comparisons
  285.      * @return a list of convex polygons constructed from the set of vertices and face indices
  286.      * @throws IllegalArgumentException if any face index array does not contain at least 3 elements or a set
  287.      *      of vertices do not define a planar convex polygon
  288.      * @throws IndexOutOfBoundsException if any index into {@code vertices} is out of bounds
  289.      * @see #indexedConvexPolygons(Vector3D[], int[][], Precision.DoubleEquivalence)
  290.      */
  291.     public static List<ConvexPolygon3D> indexedConvexPolygons(final List<? extends Vector3D> vertices,
  292.             final int[][] faceIndices, final Precision.DoubleEquivalence precision) {
  293.         final int numFaces = faceIndices.length;
  294.         final List<ConvexPolygon3D> polygons = new ArrayList<>(numFaces);
  295.         final List<Vector3D> faceVertices = new ArrayList<>();

  296.         int[] face;
  297.         for (int i = 0; i < numFaces; ++i) {
  298.             face = faceIndices[i];
  299.             if (face.length < EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
  300.                 throw new IllegalArgumentException(MessageFormat.format(
  301.                         "Invalid number of vertex indices for face at index {0}: required at least {1} but found {2}",
  302.                         i, EuclideanUtils.TRIANGLE_VERTEX_COUNT, face.length));
  303.             }

  304.             for (final int vertexIndex : face) {
  305.                 faceVertices.add(vertices.get(vertexIndex));
  306.             }

  307.             polygons.add(convexPolygonFromVertices(
  308.                         faceVertices,
  309.                         precision
  310.                     ));

  311.             faceVertices.clear();
  312.         }

  313.         return polygons;
  314.     }

  315.     /** Get the boundaries of a 3D region created by extruding a polygon defined by a list of vertices. The ends
  316.      * ("top" and "bottom") of the extruded 3D region are flat while the sides follow the boundaries of the original
  317.      * 2D region.
  318.      * @param vertices vertices forming the 2D polygon to extrude
  319.      * @param plane plane to extrude the 2D polygon from
  320.      * @param extrusionVector vector to extrude the polygon vertices through
  321.      * @param precision precision context used to construct the 3D region boundaries
  322.      * @return the boundaries of the extruded 3D region
  323.      * @throws IllegalStateException if {@code vertices} contains only a single unique vertex
  324.      * @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
  325.      *      given plane and extrusion vector. This occurs when the extrusion vector has zero length
  326.      *      or is orthogonal to the plane normal
  327.      * @see LinePath#fromVertexLoop(Collection, Precision.DoubleEquivalence)
  328.      * @see #extrude(LinePath, EmbeddingPlane, Vector3D, Precision.DoubleEquivalence)
  329.      */
  330.     public static List<PlaneConvexSubset> extrudeVertexLoop(final List<Vector2D> vertices,
  331.             final EmbeddingPlane plane, final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
  332.         final LinePath path = LinePath.fromVertexLoop(vertices, precision);
  333.         return extrude(path, plane, extrusionVector, precision);
  334.     }

  335.     /** Get the boundaries of the 3D region created by extruding a 2D line path. The ends ("top" and "bottom") of
  336.      * the extruded 3D region are flat while the sides follow the boundaries of the original 2D region. The path is
  337.      * converted to a BSP tree before extrusion.
  338.      * @param path path to extrude
  339.      * @param plane plane to extrude the path from
  340.      * @param extrusionVector vector to extrude the polygon points through
  341.      * @param precision precision precision context used to construct the 3D region boundaries
  342.      * @return the boundaries of the extruded 3D region
  343.      * @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
  344.      *      given plane and extrusion vector. This occurs when the extrusion vector has zero length
  345.      *      or is orthogonal to the plane normal
  346.      * @see #extrude(RegionBSPTree2D, EmbeddingPlane, Vector3D, Precision.DoubleEquivalence)
  347.      */
  348.     public static List<PlaneConvexSubset> extrude(final LinePath path, final EmbeddingPlane plane,
  349.             final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
  350.         return extrude(path.toTree(), plane, extrusionVector, precision);
  351.     }

  352.     /** Get the boundaries of the 3D region created by extruding a 2D region. The ends ("top" and "bottom") of
  353.      * the extruded 3D region are flat while the sides follow the boundaries of the original 2D region.
  354.      * @param region region to extrude
  355.      * @param plane plane to extrude the region from
  356.      * @param extrusionVector vector to extrude the region points through
  357.      * @param precision precision precision context used to construct the 3D region boundaries
  358.      * @return the boundaries of the extruded 3D region
  359.      * @throws IllegalArgumentException if regions of non-zero size cannot be produced with the
  360.      *      given plane and extrusion vector. This occurs when the extrusion vector has zero length
  361.      *      or is orthogonal to the plane normal
  362.      */
  363.     public static List<PlaneConvexSubset> extrude(final RegionBSPTree2D region, final EmbeddingPlane plane,
  364.             final Vector3D extrusionVector, final Precision.DoubleEquivalence precision) {
  365.         return new PlaneRegionExtruder(plane, extrusionVector, precision).extrude(region);
  366.     }

  367.     /** Get the unique intersection of the plane subset with the given line. Null is
  368.      * returned if no unique intersection point exists (ie, the line and plane are
  369.      * parallel or coincident) or the line does not intersect the plane subset.
  370.      * @param planeSubset plane subset to intersect with
  371.      * @param line line to intersect with this plane subset
  372.      * @return the unique intersection point between the line and this plane subset
  373.      *      or null if no such point exists.
  374.      */
  375.     static Vector3D intersection(final PlaneSubset planeSubset, final Line3D line) {
  376.         final Vector3D pt = planeSubset.getPlane().intersection(line);
  377.         return (pt != null && planeSubset.contains(pt)) ? pt : null;
  378.     }

  379.     /** Get the unique intersection of the plane subset with the given line subset. Null
  380.      * is returned if the underlying line and plane do not have a unique intersection
  381.      * point (ie, they are parallel or coincident) or the intersection point is unique
  382.      * but is not contained in both the line subset and plane subset.
  383.      * @param planeSubset plane subset to intersect with
  384.      * @param lineSubset line subset to intersect with
  385.      * @return the unique intersection point between this plane subset and the argument or
  386.      *      null if no such point exists.
  387.      */
  388.     static Vector3D intersection(final PlaneSubset planeSubset, final LineConvexSubset3D lineSubset) {
  389.         final Vector3D pt = intersection(planeSubset, lineSubset.getLine());
  390.         return (pt != null && lineSubset.contains(pt)) ? pt : null;
  391.     }

  392.     /** Validate that the actual plane contains the same points as the expected plane, throwing an exception if not.
  393.      * The subspace orientations of embedding planes are not considered.
  394.      * @param expected the expected plane
  395.      * @param actual the actual plane
  396.      * @throws IllegalArgumentException if the actual plane is not equivalent to the expected plane
  397.      */
  398.     static void validatePlanesEquivalent(final Plane expected, final Plane actual) {
  399.         if (!expected.eq(actual, expected.getPrecision())) {
  400.             throw new IllegalArgumentException("Arguments do not represent the same plane. Expected " +
  401.                     expected + " but was " + actual + ".");
  402.         }
  403.     }

  404.     /** Generic split method that uses performs the split using the subspace region of the plane subset.
  405.      * @param splitter splitting hyperplane
  406.      * @param subset the plane subset being split
  407.      * @param factory function used to create new plane subset instances
  408.      * @param <T> Plane subset implementation type
  409.      * @return the result of the split operation
  410.      */
  411.     static <T extends PlaneSubset> Split<T> subspaceSplit(final Plane splitter, final T subset,
  412.             final BiFunction<? super EmbeddingPlane, ? super HyperplaneBoundedRegion<Vector2D>, T> factory) {

  413.         final EmbeddingPlane thisPlane = subset.getPlane().getEmbedding();

  414.         final Line3D intersection = thisPlane.intersection(splitter);
  415.         if (intersection == null) {
  416.             return getNonIntersectingSplitResult(splitter, subset);
  417.         } else {
  418.             final EmbeddingPlane embeddingPlane = subset.getPlane().getEmbedding();

  419.             // the lines intersect; split the subregion
  420.             final Vector3D intersectionOrigin = intersection.getOrigin();
  421.             final Vector2D subspaceP1 = embeddingPlane.toSubspace(intersectionOrigin);
  422.             final Vector2D subspaceP2 = embeddingPlane.toSubspace(intersectionOrigin.add(intersection.getDirection()));

  423.             final Line subspaceSplitter = Lines.fromPoints(subspaceP1, subspaceP2, thisPlane.getPrecision());

  424.             final Split<? extends HyperplaneBoundedRegion<Vector2D>> split =
  425.                     subset.getEmbedded().getSubspaceRegion().split(subspaceSplitter);
  426.             final SplitLocation subspaceSplitLoc = split.getLocation();

  427.             if (SplitLocation.MINUS == subspaceSplitLoc) {
  428.                 return new Split<>(subset, null);
  429.             } else if (SplitLocation.PLUS == subspaceSplitLoc) {
  430.                 return new Split<>(null, subset);
  431.             }

  432.             final T minus = (split.getMinus() != null) ? factory.apply(thisPlane, split.getMinus()) : null;
  433.             final T plus = (split.getPlus() != null) ? factory.apply(thisPlane, split.getPlus()) : null;

  434.             return new Split<>(minus, plus);
  435.         }
  436.     }

  437.     /** Get a split result for cases where the splitting plane and the plane containing the subset being split
  438.      * do not intersect. Callers are responsible for ensuring that the planes involved do not actually intersect.
  439.      * @param <T> Plane subset implementation type
  440.      * @param splitter plane performing the splitting
  441.      * @param subset subset being split
  442.      * @return the split result for the non-intersecting split
  443.      */
  444.     private static <T extends PlaneSubset> Split<T> getNonIntersectingSplitResult(
  445.             final Plane splitter, final T subset) {
  446.         final Plane plane = subset.getPlane();

  447.         final double offset = splitter.offset(plane);
  448.         final int comp = plane.getPrecision().compare(offset, 0.0);

  449.         if (comp < 0) {
  450.             return new Split<>(subset, null);
  451.         } else if (comp > 0) {
  452.             return new Split<>(null, subset);
  453.         } else {
  454.             return new Split<>(null, null);
  455.         }
  456.     }

  457.     /** Construct a convex polygon 3D from a plane and a list of vertices lying in the plane. Callers are
  458.      * responsible for ensuring that the vertices lie in the plane and define a convex polygon.
  459.      * @param plane the plane containing the convex polygon
  460.      * @param vertices vertices defining the closed, convex polygon. The must must contain at least 3 unique
  461.      *      vertices and should not include the start vertex at the end of the list.
  462.      * @return a new convex polygon instance
  463.      * @throws IllegalArgumentException if the size of {@code vertices} if less than 3
  464.      */
  465.     static ConvexPolygon3D fromConvexPlanarVertices(final Plane plane, final List<Vector3D> vertices) {
  466.         final int size = vertices.size();

  467.         if (size == EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
  468.             return new SimpleTriangle3D(plane, vertices.get(0), vertices.get(1), vertices.get(2));
  469.         }

  470.         return new VertexListConvexPolygon3D(plane, vertices);
  471.     }

  472.     /** Convert a convex polygon defined by a plane and list of points into a triangle fan.
  473.      * @param plane plane containing the convex polygon
  474.      * @param vertices vertices defining the convex polygon
  475.      * @return a triangle fan representing the same area as the convex polygon
  476.      * @throws IllegalArgumentException if fewer than 3 vertices are given
  477.      */
  478.     static List<Triangle3D> convexPolygonToTriangleFan(final Plane plane, final List<Vector3D> vertices) {
  479.         return EuclideanUtils.convexPolygonToTriangleFan(vertices,
  480.                 tri -> new SimpleTriangle3D(plane, tri.get(0), tri.get(1), tri.get(2)));
  481.     }

  482.     /** Internal helper class used to construct planes from sequences of points. Instances can be also be
  483.      * configured to collect lists of unique points found during plane construction and validate that the
  484.      * defined region is convex.
  485.      */
  486.     private static final class PlaneBuilder {

  487.         /** The point sequence to build a plane for. */
  488.         private final Collection<? extends Vector3D> pts;

  489.         /** Precision context used for floating point comparisons. */
  490.         private final Precision.DoubleEquivalence precision;

  491.         /** The start point from the point sequence. */
  492.         private Vector3D startPt;

  493.         /** The previous point from the point sequence. */
  494.         private Vector3D prevPt;

  495.         /** The previous vector from the point sequence, preceding from the {@code startPt} to {@code prevPt}. */
  496.         private Vector3D prevVector;

  497.         /** The computed {@code normal} vector for the plane. */
  498.         private Vector3D.Unit normal;

  499.         /** The x component of the sum of all cross products from adjacent vectors in the point sequence. */
  500.         private double crossSumX;

  501.         /** The y component of the sum of all cross products from adjacent vectors in the point sequence. */
  502.         private double crossSumY;

  503.         /** The z component of the sum of all cross products from adjacent vectors in the point sequence. */
  504.         private double crossSumZ;

  505.         /** If true, an exception will be thrown if the point sequence is discovered to be non-convex. */
  506.         private boolean requireConvex;

  507.         /** List that unique vertices discovered in the input sequence will be added to. */
  508.         private List<? super Vector3D> uniqueVertexOutput;

  509.         /** Construct a new build instance for the given point sequence and precision context.
  510.          * @param pts point sequence
  511.          * @param precision precision context used to perform floating point comparisons
  512.          */
  513.         PlaneBuilder(final Collection<? extends Vector3D> pts, final Precision.DoubleEquivalence precision) {
  514.             this.pts = pts;
  515.             this.precision = precision;
  516.         }

  517.         /** Build a plane from the configured point sequence.
  518.          * @return a plane built from the configured point sequence
  519.          * @throws IllegalArgumentException if the points do not define a plane
  520.          */
  521.         Plane build() {
  522.             if (pts.size() < EuclideanUtils.TRIANGLE_VERTEX_COUNT) {
  523.                 throw nonPlanar();
  524.             }

  525.             pts.forEach(this::processPoint);

  526.             return createPlane();
  527.         }

  528.         /** Build a plane from the configured point sequence, validating that the points form a convex region
  529.          * and adding all discovered unique points to the given list.
  530.          * @param vertexOutput list that unique points discovered in the point sequence will be added to
  531.          * @return a plane created from the configured point sequence
  532.          * @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
  533.          *      flag is true and the points do not define a convex area
  534.          */
  535.         Plane buildForConvexPolygon(final List<? super Vector3D> vertexOutput) {
  536.             this.requireConvex = true;
  537.             this.uniqueVertexOutput = vertexOutput;

  538.             return build();
  539.         }

  540.         /** Process a point from the point sequence.
  541.          * @param pt
  542.          * @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
  543.          *      flag is true and the points do not define a convex area
  544.          */
  545.         private void processPoint(final Vector3D pt) {
  546.             if (prevPt == null) {
  547.                 startPt = pt;
  548.                 prevPt = pt;

  549.                 if (uniqueVertexOutput != null) {
  550.                     uniqueVertexOutput.add(pt);
  551.                 }

  552.             } else if (!prevPt.eq(pt, precision)) { // skip duplicate points
  553.                 final Vector3D vec = startPt.vectorTo(pt);

  554.                 if (prevVector != null) {
  555.                     processCrossProduct(prevVector.cross(vec));
  556.                 }

  557.                 if (uniqueVertexOutput != null) {
  558.                     uniqueVertexOutput.add(pt);
  559.                 }

  560.                 prevPt = pt;
  561.                 prevVector = vec;
  562.             }
  563.         }

  564.         /** Process the computed cross product of two vectors from the input point sequence. The vectors
  565.          * start at the first point in the sequence and point to adjacent points later in the sequence.
  566.          * @param cross the cross product of two vectors from the input point sequence
  567.          * @throws IllegalArgumentException if the points do not define a plane or the {@code requireConvex}
  568.          *      flag is true and the points do not define a convex area
  569.          */
  570.         private void processCrossProduct(final Vector3D cross) {
  571.             crossSumX += cross.getX();
  572.             crossSumY += cross.getY();
  573.             crossSumZ += cross.getZ();

  574.             final double crossNorm = cross.norm();

  575.             if (!precision.eqZero(crossNorm)) {
  576.                 // the cross product has non-zero magnitude
  577.                 if (normal == null) {
  578.                     // save the first non-zero cross product as our normal
  579.                     normal = cross.normalize();
  580.                 } else {
  581.                     final double crossDot = normal.dot(cross) / crossNorm;

  582.                     // check non-planar before non-convex since the former is a more general type
  583.                     // of issue
  584.                     if (!precision.eq(1.0, Math.abs(crossDot))) {
  585.                         throw nonPlanar();
  586.                     } else if (requireConvex && crossDot < 0) {
  587.                         throw nonConvex();
  588.                     }
  589.                 }
  590.             }
  591.         }

  592.         /** Construct the plane instance using the value gathered during point processing.
  593.          * @return the created plane instance
  594.          * @throws IllegalArgumentException if the point do not define a plane
  595.          */
  596.         private Plane createPlane() {
  597.             if (normal == null) {
  598.                 throw nonPlanar();
  599.             }

  600.             // flip the normal if needed to match the overall orientation of the points
  601.             if (normal.dot(Vector3D.of(crossSumX, crossSumY, crossSumZ)) < 0) {
  602.                 normal = normal.negate();
  603.             }

  604.             // construct the plane
  605.             final double originOffset = -startPt.dot(normal);

  606.             return new Plane(normal, originOffset, precision);
  607.         }

  608.         /** Return an exception with a message stating that the points given to this builder do not
  609.          * define a plane.
  610.          * @return an exception stating that the points do not define a plane
  611.          */
  612.         private IllegalArgumentException nonPlanar() {
  613.             return new IllegalArgumentException("Points do not define a plane: " + pts);
  614.         }

  615.         /** Return an exception with a message stating that the points given to this builder do not
  616.          * define a convex region.
  617.          * @return an exception stating that the points do not define a plane
  618.          */
  619.         private IllegalArgumentException nonConvex() {
  620.             return new IllegalArgumentException("Points do not define a convex region: " + pts);
  621.         }
  622.     }

  623.     /** Class designed to create 3D regions by taking a 2D region and extruding from a base plane
  624.      * through an extrusion vector. The ends ("top" and "bottom") of the extruded 3D region are flat
  625.      * while the sides follow the boundaries of the original 2D region.
  626.      */
  627.     private static final class PlaneRegionExtruder {
  628.         /** Base plane to extrude from. */
  629.         private final EmbeddingPlane basePlane;

  630.         /** Vector to extrude along; the extruded plane is translated from the base plane by this amount. */
  631.         private final Vector3D extrusionVector;

  632.         /** True if the extrusion vector points to the plus side of the base plane. */
  633.         private final boolean extrudingOnPlusSide;

  634.         /** Precision context used to create boundaries. */
  635.         private final Precision.DoubleEquivalence precision;

  636.         /** Construct a new instance that performs extrusions from {@code basePlane} along {@code extrusionVector}.
  637.          * @param basePlane base plane to extrude from
  638.          * @param extrusionVector vector to extrude along
  639.          * @param precision precision context used to construct boundaries
  640.          * @throws IllegalArgumentException if the given extrusion vector and plane produce regions
  641.          *      of zero size
  642.          */
  643.         PlaneRegionExtruder(final EmbeddingPlane basePlane, final Vector3D extrusionVector,
  644.                 final Precision.DoubleEquivalence precision) {

  645.             this.basePlane = basePlane;

  646.             // Extruded plane; this forms the end of the 3D region opposite the base plane.
  647.             final EmbeddingPlane extrudedPlane = basePlane.translate(extrusionVector);

  648.             if (basePlane.contains(extrudedPlane)) {
  649.                 throw new IllegalArgumentException(
  650.                         "Extrusion vector produces regions of zero size: extrusionVector= " +
  651.                                 extrusionVector + ",  plane= " + basePlane);
  652.             }

  653.             this.extrusionVector = extrusionVector;
  654.             this.extrudingOnPlusSide = basePlane.getNormal().dot(extrusionVector) > 0;

  655.             this.precision = precision;
  656.         }

  657.         /** Extrude the given 2D BSP tree using the configured base plane and extrusion vector.
  658.          * @param subspaceRegion region to extrude
  659.          * @return the boundaries of the extruded region
  660.          */
  661.         public List<PlaneConvexSubset> extrude(final RegionBSPTree2D subspaceRegion) {
  662.             final List<PlaneConvexSubset> extrudedBoundaries = new ArrayList<>();

  663.             // add the boundaries
  664.             addEnds(subspaceRegion, extrudedBoundaries);
  665.             addSides(subspaceRegion, extrudedBoundaries);

  666.             return extrudedBoundaries;
  667.         }

  668.         /** Add the end ("top" and "bottom") of the extruded subspace region to the result list.
  669.          * @param subspaceRegion subspace region being extruded.
  670.          * @param result list to add the boundary results to
  671.          */
  672.         private void addEnds(final RegionBSPTree2D subspaceRegion, final List<? super PlaneConvexSubset> result) {
  673.             // add the base boundaries
  674.             final List<ConvexArea> baseAreas = subspaceRegion.toConvex();

  675.             final List<PlaneConvexSubset> baseList = new ArrayList<>(baseAreas.size());
  676.             final List<PlaneConvexSubset> extrudedList = new ArrayList<>(baseAreas.size());

  677.             final AffineTransformMatrix3D extrudeTransform = AffineTransformMatrix3D.createTranslation(extrusionVector);

  678.             PlaneConvexSubset base;
  679.             for (final ConvexArea area : baseAreas) {
  680.                 base = subsetFromConvexArea(basePlane, area);
  681.                 if (extrudingOnPlusSide) {
  682.                     base = base.reverse();
  683.                 }

  684.                 baseList.add(base);
  685.                 extrudedList.add(base.transform(extrudeTransform).reverse());
  686.             }

  687.             result.addAll(baseList);
  688.             result.addAll(extrudedList);
  689.         }

  690.         /** Add the side boundaries of the extruded region to the result list.
  691.          * @param subspaceRegion subspace region being extruded.
  692.          * @param result list to add the boundary results to
  693.          */
  694.         private void addSides(final RegionBSPTree2D subspaceRegion, final List<? super PlaneConvexSubset> result) {
  695.             Vector2D subStartPt;
  696.             Vector2D subEndPt;

  697.             PlaneConvexSubset boundary;
  698.             for (final LinePath path : subspaceRegion.getBoundaryPaths()) {
  699.                 for (final LineConvexSubset lineSubset : path.getElements()) {
  700.                     subStartPt = lineSubset.getStartPoint();
  701.                     subEndPt = lineSubset.getEndPoint();

  702.                     boundary = (subStartPt != null && subEndPt != null) ?
  703.                             extrudeSideFinite(basePlane.toSpace(subStartPt), basePlane.toSpace(subEndPt)) :
  704.                             extrudeSideInfinite(lineSubset);

  705.                     result.add(boundary);
  706.                 }
  707.             }
  708.         }

  709.         /** Extrude a single, finite boundary forming one of the sides of the extruded region.
  710.          * @param startPt start point of the boundary
  711.          * @param endPt end point of the boundary
  712.          * @return the extruded region side boundary
  713.          */
  714.         private ConvexPolygon3D extrudeSideFinite(final Vector3D startPt, final Vector3D endPt) {
  715.             final Vector3D extrudedStartPt = startPt.add(extrusionVector);
  716.             final Vector3D extrudedEndPt = endPt.add(extrusionVector);

  717.             final List<Vector3D> vertices = extrudingOnPlusSide ?
  718.                     Arrays.asList(startPt, endPt, extrudedEndPt, extrudedStartPt) :
  719.                     Arrays.asList(startPt, extrudedStartPt, extrudedEndPt, endPt);

  720.             return convexPolygonFromVertices(vertices, precision);
  721.         }

  722.         /** Extrude a single, infinite boundary forming one of the sides of the extruded region.
  723.          * @param lineSubset line subset to extrude
  724.          * @return the extruded region side boundary
  725.          */
  726.         private PlaneConvexSubset extrudeSideInfinite(final LineConvexSubset lineSubset) {
  727.             final Vector2D subLinePt = lineSubset.getLine().getOrigin();
  728.             final Vector2D subLineDir = lineSubset.getLine().getDirection();

  729.             final Vector3D linePt = basePlane.toSpace(subLinePt);
  730.             final Vector3D lineDir = linePt.vectorTo(basePlane.toSpace(subLinePt.add(subLineDir)));

  731.             final EmbeddingPlane sidePlane;
  732.             if (extrudingOnPlusSide) {
  733.                 sidePlane = fromPointAndPlaneVectors(linePt, lineDir, extrusionVector, precision);
  734.             } else {
  735.                 sidePlane = fromPointAndPlaneVectors(linePt, extrusionVector, lineDir, precision);
  736.             }

  737.             final Vector2D sideLineOrigin = sidePlane.toSubspace(linePt);
  738.             final Vector2D sideLineDir = sideLineOrigin.vectorTo(sidePlane.toSubspace(linePt.add(lineDir)));

  739.             final Vector2D extrudedSideLineOrigin = sidePlane.toSubspace(linePt.add(extrusionVector));

  740.             final Vector2D sideExtrusionDir = sidePlane.toSubspace(sidePlane.getOrigin().add(extrusionVector))
  741.                     .normalize();

  742.             // construct a list of lines forming the bounds of the extruded subspace region
  743.             final List<Line> lines = new ArrayList<>();

  744.             // add the top and bottom lines (original and extruded)
  745.             if (extrudingOnPlusSide) {
  746.                 lines.add(Lines.fromPointAndDirection(sideLineOrigin, sideLineDir, precision));
  747.                 lines.add(Lines.fromPointAndDirection(extrudedSideLineOrigin, sideLineDir.negate(), precision));
  748.             } else {
  749.                 lines.add(Lines.fromPointAndDirection(sideLineOrigin, sideLineDir.negate(), precision));
  750.                 lines.add(Lines.fromPointAndDirection(extrudedSideLineOrigin, sideLineDir, precision));
  751.             }

  752.             // if we have a point on the original line, then connect the two
  753.             final Vector2D startPt = lineSubset.getStartPoint();
  754.             final Vector2D endPt = lineSubset.getEndPoint();
  755.             if (startPt != null) {
  756.                 lines.add(Lines.fromPointAndDirection(
  757.                         sidePlane.toSubspace(basePlane.toSpace(startPt)),
  758.                         extrudingOnPlusSide ? sideExtrusionDir.negate() : sideExtrusionDir,
  759.                         precision));
  760.             } else if (endPt != null) {
  761.                 lines.add(Lines.fromPointAndDirection(
  762.                         sidePlane.toSubspace(basePlane.toSpace(endPt)),
  763.                         extrudingOnPlusSide ? sideExtrusionDir : sideExtrusionDir.negate(),
  764.                         precision));
  765.             }

  766.             return subsetFromConvexArea(sidePlane, ConvexArea.fromBounds(lines));
  767.         }
  768.     }
  769. }