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