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.util.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.Collection;
    22  import java.util.Collections;
    23  import java.util.List;
    24  import java.util.regex.Pattern;
    25
    26  import org.apache.commons.geometry.core.GeometryTestUtils;
    27  import org.apache.commons.geometry.core.RegionLocation;
    28  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    29  import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
    30  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    31  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
    32  import org.apache.commons.geometry.euclidean.twod.Line;
    33  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    34  import org.apache.commons.geometry.euclidean.twod.Lines;
    35  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
    36  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    37  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    38  import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
    39  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    40  import org.junit.Assert;
    41  import org.junit.Test;
    42
    43  public class PlanesTest {
    44
    45      private static final double TEST_EPS = 1e-10;
    46
    47      private static final DoublePrecisionContext TEST_PRECISION =
    48              new EpsilonDoublePrecisionContext(TEST_EPS);
    49
    50      @Test
    51      public void testSubsetFromConvexArea() {
    52          // arrange
    53          final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    54                  Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    55          final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    56                      Vector2D.of(1, 0),
    57                      Vector2D.of(3, 0),
    58                      Vector2D.of(3, 1),
    59                      Vector2D.of(1, 1)
    60                  ), TEST_PRECISION);
    61
    62          // act
    63          final PlaneConvexSubset sp = Planes.subsetFromConvexArea(plane, area);
    64
    65          // assert
    66          Assert.assertFalse(sp.isFull());
    67          Assert.assertFalse(sp.isEmpty());
    68          Assert.assertTrue(sp.isFinite());
    69
    70          Assert.assertEquals(2, sp.getSize(), TEST_EPS);
    71
    72          Assert.assertSame(plane, sp.getPlane());
    73          Assert.assertSame(plane, sp.getHyperplane());
    74          assertConvexAreasEqual(area, sp.getEmbedded().getSubspaceRegion());
    75      }
    76
    77      @Test
    78      public void testConvexPolygonFromVertices() {
    79          // arrange
    80          final Vector3D p0 = Vector3D.of(1, 0, 0);
    81          final Vector3D p1 = Vector3D.of(1, 1, 0);
    82          final Vector3D p2 = Vector3D.of(1, 1, 2);
    83
    84          // act
    85          final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(p0, p1, p2), TEST_PRECISION);
    86
    87          // assert
    88          Assert.assertTrue(sp instanceof Triangle3D);
    89
    90          Assert.assertFalse(sp.isFull());
    91          Assert.assertFalse(sp.isEmpty());
    92          Assert.assertTrue(sp.isFinite());
    93
    94          Assert.assertEquals(3, sp.getVertices().size());
    95          EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p0, p1, p2), sp.getVertices(), TEST_PRECISION);
    96
    97          Assert.assertEquals(1, sp.getSize(), TEST_EPS);
    98
    99          checkPlane(sp.getPlane(), Vector3D.of(1, 0, 0), Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_Z);
    100
    101         checkPoints(sp, RegionLocation.OUTSIDE,
    102                 Vector3D.of(0, 1, 1), Vector3D.of(0, 1, 0), Vector3D.of(0, 1, -1),
    103                 Vector3D.of(0, 0, 1), Vector3D.of(0, 0, 0), Vector3D.of(0, 0, -1),
    104                 Vector3D.of(0, -1, 1), Vector3D.of(0, -1, 0), Vector3D.of(0, -1, -1));
    105
    106         checkPoints(sp, RegionLocation.OUTSIDE,
    107                 Vector3D.of(1, 1, -1),
    108                 Vector3D.of(1, 0, 1), Vector3D.of(1, 0, -1),
    109                 Vector3D.of(1, -1, 1), Vector3D.of(1, -1, 0), Vector3D.of(1, -1, -1));
    110
    111         checkPoints(sp, RegionLocation.BOUNDARY,
    112                 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, 0),
    113                 Vector3D.of(1, 0, 0));
    114
    115         checkPoints(sp, RegionLocation.INSIDE, Vector3D.of(1, 0.5, 0.5));
    116
    117         checkPoints(sp, RegionLocation.OUTSIDE,
    118                 Vector3D.of(2, 1, 1), Vector3D.of(2, 1, 0), Vector3D.of(2, 1, -1),
    119                 Vector3D.of(2, 0, 1), Vector3D.of(2, 0, 0), Vector3D.of(2, 0, -1),
    120                 Vector3D.of(2, -1, 1), Vector3D.of(2, -1, 0), Vector3D.of(2, -1, -1));
    121     }
    122
    123     @Test
    124     public void testConvexPolygonFromVertices_duplicatePoints() {
    125         // arrange
    126         final Vector3D p0 = Vector3D.of(1, 0, 0);
    127         final Vector3D p1 = Vector3D.of(1, 1, 0);
    128         final Vector3D p2 = Vector3D.of(1, 1, 2);
    129         final Vector3D p3 = Vector3D.of(1, 0, 2);
    130
    131         // act
    132         final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
    133                     p0,
    134                     Vector3D.of(1, 1e-15, 0),
    135                     p1,
    136                     p2,
    137                     p3,
    138                     Vector3D.of(1, 1e-15, 2),
    139                     Vector3D.of(1, 0, 1e-15)
    140                 ), TEST_PRECISION);
    141
    142         // assert
    143         Assert.assertTrue(sp instanceof VertexListConvexPolygon3D);
    144
    145         Assert.assertFalse(sp.isFull());
    146         Assert.assertFalse(sp.isEmpty());
    147         Assert.assertTrue(sp.isFinite());
    148
    149         Assert.assertEquals(4, sp.getVertices().size());
    150         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p0, p1, p2, p3), sp.getVertices(), TEST_PRECISION);
    151
    152         Assert.assertEquals(2, sp.getSize(), TEST_EPS);
    153
    154         checkPlane(sp.getPlane(), Vector3D.of(1, 0, 0), Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_Z);
    155
    156         checkPoints(sp, RegionLocation.OUTSIDE,
    157                 Vector3D.of(0, 1, 1), Vector3D.of(0, 1, 0), Vector3D.of(0, 1, -1),
    158                 Vector3D.of(0, 0, 1), Vector3D.of(0, 0, 0), Vector3D.of(0, 0, -1),
    159                 Vector3D.of(0, -1, 1), Vector3D.of(0, -1, 0), Vector3D.of(0, -1, -1));
    160
    161         checkPoints(sp, RegionLocation.OUTSIDE,
    162                 Vector3D.of(1, 1, -1),
    163                 Vector3D.of(1, -1, 1), Vector3D.of(1, 0, -1),
    164                 Vector3D.of(1, -1, 0), Vector3D.of(1, -1, -1));
    165
    166         checkPoints(sp, RegionLocation.BOUNDARY,
    167                 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, 0),
    168                 Vector3D.of(1, 0, 0), Vector3D.of(1, 0, 2));
    169
    170         checkPoints(sp, RegionLocation.INSIDE, Vector3D.of(1, 0.5, 1));
    171
    172         checkPoints(sp, RegionLocation.OUTSIDE,
    173                 Vector3D.of(2, 1, 1), Vector3D.of(2, 1, 0), Vector3D.of(2, 1, -1),
    174                 Vector3D.of(2, 0, 1), Vector3D.of(2, 0, 0), Vector3D.of(2, 0, -1),
    175                 Vector3D.of(2, -1, 1), Vector3D.of(2, -1, 0), Vector3D.of(2, -1, -1));
    176     }
    177
    178     @Test
    179     public void testConvexPolygonFromVertices_nonPlanar() {
    180         // arrange
    181         final Pattern nonPlanarPattern = Pattern.compile("Points do not define a plane.*");
    182
    183         // act/assert
    184         GeometryTestUtils.assertThrows(() -> {
    185             Planes.convexPolygonFromVertices(Collections.emptyList(), TEST_PRECISION);
    186         }, IllegalArgumentException.class, nonPlanarPattern);
    187
    188         GeometryTestUtils.assertThrows(() -> {
    189             Planes.convexPolygonFromVertices(Collections.singletonList(Vector3D.ZERO), TEST_PRECISION);
    190         }, IllegalArgumentException.class, nonPlanarPattern);
    191
    192         GeometryTestUtils.assertThrows(() -> {
    193             Planes.convexPolygonFromVertices(Arrays.asList(Vector3D.ZERO, Vector3D.of(1, 0, 0)), TEST_PRECISION);
    194         }, IllegalArgumentException.class, nonPlanarPattern);
    195
    196         GeometryTestUtils.assertThrows(() -> {
    197             Planes.convexPolygonFromVertices(
    198                     Arrays.asList(Vector3D.ZERO, Vector3D.of(1, 0, 0), Vector3D.of(1, 1e-15, 0)), TEST_PRECISION);
    199         }, IllegalArgumentException.class, nonPlanarPattern);
    200
    201         GeometryTestUtils.assertThrows(() -> {
    202             Planes.convexPolygonFromVertices(Arrays.asList(
    203                         Vector3D.ZERO,
    204                         Vector3D.of(1, 0, 1),
    205                         Vector3D.of(1, 1, 0),
    206                         Vector3D.of(0, 1, 1)
    207                     ), TEST_PRECISION);
    208         }, IllegalArgumentException.class, nonPlanarPattern);
    209     }
    210
    211     @Test
    212     public void testConvexPolygonFromVertices_nonConvex() {
    213         // arrange
    214         final Pattern nonConvexPattern = Pattern.compile("Points do not define a convex region.*");
    215
    216         // act/assert
    217         GeometryTestUtils.assertThrows(() -> {
    218             Planes.convexPolygonFromVertices(Arrays.asList(
    219                         Vector3D.ZERO,
    220                         Vector3D.of(2, 0, 0),
    221                         Vector3D.of(2, 2, 0),
    222                         Vector3D.of(1, 1, 0),
    223                         Vector3D.of(1.5, 1, 0)
    224                     ), TEST_PRECISION);
    225         }, IllegalArgumentException.class, nonConvexPattern);
    226     }
    227
    228     @Test
    229     public void testTriangleFromVertices() {
    230         // act
    231         final Triangle3D tri = Planes.triangleFromVertices(
    232                 Vector3D.of(1, 1, 1),
    233                 Vector3D.of(2, 1, 1),
    234                 Vector3D.of(2, 1, 2), TEST_PRECISION);
    235
    236         // assert
    237         Assert.assertEquals(0.5, tri.getSize(), TEST_EPS);
    238         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(5.0 / 3.0, 1, 4.0 / 3.0),
    239                 tri.getCentroid(), TEST_EPS);
    240     }
    241
    242     @Test
    243     public void testTriangleFromVertices_degenerateTriangles() {
    244         // arrange
    245         final Pattern msg = Pattern.compile("^Points do not define a plane.*");
    246
    247         // act/assert
    248         GeometryTestUtils.assertThrows(() -> {
    249             Planes.triangleFromVertices(
    250                         Vector3D.ZERO,
    251                         Vector3D.of(1e-11, 0, 0),
    252                         Vector3D.of(0, 1e-11, 0),
    253                         TEST_PRECISION);
    254         }, IllegalArgumentException.class, msg);
    255
    256         GeometryTestUtils.assertThrows(() -> {
    257             Planes.triangleFromVertices(
    258                         Vector3D.ZERO,
    259                         Vector3D.of(1, 0, 0),
    260                         Vector3D.of(2, 0, 0),
    261                         TEST_PRECISION);
    262         }, IllegalArgumentException.class, msg);
    263     }
    264
    265     @Test
    266     public void testIndexedTriangles_singleTriangle_noFaces() {
    267         // act
    268         final List<Triangle3D> tris = Planes.indexedTriangles(new Vector3D[0], new int[0][], TEST_PRECISION);
    269
    270         // assert
    271         Assert.assertEquals(0, tris.size());
    272     }
    273
    274     @Test
    275     public void testIndexedTriangles_singleTriangle() {
    276         // arrange
    277         final Vector3D[] vertices = {
    278             Vector3D.ZERO,
    279             Vector3D.of(1, 0, 0),
    280             Vector3D.of(1, 1, 0)
    281         };
    282
    283         final int[][] faceIndices = {
    284             {0, 2, 1}
    285         };
    286
    287         // act
    288         final List<Triangle3D> tris = Planes.indexedTriangles(Arrays.asList(vertices), faceIndices, TEST_PRECISION);
    289
    290         // assert
    291         Assert.assertEquals(1, tris.size());
    292
    293         final Triangle3D a = tris.get(0);
    294         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_Z, a.getPlane().getNormal(), TEST_EPS);
    295         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, a.getPoint1(), TEST_EPS);
    296         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 0), a.getPoint2(), TEST_EPS);
    297         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0), a.getPoint3(), TEST_EPS);
    298     }
    299
    300     @Test
    301     public void testIndexedTriangles_multipleTriangles() {
    302         // arrange
    303         // define a square pyramind
    304         final Vector3D[] vertices = {
    305             Vector3D.ZERO,
    306             Vector3D.of(1, 0, 0),
    307             Vector3D.of(1, 1, 0),
    308             Vector3D.of(0, 1, 0),
    309             Vector3D.of(0.5, 0.5, 4)
    310         };
    311
    312         final int[][] faceIndices = {
    313             {0, 2, 1},
    314             {0, 3, 2},
    315             {0, 1, 4},
    316             {1, 2, 4},
    317             {2, 3, 4},
    318             {3, 0, 4}
    319         };
    320
    321         // act
    322         final List<Triangle3D> tris = Planes.indexedTriangles(vertices, faceIndices, TEST_PRECISION);
    323
    324         // assert
    325         Assert.assertEquals(6, tris.size());
    326
    327         final RegionBSPTree3D tree = RegionBSPTree3D.from(tris);
    328         Assert.assertEquals(4 / 3.0, tree.getSize(), TEST_EPS);
    329
    330         final Bounds3D bounds = tree.getBounds();
    331         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, bounds.getMin(), TEST_EPS);
    332         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 4), bounds.getMax(), TEST_EPS);
    333     }
    334
    335     @Test
    336     public void testIndexedTriangles_invalidArgs() {
    337         // arrange
    338         final Vector3D[] vertices = {
    339             Vector3D.ZERO,
    340             Vector3D.of(1, 0, 0),
    341             Vector3D.of(1, 1, 0),
    342             Vector3D.of(2, 0, 0)
    343         };
    344
    345         // act/assert
    346         GeometryTestUtils.assertThrows(() -> {
    347             Planes.indexedTriangles(vertices, new int[][] {
    348                 {0}
    349             }, TEST_PRECISION);
    350         }, IllegalArgumentException.class,
    351                 "Invalid number of vertex indices for face at index 0: expected 3 but found 1");
    352
    353         GeometryTestUtils.assertThrows(() -> {
    354             Planes.indexedTriangles(vertices, new int[][] {
    355                 {0, 1, 2, 0}
    356             }, TEST_PRECISION);
    357         }, IllegalArgumentException.class,
    358                 "Invalid number of vertex indices for face at index 0: expected 3 but found 4");
    359
    360         GeometryTestUtils.assertThrows(() -> {
    361             Planes.indexedTriangles(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
    362                 {0, 1, 3}
    363             }, TEST_PRECISION);
    364         }, IllegalArgumentException.class, Pattern.compile("^Points do not define a plane: .*"));
    365
    366         GeometryTestUtils.assertThrows(() -> {
    367             Planes.indexedTriangles(vertices, new int[][] {
    368                 {0, 1, 10}
    369             }, TEST_PRECISION);
    370         }, IndexOutOfBoundsException.class);
    371
    372         GeometryTestUtils.assertThrows(() -> {
    373             Planes.indexedTriangles(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
    374                 {0, 1, 10}
    375             }, TEST_PRECISION);
    376         }, IndexOutOfBoundsException.class);
    377     }
    378
    379     @Test
    380     public void testIndexedConvexPolygons_singleTriangle_noFaces() {
    381         // act
    382         final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(new Vector3D[0], new int[0][], TEST_PRECISION);
    383
    384         // assert
    385         Assert.assertEquals(0, polys.size());
    386     }
    387
    388     @Test
    389     public void testIndexedConvexPolygons_singleSquare() {
    390         // arrange
    391         final Vector3D[] vertices = {
    392             Vector3D.ZERO,
    393             Vector3D.of(1, 0, 0),
    394             Vector3D.of(1, 1, 0),
    395             Vector3D.of(0, 1, 0)
    396         };
    397
    398         final int[][] faceIndices = {
    399             {0, 3, 2, 1}
    400         };
    401
    402         // act
    403         final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(Arrays.asList(vertices), faceIndices,
    404                 TEST_PRECISION);
    405
    406         // assert
    407         Assert.assertEquals(1, polys.size());
    408
    409         final ConvexPolygon3D a = polys.get(0);
    410         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(
    411                     Vector3D.ZERO,
    412                     Vector3D.of(0, 1, 0),
    413                     Vector3D.of(1, 1, 0),
    414                     Vector3D.of(1, 0, 0)
    415                 ), a.getVertices(), TEST_PRECISION);
    416     }
    417
    418     @Test
    419     public void testIndexedConvexPolygons_mixedPolygons() {
    420         // arrange
    421         // define a square pyramind
    422         final Vector3D[] vertices = {
    423             Vector3D.ZERO,
    424             Vector3D.of(1, 0, 0),
    425             Vector3D.of(1, 1, 0),
    426             Vector3D.of(0, 1, 0),
    427             Vector3D.of(0.5, 0.5, 4)
    428         };
    429
    430         final int[][] faceIndices = {
    431             {0, 3, 2, 1},
    432             {0, 1, 4},
    433             {1, 2, 4},
    434             {2, 3, 4},
    435             {3, 0, 4}
    436         };
    437
    438         // act
    439         final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, faceIndices, TEST_PRECISION);
    440
    441         // assert
    442         Assert.assertEquals(5, polys.size());
    443
    444         final RegionBSPTree3D tree = RegionBSPTree3D.from(polys);
    445         Assert.assertEquals(4 / 3.0, tree.getSize(), TEST_EPS);
    446
    447         final Bounds3D bounds = tree.getBounds();
    448         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, bounds.getMin(), TEST_EPS);
    449         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 4), bounds.getMax(), TEST_EPS);
    450     }
    451
    452     @Test
    453     public void testIndexedConvexPolygons_cube() {
    454         // arrange
    455         final Vector3D[] vertices = {
    456             Vector3D.of(-0.5, -0.5, -0.5),
    457             Vector3D.of(0.5, -0.5, -0.5),
    458             Vector3D.of(0.5, 0.5, -0.5),
    459             Vector3D.of(-0.5, 0.5, -0.5),
    460
    461             Vector3D.of(-0.5, -0.5, 0.5),
    462             Vector3D.of(0.5, -0.5, 0.5),
    463             Vector3D.of(0.5, 0.5, 0.5),
    464             Vector3D.of(-0.5, 0.5, 0.5)
    465         };
    466
    467         final int[][] faceIndices = {
    468             {0, 4, 7, 3},
    469             {1, 2, 6, 5},
    470             {0, 1, 5, 4},
    471             {3, 7, 6, 2},
    472             {0, 3, 2, 1},
    473             {4, 5, 6, 7}
    474         };
    475
    476         // act
    477         final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(Arrays.asList(vertices), faceIndices,
    478                 TEST_PRECISION);
    479
    480         // assert
    481         Assert.assertEquals(6, polys.size());
    482
    483         final RegionBSPTree3D tree = RegionBSPTree3D.from(polys);
    484         Assert.assertEquals(1.0, tree.getSize(), TEST_EPS);
    485
    486         final Bounds3D bounds = tree.getBounds();
    487         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-0.5, -0.5, -0.5), bounds.getMin(), TEST_EPS);
    488         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), bounds.getMax(), TEST_EPS);
    489     }
    490
    491     @Test
    492     public void testIndexedConvexPolygons_invalidArgs() {
    493         // arrange
    494         final Vector3D[] vertices = {
    495             Vector3D.ZERO,
    496             Vector3D.of(1, 0, 0),
    497             Vector3D.of(1, 1, 0),
    498             Vector3D.of(2, 0, 0)
    499         };
    500
    501         // act/assert
    502         GeometryTestUtils.assertThrows(() -> {
    503             Planes.indexedConvexPolygons(vertices, new int[][] {
    504                 {0}
    505             }, TEST_PRECISION);
    506         }, IllegalArgumentException.class,
    507                 "Invalid number of vertex indices for face at index 0: required at least 3 but found 1");
    508
    509         GeometryTestUtils.assertThrows(() -> {
    510             Planes.indexedConvexPolygons(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
    511                 {0, 1, 3}
    512             }, TEST_PRECISION);
    513         }, IllegalArgumentException.class, Pattern.compile("^Points do not define a plane: .*"));
    514
    515         GeometryTestUtils.assertThrows(() -> {
    516             Planes.indexedConvexPolygons(vertices, new int[][] {
    517                 {0, 1, 10}
    518             }, TEST_PRECISION);
    519         }, IndexOutOfBoundsException.class);
    520
    521         GeometryTestUtils.assertThrows(() -> {
    522             Planes.indexedConvexPolygons(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
    523                 {0, 1, 10}
    524             }, TEST_PRECISION);
    525         }, IndexOutOfBoundsException.class);
    526     }
    527
    528     @Test
    529     public void testConvexPolygonToTriangleFan_threeVertices() {
    530         // arrange
    531         final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    532         final Vector3D p1 = Vector3D.ZERO;
    533         final Vector3D p2 = Vector3D.of(1, 0, 0);
    534         final Vector3D p3 = Vector3D.of(0, 1, 0);
    535
    536         // act
    537         final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3));
    538
    539         // assert
    540         Assert.assertEquals(1, tris.size());
    541
    542         final Triangle3D a = tris.get(0);
    543         Assert.assertSame(plane, a.getPlane());
    544         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), a.getVertices(), TEST_PRECISION);
    545     }
    546
    547     @Test
    548     public void testConvexPolygonToTriangleFan_fourVertices() {
    549         // arrange
    550         final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    551         final Vector3D p1 = Vector3D.ZERO;
    552         final Vector3D p2 = Vector3D.of(1, 0, 0);
    553         final Vector3D p3 = Vector3D.of(1, 1, 0);
    554         final Vector3D p4 = Vector3D.of(0, 1, 0);
    555
    556         // act
    557         final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3, p4));
    558
    559         // assert
    560         Assert.assertEquals(2, tris.size());
    561
    562         final Triangle3D a = tris.get(0);
    563         Assert.assertSame(plane, a.getPlane());
    564         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), a.getVertices(), TEST_PRECISION);
    565
    566         final Triangle3D b = tris.get(1);
    567         Assert.assertSame(plane, b.getPlane());
    568         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p3, p4), b.getVertices(), TEST_PRECISION);
    569     }
    570
    571     @Test
    572     public void testConvexPolygonToTriangleFan_fourVertices_chooseLargestInteriorAngleForBase() {
    573         // arrange
    574         final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    575         final Vector3D p1 = Vector3D.ZERO;
    576         final Vector3D p2 = Vector3D.of(1, 0, 0);
    577         final Vector3D p3 = Vector3D.of(2, 1, 0);
    578         final Vector3D p4 = Vector3D.of(1.5, 1, 0);
    579
    580         // act
    581         final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3, p4));
    582
    583         // assert
    584         Assert.assertEquals(2, tris.size());
    585
    586         final Triangle3D a = tris.get(0);
    587         Assert.assertSame(plane, a.getPlane());
    588         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p1, p2), a.getVertices(), TEST_PRECISION);
    589
    590         final Triangle3D b = tris.get(1);
    591         Assert.assertSame(plane, b.getPlane());
    592         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p2, p3), b.getVertices(), TEST_PRECISION);
    593     }
    594
    595     @Test
    596     public void testConvexPolygonToTriangleFan_fourVertices_distancesLessThanPrecision() {
    597         // This test checks that the triangle fan algorithm is not affected by the distances between
    598         // the vertices, just as long as the points are not exactly equal. Callers are responsible for
    599         // ensuring that the points are actually distinct according to the relevant precision context.
    600
    601         // arrange
    602         final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    603         final Vector3D p1 = Vector3D.ZERO;
    604         final Vector3D p2 = Vector3D.of(1e-20, 0, 0);
    605         final Vector3D p3 = Vector3D.of(1e-20, 1e-20, 0);
    606         final Vector3D p4 = Vector3D.of(0, 1e-20, 0);
    607
    608         // act
    609         final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3, p4));
    610
    611         // assert
    612         Assert.assertEquals(2, tris.size());
    613
    614         final Triangle3D a = tris.get(0);
    615         Assert.assertSame(plane, a.getPlane());
    616         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), a.getVertices(), TEST_PRECISION);
    617
    618         final Triangle3D b = tris.get(1);
    619         Assert.assertSame(plane, b.getPlane());
    620         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p3, p4), b.getVertices(), TEST_PRECISION);
    621     }
    622
    623
    624     @Test
    625     public void testConvexPolygonToTriangleFan_sixVertices() {
    626         // arrange
    627         final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    628         final Vector3D p1 = Vector3D.ZERO;
    629         final Vector3D p2 = Vector3D.of(1, -1, 0);
    630         final Vector3D p3 = Vector3D.of(1.5, -1, 0);
    631         final Vector3D p4 = Vector3D.of(5, 0, 0);
    632         final Vector3D p5 = Vector3D.of(3, 1, 0);
    633         final Vector3D p6 = Vector3D.of(0.5, 1, 0);
    634
    635         // act
    636         final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3, p4, p5, p6));
    637
    638         // assert
    639         Assert.assertEquals(4, tris.size());
    640
    641         final Triangle3D a = tris.get(0);
    642         Assert.assertSame(plane, a.getPlane());
    643         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p4, p5), a.getVertices(), TEST_PRECISION);
    644
    645         final Triangle3D b = tris.get(1);
    646         Assert.assertSame(plane, b.getPlane());
    647         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p5, p6), b.getVertices(), TEST_PRECISION);
    648
    649         final Triangle3D c = tris.get(2);
    650         Assert.assertSame(plane, c.getPlane());
    651         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p6, p1), c.getVertices(), TEST_PRECISION);
    652
    653         final Triangle3D d = tris.get(3);
    654         Assert.assertSame(plane, d.getPlane());
    655         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p1, p2), d.getVertices(), TEST_PRECISION);
    656     }
    657
    658     @Test
    659     public void testConvexPolygonToTriangleFan_notEnoughVertices() {
    660         // arrange
    661         final String baseMsg = "Cannot create triangle fan: 3 or more vertices are required but found only ";
    662         final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    663
    664         // act/assert
    665         GeometryTestUtils.assertThrows(() -> {
    666             Planes.convexPolygonToTriangleFan(plane, Collections.emptyList());
    667         }, IllegalArgumentException.class, baseMsg + "0");
    668
    669         GeometryTestUtils.assertThrows(() -> {
    670             Planes.convexPolygonToTriangleFan(plane, Collections.singletonList(Vector3D.ZERO));
    671         }, IllegalArgumentException.class, baseMsg + "1");
    672
    673         GeometryTestUtils.assertThrows(() -> {
    674             Planes.convexPolygonToTriangleFan(plane, Arrays.asList(Vector3D.ZERO, Vector3D.of(1, 0, 0)));
    675         }, IllegalArgumentException.class, baseMsg + "2");
    676     }
    677
    678     @Test
    679     public void testExtrudeVertexLoop_convex() {
    680         // arrange
    681         final List<Vector2D> vertices = Arrays.asList(
    682                 Vector2D.of(2, 1),
    683                 Vector2D.of(3, 1),
    684                 Vector2D.of(2, 3)
    685             );
    686
    687         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    688                 Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_X, TEST_PRECISION);
    689         final Vector3D extrusionVector = Vector3D.of(1, 0, 1);
    690
    691         // act
    692         final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
    693
    694         // assert
    695         Assert.assertEquals(5, boundaries.size());
    696
    697         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    698
    699         Assert.assertEquals(1, tree.getSize(), TEST_EPS);
    700         EuclideanTestUtils.assertCoordinatesEqual(
    701                 Vector3D.of(-5.0 / 3.0, 7.0 / 3.0, 1).add(extrusionVector.multiply(0.5)), tree.getCentroid(), TEST_EPS);
    702
    703         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    704                 Vector3D.of(-1.5, 2.5, 1.25), tree.getCentroid());
    705         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    706                 Vector3D.of(-2, 2, 1), Vector3D.of(-1, 2, 1), Vector3D.of(-1, 3, 1),
    707                 Vector3D.of(-1, 2, 2), Vector3D.of(0, 2, 2), Vector3D.of(0, 3, 2));
    708
    709         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    710                 Vector3D.of(-1.5, 2.5, 0.9), Vector3D.of(-1.5, 2.5, 2.1));
    711     }
    712
    713     @Test
    714     public void testExtrudeVertexLoop_nonConvex() {
    715         // arrange
    716         final List<Vector2D> vertices = Arrays.asList(
    717                 Vector2D.of(1, 2),
    718                 Vector2D.of(1, -2),
    719                 Vector2D.of(4, -2),
    720                 Vector2D.of(4, -1),
    721                 Vector2D.of(2, -1),
    722                 Vector2D.of(2, 1),
    723                 Vector2D.of(4, 1),
    724                 Vector2D.of(4, 2),
    725                 Vector2D.of(1, 2)
    726             );
    727
    728         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    729                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    730         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    731
    732         // act
    733         final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
    734
    735         // assert
    736         Assert.assertEquals(14, boundaries.size());
    737
    738         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    739
    740         Assert.assertEquals(16, tree.getSize(), TEST_EPS);
    741         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2.25, 0, 0), tree.getCentroid(), TEST_EPS);
    742
    743         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    744                 Vector3D.of(1.5, 0, 0), Vector3D.of(3, 1.5, 0), Vector3D.of(3, -1.5, 0));
    745         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    746                 Vector3D.of(1.5, 0, -1), Vector3D.of(3, 1.5, -1), Vector3D.of(3, -1.5, -1),
    747                 Vector3D.of(1.5, 0, 1), Vector3D.of(3, 1.5, 1), Vector3D.of(3, -1.5, 1),
    748                 Vector3D.of(1, 0, 0), Vector3D.of(2.5, -2, 0), Vector3D.of(4, -1.5, 0),
    749                 Vector3D.of(3, -1, 0), Vector3D.of(2, 0, 0), Vector3D.of(3, 1, 0),
    750                 Vector3D.of(4, 1.5, 0), Vector3D.of(2.5, 2, 0));
    751
    752         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    753                 tree.getCentroid(), Vector3D.ZERO, Vector3D.of(5, 0, 0));
    754     }
    755
    756     @Test
    757     public void testExtrudeVertexLoop_noVertices() {
    758         // arrange
    759         final List<Vector2D> vertices = new ArrayList<>();
    760
    761         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    762                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    763         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    764
    765         // act
    766         final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
    767
    768         // assert
    769         Assert.assertEquals(0, boundaries.size());
    770     }
    771
    772     @Test
    773     public void testExtrudeVertexLoop_twoVertices_producesInfiniteRegion() {
    774         // arrange
    775         final List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.of(1, 1));
    776
    777         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    778                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    779         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    780
    781         // act
    782         final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
    783
    784         // assert
    785         Assert.assertEquals(3, boundaries.size());
    786
    787         final PlaneConvexSubset bottom = boundaries.get(0);
    788         Assert.assertTrue(bottom.isInfinite());
    789         Assert.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
    790         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
    791
    792         final PlaneConvexSubset top = boundaries.get(1);
    793         Assert.assertTrue(top.isInfinite());
    794         Assert.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
    795         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
    796
    797         final PlaneConvexSubset side = boundaries.get(2);
    798         Assert.assertTrue(side.isInfinite());
    799         Assert.assertTrue(side.getPlane().contains(Vector3D.ZERO));
    800         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
    801                 side.getPlane().getNormal(), TEST_EPS);
    802
    803         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    804         Assert.assertFalse(tree.isFull());
    805         Assert.assertTrue(tree.isInfinite());
    806
    807         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    808                 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
    809
    810         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    811                 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
    812
    813         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    814                 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
    815     }
    816
    817     @Test
    818     public void testExtrudeVertexLoop_invalidVertexList() {
    819         // arrange
    820         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    821                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    822         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    823
    824         // act/assert
    825         GeometryTestUtils.assertThrows(() -> {
    826             Planes.extrudeVertexLoop(Collections.singletonList(Vector2D.ZERO), plane, extrusionVector, TEST_PRECISION);
    827         }, IllegalStateException.class);
    828
    829         GeometryTestUtils.assertThrows(() -> {
    830             Planes.extrudeVertexLoop(Arrays.asList(Vector2D.ZERO, Vector2D.of(0, 1e-16)), plane,
    831                     extrusionVector, TEST_PRECISION);
    832         }, IllegalStateException.class);
    833     }
    834
    835     @Test
    836     public void testExtrudeVertexLoop_regionsConsistentBetweenExtrusionPlanes() {
    837         // arrange
    838         final List<Vector2D> vertices = Arrays.asList(
    839                 Vector2D.of(1, 2),
    840                 Vector2D.of(1, -2),
    841                 Vector2D.of(4, -2),
    842                 Vector2D.of(4, -1),
    843                 Vector2D.of(2, -1),
    844                 Vector2D.of(2, 1),
    845                 Vector2D.of(4, 1),
    846                 Vector2D.of(4, 2),
    847                 Vector2D.of(1, 2)
    848             );
    849
    850         final RegionBSPTree2D subspaceTree = LinePath.fromVertexLoop(vertices, TEST_PRECISION).toTree();
    851
    852         final double subspaceSize = subspaceTree.getSize();
    853         final Vector2D subspaceCentroid = subspaceTree.getCentroid();
    854
    855         final double extrusionLength = 2;
    856         final double expectedSize = subspaceSize * extrusionLength;
    857
    858         final Vector3D planePt = Vector3D.of(-1, 2, -3);
    859
    860         EuclideanTestUtils.permuteSkipZero(-2, 2, 1, (x, y, z) -> {
    861             final Vector3D normal = Vector3D.of(x, y, z);
    862             final EmbeddingPlane plane = Planes.fromPointAndNormal(planePt, normal, TEST_PRECISION).getEmbedding();
    863
    864             final Vector3D baseCentroid = plane.toSpace(subspaceCentroid);
    865
    866             final Vector3D plusExtrusionVector = normal.withNorm(extrusionLength);
    867             final Vector3D minusExtrusionVector = plusExtrusionVector.negate();
    868
    869             // act
    870             final RegionBSPTree3D extrudePlus = RegionBSPTree3D.from(
    871                     Planes.extrudeVertexLoop(vertices, plane, plusExtrusionVector, TEST_PRECISION));
    872             final RegionBSPTree3D extrudeMinus = RegionBSPTree3D.from(
    873                     Planes.extrudeVertexLoop(vertices, plane, minusExtrusionVector, TEST_PRECISION));
    874
    875             // assert
    876             Assert.assertEquals(expectedSize, extrudePlus.getSize(), TEST_EPS);
    877             EuclideanTestUtils.assertCoordinatesEqual(baseCentroid.add(plusExtrusionVector.multiply(0.5)),
    878                     extrudePlus.getCentroid(), TEST_EPS);
    879
    880             Assert.assertEquals(expectedSize, extrudeMinus.getSize(), TEST_EPS);
    881             EuclideanTestUtils.assertCoordinatesEqual(baseCentroid.add(minusExtrusionVector.multiply(0.5)),
    882                     extrudeMinus.getCentroid(), TEST_EPS);
    883         });
    884     }
    885
    886     @Test
    887     public void testExtrude_vertexLoop_clockwiseWinding() {
    888         // arrange
    889         final List<Vector2D> vertices = Arrays.asList(
    890             Vector2D.of(0, 1),
    891             Vector2D.of(1, 0),
    892             Vector2D.of(0, -1),
    893             Vector2D.of(-1, 0));
    894
    895         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    896                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    897         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    898
    899         // act
    900         final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
    901
    902         // assert
    903         final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
    904
    905         Assert.assertTrue(resultTree.isInfinite());
    906         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
    907                 Vector3D.of(1, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0));
    908         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE, Vector3D.ZERO);
    909     }
    910
    911     @Test
    912     public void testExtrude_linePath_emptyPath() {
    913         // arrange
    914         final LinePath path = LinePath.empty();
    915
    916         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    917                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    918         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    919
    920         // act
    921         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    922
    923         // assert
    924         Assert.assertEquals(0, boundaries.size());
    925     }
    926
    927     @Test
    928     public void testExtrude_linePath_singleSegment_producesInfiniteRegion_extrudingOnMinus() {
    929         // arrange
    930         final LinePath path = LinePath.builder(TEST_PRECISION)
    931                 .append(Vector2D.ZERO)
    932                 .append(Vector2D.of(1, 1))
    933                 .build();
    934
    935         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    936                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    937         final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
    938
    939         // act
    940         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    941
    942         // assert
    943         Assert.assertEquals(3, boundaries.size());
    944
    945         final PlaneConvexSubset top = boundaries.get(0);
    946         Assert.assertTrue(top.isInfinite());
    947         Assert.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
    948         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
    949
    950         final PlaneConvexSubset bottom = boundaries.get(1);
    951         Assert.assertTrue(bottom.isInfinite());
    952         Assert.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
    953         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
    954
    955         final PlaneConvexSubset side = boundaries.get(2);
    956         Assert.assertTrue(side.isInfinite());
    957         Assert.assertTrue(side.getPlane().contains(Vector3D.ZERO));
    958         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
    959                 side.getPlane().getNormal(), TEST_EPS);
    960
    961         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    962         Assert.assertFalse(tree.isFull());
    963         Assert.assertTrue(tree.isInfinite());
    964
    965         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    966                 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
    967
    968         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    969                 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
    970
    971         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    972                 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
    973     }
    974
    975     @Test
    976     public void testExtrude_linePath_singleSegment_producesInfiniteRegion_extrudingOnPlus() {
    977         // arrange
    978         final LinePath path = LinePath.builder(TEST_PRECISION)
    979                 .append(Vector2D.ZERO)
    980                 .append(Vector2D.of(1, 1))
    981                 .build();
    982
    983         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    984                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    985         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    986
    987         // act
    988         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    989
    990         // assert
    991         Assert.assertEquals(3, boundaries.size());
    992
    993         final PlaneConvexSubset bottom = boundaries.get(0);
    994         Assert.assertTrue(bottom.isInfinite());
    995         Assert.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
    996         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
    997
    998         final PlaneConvexSubset top = boundaries.get(1);
    999         Assert.assertTrue(top.isInfinite());
    1000         Assert.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
    1001         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
    1002
    1003         final PlaneConvexSubset side = boundaries.get(2);
    1004         Assert.assertTrue(side.isInfinite());
    1005         Assert.assertTrue(side.getPlane().contains(Vector3D.ZERO));
    1006         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
    1007                 side.getPlane().getNormal(), TEST_EPS);
    1008
    1009         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    1010         Assert.assertFalse(tree.isFull());
    1011         Assert.assertTrue(tree.isInfinite());
    1012
    1013         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1014                 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
    1015
    1016         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    1017                 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
    1018
    1019         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1020                 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
    1021     }
    1022
    1023     @Test
    1024     public void testExtrude_linePath_singleSpan_producesInfiniteRegion() {
    1025         // arrange
    1026         final LinePath path = LinePath.from(Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).span());
    1027
    1028         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    1029                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1030         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    1031
    1032         // act
    1033         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    1034
    1035         // assert
    1036         Assert.assertEquals(3, boundaries.size());
    1037
    1038         final PlaneConvexSubset bottom = boundaries.get(0);
    1039         Assert.assertTrue(bottom.isInfinite());
    1040         Assert.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
    1041         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
    1042
    1043         final PlaneConvexSubset top = boundaries.get(1);
    1044         Assert.assertTrue(top.isInfinite());
    1045         Assert.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
    1046         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
    1047
    1048         final PlaneConvexSubset side = boundaries.get(2);
    1049         Assert.assertTrue(side.isInfinite());
    1050         Assert.assertTrue(side.getPlane().contains(Vector3D.ZERO));
    1051         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
    1052                 side.getPlane().getNormal(), TEST_EPS);
    1053
    1054         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    1055         Assert.assertFalse(tree.isFull());
    1056         Assert.assertTrue(tree.isInfinite());
    1057
    1058         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1059                 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
    1060
    1061         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    1062                 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
    1063
    1064         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1065                 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
    1066     }
    1067
    1068     @Test
    1069     public void testExtrude_linePath_intersectingInfiniteLines_extrudingOnPlus() {
    1070         // arrange
    1071         final Vector2D intersectionPt = Vector2D.of(1, 0);
    1072
    1073         final LinePath path = LinePath.from(
    1074                 Lines.fromPointAndAngle(intersectionPt, 0, TEST_PRECISION).reverseRayTo(intersectionPt),
    1075                 Lines.fromPointAndAngle(intersectionPt, PlaneAngleRadians.PI_OVER_TWO, TEST_PRECISION)
    1076                     .rayFrom(intersectionPt));
    1077
    1078         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    1079                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1080         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    1081
    1082         // act
    1083         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    1084
    1085         // assert
    1086         Assert.assertEquals(4, boundaries.size());
    1087
    1088         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    1089         Assert.assertFalse(tree.isFull());
    1090         Assert.assertTrue(tree.isInfinite());
    1091
    1092         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1093                 Vector3D.of(0, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(0, 2, 0), Vector3D.of(-1, 2, 0));
    1094
    1095         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    1096                 Vector3D.of(-1, 0, 0), Vector3D.of(0, 0, 0), Vector3D.of(1, 0, 0),
    1097                 Vector3D.of(1, 1, 0), Vector3D.of(1, 2, 0), Vector3D.of(-2, 2, 1),
    1098                 Vector3D.of(-2, 2, -1));
    1099
    1100         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1101                 Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0), Vector3D.of(3, 1, 0), Vector3D.of(3, -1, 0),
    1102                 Vector3D.of(-2, -2, -2), Vector3D.of(-2, -2, 2));
    1103     }
    1104
    1105     @Test
    1106     public void testExtrude_linePath_intersectingInfiniteLines_extrudingOnMinus() {
    1107         // arrange
    1108         final Vector2D intersectionPt = Vector2D.of(1, 0);
    1109
    1110         final LinePath path = LinePath.from(
    1111                 Lines.fromPointAndAngle(intersectionPt, 0, TEST_PRECISION).reverseRayTo(intersectionPt),
    1112                 Lines.fromPointAndAngle(intersectionPt, PlaneAngleRadians.PI_OVER_TWO, TEST_PRECISION)
    1113                     .rayFrom(intersectionPt));
    1114
    1115         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    1116                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1117         final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
    1118
    1119         // act
    1120         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    1121
    1122         // assert
    1123         Assert.assertEquals(4, boundaries.size());
    1124
    1125         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    1126         Assert.assertFalse(tree.isFull());
    1127         Assert.assertTrue(tree.isInfinite());
    1128
    1129         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1130                 Vector3D.of(0, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(0, 2, 0), Vector3D.of(-1, 2, 0));
    1131
    1132         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    1133                 Vector3D.of(-1, 0, 0), Vector3D.of(0, 0, 0), Vector3D.of(1, 0, 0),
    1134                 Vector3D.of(1, 1, 0), Vector3D.of(1, 2, 0), Vector3D.of(-2, 2, 1),
    1135                 Vector3D.of(-2, 2, -1));
    1136
    1137         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1138                 Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0), Vector3D.of(3, 1, 0), Vector3D.of(3, -1, 0),
    1139                 Vector3D.of(-2, -2, -2), Vector3D.of(-2, -2, 2));
    1140     }
    1141
    1142     @Test
    1143     public void testExtrude_linePath_infiniteNonConvex() {
    1144         // arrange
    1145         final LinePath path = LinePath.builder(TEST_PRECISION)
    1146                 .append(Vector2D.of(1, -5))
    1147                 .append(Vector2D.of(1, 1))
    1148                 .append(Vector2D.of(0, 0))
    1149                 .append(Vector2D.of(-1, 1))
    1150                 .append(Vector2D.of(-1, -5))
    1151                 .build();
    1152
    1153         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    1154                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1155         final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
    1156
    1157         // act
    1158         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    1159
    1160         // assert
    1161         Assert.assertEquals(8, boundaries.size());
    1162
    1163         final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
    1164         Assert.assertFalse(tree.isFull());
    1165         Assert.assertTrue(tree.isInfinite());
    1166
    1167         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
    1168                 Vector3D.of(0, -1, 0), Vector3D.of(0, -100, 0));
    1169
    1170         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
    1171                 Vector3D.of(-1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(1, 1, 0),
    1172                 Vector3D.of(-1, -100, 0), Vector3D.of(1, -100, 0),
    1173                 Vector3D.of(0, -100, 1), Vector3D.of(0, -100, -1));
    1174
    1175         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
    1176                 Vector3D.of(-2, 0, 0), Vector3D.of(2, 0, 0), Vector3D.of(0, 0.5, 0),
    1177                 Vector3D.of(0, -100, -2), Vector3D.of(0, -100, 2));
    1178     }
    1179
    1180     @Test
    1181     public void testExtrude_linePath_clockwiseWinding() {
    1182         // arrange
    1183         final LinePath path = LinePath.builder(TEST_PRECISION)
    1184                 .append(Vector2D.of(0, 1))
    1185                 .append(Vector2D.of(1, 0))
    1186                 .append(Vector2D.of(0, -1))
    1187                 .append(Vector2D.of(-1, 0))
    1188                 .close();
    1189
    1190         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    1191                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1192         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    1193
    1194         // act
    1195         final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
    1196
    1197         // assert
    1198         final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
    1199
    1200         Assert.assertTrue(resultTree.isInfinite());
    1201         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
    1202                 Vector3D.of(1, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0));
    1203         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE, Vector3D.ZERO);
    1204     }
    1205
    1206     @Test
    1207     public void testExtrude_region_empty() {
    1208         // arrange
    1209         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1210
    1211         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    1212                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1213         final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
    1214
    1215         // act
    1216         final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
    1217
    1218         // assert
    1219         Assert.assertEquals(0, boundaries.size());
    1220     }
    1221
    1222     @Test
    1223     public void testExtrude_region_full() {
    1224         // arrange
    1225         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    1226
    1227         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    1228                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1229         final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
    1230
    1231         // act
    1232         final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
    1233
    1234         // assert
    1235         Assert.assertEquals(2, boundaries.size());
    1236
    1237         Assert.assertTrue(boundaries.get(0).isFull());
    1238         Assert.assertTrue(boundaries.get(1).isFull());
    1239
    1240         final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
    1241
    1242         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
    1243                 Vector3D.of(1, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0));
    1244
    1245         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.BOUNDARY,
    1246                 Vector3D.of(1, 1, 1), Vector3D.of(-1, 1, 1), Vector3D.of(-1, -1, 1), Vector3D.of(1, -1, 1),
    1247                 Vector3D.of(1, 1, -1), Vector3D.of(-1, 1, -1), Vector3D.of(-1, -1, -1), Vector3D.of(1, -1, -1));
    1248
    1249         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE,
    1250                 Vector3D.of(1, 1, 2), Vector3D.of(-1, 1, 2), Vector3D.of(-1, -1, 2), Vector3D.of(1, -1, 2),
    1251                 Vector3D.of(1, 1, -2), Vector3D.of(-1, 1, -2), Vector3D.of(-1, -1, -2), Vector3D.of(1, -1, -2));
    1252     }
    1253
    1254     @Test
    1255     public void testExtrude_region_disjointRegions() {
    1256         // arrange
    1257         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1258         tree.insert(Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
    1259         tree.insert(Parallelogram.axisAligned(Vector2D.of(2, 2), Vector2D.of(3, 3), TEST_PRECISION));
    1260
    1261         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    1262                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1263         final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
    1264
    1265         // act
    1266         final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
    1267
    1268         // assert
    1269         Assert.assertEquals(12, boundaries.size());
    1270
    1271         final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
    1272
    1273         Assert.assertEquals(4, resultTree.getSize(), TEST_EPS);
    1274         Assert.assertEquals(20, resultTree.getBoundarySize(), TEST_EPS);
    1275         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1.5, 1.5, 0), resultTree.getCentroid(), TEST_EPS);
    1276
    1277         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
    1278                 Vector3D.of(0.5, 0.5, 0), Vector3D.of(2.5, 2.5, 0));
    1279
    1280         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.BOUNDARY,
    1281                 Vector3D.ZERO, Vector3D.of(1, 1, 0), Vector3D.of(2, 2, 0), Vector3D.of(3, 3, 0),
    1282                 Vector3D.of(0.5, 0.5, -1), Vector3D.of(0.5, 0.5, 1), Vector3D.of(2.5, 2.5, -1),
    1283                 Vector3D.of(2.5, 2.5, 1));
    1284
    1285         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE,
    1286                 Vector3D.of(-1, -1, 0), Vector3D.of(1.5, 1.5, 0), Vector3D.of(4, 4, 0),
    1287                 Vector3D.of(0.5, 0.5, -2), Vector3D.of(0.5, 0.5, 2), Vector3D.of(2.5, 2.5, -2),
    1288                 Vector3D.of(2.5, 2.5, 2));
    1289     }
    1290
    1291     @Test
    1292     public void testExtrude_region_starWithCutout() {
    1293         // arrange
    1294         // NOTE: this is pretty messed-up looking star :-)
    1295         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1296         tree.insert(LinePath.builder(TEST_PRECISION)
    1297                 .append(Vector2D.of(0, 4))
    1298                 .append(Vector2D.of(-1.5, 1))
    1299                 .append(Vector2D.of(-4, 1))
    1300                 .append(Vector2D.of(-2, -1))
    1301                 .append(Vector2D.of(-3, -4))
    1302                 .append(Vector2D.of(0, -2))
    1303                 .append(Vector2D.of(3, -4))
    1304                 .append(Vector2D.of(2, -1))
    1305                 .append(Vector2D.of(4, 1))
    1306                 .append(Vector2D.of(1.5, 1))
    1307                 .close());
    1308         tree.insert(LinePath.builder(TEST_PRECISION)
    1309                 .append(Vector2D.of(0, 1))
    1310                 .append(Vector2D.of(1, 0))
    1311                 .append(Vector2D.of(0, -1))
    1312                 .append(Vector2D.of(-1, 0))
    1313                 .close());
    1314
    1315         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
    1316                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1317         final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
    1318
    1319         // act
    1320         final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
    1321
    1322         // assert
    1323         final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
    1324
    1325         Assert.assertTrue(resultTree.isFinite());
    1326         EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE, resultTree.getCentroid());
    1327     }
    1328
    1329     @Test
    1330     public void testExtrude_invalidExtrusionVector() {
    1331         // arrange
    1332         final List<Vector2D> vertices = new ArrayList<>();
    1333         final LinePath path = LinePath.empty();
    1334         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1335
    1336         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
    1337                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    1338
    1339         final Pattern errorPattern = Pattern.compile("^Extrusion vector produces regions of zero size.*");
    1340
    1341         // act/assert
    1342         GeometryTestUtils.assertThrows(() -> {
    1343             Planes.extrudeVertexLoop(vertices, plane, Vector3D.of(1e-16, 0, 0), TEST_PRECISION);
    1344         }, IllegalArgumentException.class, errorPattern);
    1345         GeometryTestUtils.assertThrows(() -> {
    1346             Planes.extrudeVertexLoop(vertices, plane, Vector3D.of(4, 1e-16, 0), TEST_PRECISION);
    1347         }, IllegalArgumentException.class, errorPattern);
    1348         GeometryTestUtils.assertThrows(() -> {
    1349             Planes.extrudeVertexLoop(vertices, plane, Vector3D.of(1e-16, 5, 0), TEST_PRECISION);
    1350         }, IllegalArgumentException.class, errorPattern);
    1351
    1352         GeometryTestUtils.assertThrows(() -> {
    1353             Planes.extrude(path, plane, Vector3D.of(1e-16, 0, 0), TEST_PRECISION);
    1354         }, IllegalArgumentException.class, errorPattern);
    1355         GeometryTestUtils.assertThrows(() -> {
    1356             Planes.extrude(path, plane, Vector3D.of(4, 1e-16, 0), TEST_PRECISION);
    1357         }, IllegalArgumentException.class, errorPattern);
    1358         GeometryTestUtils.assertThrows(() -> {
    1359             Planes.extrude(path, plane, Vector3D.of(1e-16, 5, 0), TEST_PRECISION);
    1360         }, IllegalArgumentException.class, errorPattern);
    1361
    1362         GeometryTestUtils.assertThrows(() -> {
    1363             Planes.extrude(tree, plane, Vector3D.of(1e-16, 0, 0), TEST_PRECISION);
    1364         }, IllegalArgumentException.class, errorPattern);
    1365         GeometryTestUtils.assertThrows(() -> {
    1366             Planes.extrude(tree, plane, Vector3D.of(4, 1e-16, 0), TEST_PRECISION);
    1367         }, IllegalArgumentException.class, errorPattern);
    1368         GeometryTestUtils.assertThrows(() -> {
    1369             Planes.extrude(tree, plane, Vector3D.of(1e-16, 5, 0), TEST_PRECISION);
    1370         }, IllegalArgumentException.class, errorPattern);
    1371     }
    1372
    1373     private static void checkPlane(final Plane plane, final Vector3D origin, Vector3D u, Vector3D v) {
    1374         u = u.normalize();
    1375         v = v.normalize();
    1376         final Vector3D w = u.cross(v);
    1377
    1378         EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getOrigin(), TEST_EPS);
    1379         Assert.assertTrue(plane.contains(origin));
    1380
    1381         EuclideanTestUtils.assertCoordinatesEqual(w, plane.getNormal(), TEST_EPS);
    1382         Assert.assertEquals(1.0, plane.getNormal().norm(), TEST_EPS);
    1383
    1384         final double offset = plane.getOriginOffset();
    1385         Assert.assertEquals(Vector3D.ZERO.distance(plane.getOrigin()), Math.abs(offset), TEST_EPS);
    1386         EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getNormal().multiply(-offset), TEST_EPS);
    1387     }
    1388
    1389     private static void checkPoints(final PlaneConvexSubset sp, final RegionLocation loc, final Vector3D... pts) {
    1390         for (final Vector3D pt : pts) {
    1391             Assert.assertEquals("Unexpected location for point " + pt, loc, sp.classify(pt));
    1392         }
    1393     }
    1394
    1395     private static void assertConvexAreasEqual(final ConvexArea a, final ConvexArea b) {
    1396         final List<LineConvexSubset> aBoundaries = new ArrayList<>(a.getBoundaries());
    1397         final List<LineConvexSubset> bBoundaries = new ArrayList<>(b.getBoundaries());
    1398
    1399         Assert.assertEquals(aBoundaries.size(), bBoundaries.size());
    1400
    1401         for (final LineConvexSubset aBoundary : aBoundaries) {
    1402             if (!hasEquivalentSubLine(aBoundary, bBoundaries)) {
    1403                 Assert.fail("Failed to find equivalent subline for " + aBoundary);
    1404             }
    1405         }
    1406     }
    1407
    1408     private static boolean hasEquivalentSubLine(final LineConvexSubset target, final Collection<LineConvexSubset> subsets) {
    1409         final Line line = target.getLine();
    1410         final double start = target.getSubspaceStart();
    1411         final double end = target.getSubspaceEnd();
    1412
    1413         for (final LineConvexSubset subset : subsets) {
    1414             if (line.eq(subset.getLine(), TEST_PRECISION) &&
    1415                     TEST_PRECISION.eq(start, subset.getSubspaceStart()) &&
    1416                     TEST_PRECISION.eq(end, subset.getSubspaceEnd())) {
    1417                 return true;
    1418             }
    1419         }
    1420
    1421         return false;
    1422     }
    1423 }