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.twod;
    18
    19  import java.util.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.Collections;
    22  import java.util.Comparator;
    23  import java.util.List;
    24  import java.util.stream.Collectors;
    25
    26  import org.apache.commons.geometry.core.GeometryTestUtils;
    27  import org.apache.commons.geometry.core.Region;
    28  import org.apache.commons.geometry.core.RegionLocation;
    29  import org.apache.commons.geometry.core.partitioning.Split;
    30  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    31  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
    32  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    33  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.PartitionedRegionBuilder2D;
    34  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.RegionNode2D;
    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 RegionBSPTree2DTest {
    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      private static final Comparator<LineConvexSubset> SEGMENT_COMPARATOR =
    50          (a, b) -> Vector2D.COORDINATE_ASCENDING_ORDER.compare(a.getStartPoint(), b.getStartPoint());
    51
    52      private static final Line X_AXIS = Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
    53
    54      private static final Line Y_AXIS = Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION);
    55
    56      @Test
    57      void testCtor_booleanArg_true() {
    58          // act
    59          final RegionBSPTree2D tree = new RegionBSPTree2D(true);
    60
    61          // assert
    62          Assertions.assertTrue(tree.isFull());
    63          Assertions.assertFalse(tree.isEmpty());
    64          Assertions.assertEquals(1, tree.count());
    65      }
    66
    67      @Test
    68      void testCtor_booleanArg_false() {
    69          // act
    70          final RegionBSPTree2D tree = new RegionBSPTree2D(false);
    71
    72          // assert
    73          Assertions.assertFalse(tree.isFull());
    74          Assertions.assertTrue(tree.isEmpty());
    75          Assertions.assertEquals(1, tree.count());
    76      }
    77
    78      @Test
    79      void testCtor_default() {
    80          // act
    81          final RegionBSPTree2D tree = new RegionBSPTree2D();
    82
    83          // assert
    84          Assertions.assertFalse(tree.isFull());
    85          Assertions.assertTrue(tree.isEmpty());
    86          Assertions.assertEquals(1, tree.count());
    87      }
    88
    89      @Test
    90      void testFull_factoryMethod() {
    91          // act
    92          final RegionBSPTree2D tree = RegionBSPTree2D.full();
    93
    94          // assert
    95          Assertions.assertTrue(tree.isFull());
    96          Assertions.assertFalse(tree.isEmpty());
    97          Assertions.assertEquals(1, tree.count());
    98      }
    99
    100     @Test
    101     void testEmpty_factoryMethod() {
    102         // act
    103         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    104
    105         // assert
    106         Assertions.assertFalse(tree.isFull());
    107         Assertions.assertTrue(tree.isEmpty());
    108         Assertions.assertEquals(1, tree.count());
    109     }
    110
    111     @Test
    112     void testPartitionedRegionBuilder_halfSpace() {
    113         // act
    114         final RegionBSPTree2D tree = RegionBSPTree2D.partitionedRegionBuilder()
    115                 .insertPartition(
    116                     Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION))
    117                 .insertBoundary(
    118                     Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.MINUS_X, TEST_PRECISION).span())
    119                 .build();
    120
    121         // assert
    122         Assertions.assertFalse(tree.isFull());
    123         Assertions.assertTrue(tree.isInfinite());
    124
    125         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector2D.of(0, -1));
    126         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, Vector2D.ZERO);
    127         EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE, Vector2D.of(0, 1));
    128     }
    129
    130     @Test
    131     void testPartitionedRegionBuilder_square() {
    132         // arrange
    133         final Parallelogram square = Parallelogram.unitSquare(TEST_PRECISION);
    134         final List<LineConvexSubset> boundaries = square.getBoundaries();
    135
    136         final Vector2D lowerBound = Vector2D.of(-2, -2);
    137
    138         final int maxUpper = 5;
    139         final int maxLevel = 4;
    140
    141         // act/assert
    142         Bounds2D bounds;
    143         for (int u = 0; u <= maxUpper; ++u) {
    144             for (int level = 0; level <= maxLevel; ++level) {
    145                 bounds = Bounds2D.from(lowerBound, Vector2D.of(u, u));
    146
    147                 checkFinitePartitionedRegion(bounds, level, square);
    148                 checkFinitePartitionedRegion(bounds, level, boundaries);
    149             }
    150         }
    151     }
    152
    153     @Test
    154     void testPartitionedRegionBuilder_nonConvex() {
    155         // arrange
    156         final RegionBSPTree2D src = Parallelogram.unitSquare(TEST_PRECISION).toTree();
    157         src.union(Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).toTree());
    158
    159         final List<LineConvexSubset> boundaries = src.getBoundaries();
    160
    161         final Vector2D lowerBound = Vector2D.of(-2, -2);
    162
    163         final int maxUpper = 5;
    164         final int maxLevel = 4;
    165
    166         // act/assert
    167         Bounds2D bounds;
    168         for (int u = 0; u <= maxUpper; ++u) {
    169             for (int level = 0; level <= maxLevel; ++level) {
    170                 bounds = Bounds2D.from(lowerBound, Vector2D.of(u, u));
    171
    172                 checkFinitePartitionedRegion(bounds, level, src);
    173                 checkFinitePartitionedRegion(bounds, level, boundaries);
    174             }
    175         }
    176     }
    177
    178     /** Check that a partitioned BSP tree behaves the same as a non-partitioned tree when
    179      * constructed with the given boundary source.
    180      * @param bounds
    181      * @param level
    182      * @param src
    183      */
    184     private void checkFinitePartitionedRegion(final Bounds2D bounds, final int level, final BoundarySource2D src) {
    185         // arrange
    186         final String msg = "Partitioned region check failed with bounds= " + bounds + " and level= " + level;
    187
    188         final RegionBSPTree2D standard = RegionBSPTree2D.from(src.boundaryStream().collect(Collectors.toList()));
    189
    190         // act
    191         final RegionBSPTree2D partitioned = RegionBSPTree2D.partitionedRegionBuilder()
    192                 .insertAxisAlignedGrid(bounds, level, TEST_PRECISION)
    193                 .insertBoundaries(src)
    194                 .build();
    195
    196         // assert
    197         Assertions.assertEquals(standard.getSize(), partitioned.getSize(), TEST_EPS, msg);
    198         Assertions.assertEquals(standard.getBoundarySize(), partitioned.getBoundarySize(), TEST_EPS, msg);
    199         EuclideanTestUtils.assertCoordinatesEqual(standard.getCentroid(), partitioned.getCentroid(), TEST_EPS);
    200
    201         final RegionBSPTree2D diff = RegionBSPTree2D.empty();
    202         diff.difference(partitioned, standard);
    203         Assertions.assertTrue(diff.isEmpty(), msg);
    204     }
    205
    206     /** Check that a partitioned BSP tree behaves the same as a non-partitioned tree when
    207      * constructed with the given boundaries.
    208      * @param bounds
    209      * @param level
    210      * @param boundaries
    211      */
    212     private void checkFinitePartitionedRegion(final Bounds2D bounds, final int level,
    213                                               final List<? extends LineConvexSubset> boundaries) {
    214         // arrange
    215         final String msg = "Partitioned region check failed with bounds= " + bounds + " and level= " + level;
    216
    217         final RegionBSPTree2D standard = RegionBSPTree2D.from(boundaries);
    218
    219         // act
    220         final RegionBSPTree2D partitioned = RegionBSPTree2D.partitionedRegionBuilder()
    221                 .insertAxisAlignedGrid(bounds, level, TEST_PRECISION)
    222                 .insertBoundaries(boundaries)
    223                 .build();
    224
    225         // assert
    226         Assertions.assertEquals(standard.getSize(), partitioned.getSize(), TEST_EPS, msg);
    227         Assertions.assertEquals(standard.getBoundarySize(), partitioned.getBoundarySize(), TEST_EPS, msg);
    228         EuclideanTestUtils.assertCoordinatesEqual(standard.getCentroid(), partitioned.getCentroid(), TEST_EPS);
    229
    230         final RegionBSPTree2D diff = RegionBSPTree2D.empty();
    231         diff.difference(partitioned, standard);
    232         Assertions.assertTrue(diff.isEmpty(), msg);
    233     }
    234
    235     @Test
    236     void testPartitionedRegionBuilder_insertPartitionAfterBoundary() {
    237         // arrange
    238         final PartitionedRegionBuilder2D builder = RegionBSPTree2D.partitionedRegionBuilder();
    239         builder.insertBoundary(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 0), TEST_PRECISION));
    240
    241         final Line partition = Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION);
    242
    243         final String msg = "Cannot insert partitions after boundaries have been inserted";
    244
    245         // act/assert
    246         GeometryTestUtils.assertThrowsWithMessage(() -> {
    247             builder.insertPartition(partition);
    248         }, IllegalStateException.class, msg);
    249
    250         GeometryTestUtils.assertThrowsWithMessage(() -> {
    251             builder.insertPartition(partition.span());
    252         }, IllegalStateException.class, msg);
    253
    254         GeometryTestUtils.assertThrowsWithMessage(() -> {
    255             builder.insertAxisAlignedPartitions(Vector2D.ZERO, TEST_PRECISION);
    256         }, IllegalStateException.class, msg);
    257
    258         GeometryTestUtils.assertThrowsWithMessage(() -> {
    259             builder.insertAxisAlignedGrid(Bounds2D.from(Vector2D.ZERO, Vector2D.of(1, 1)), 1, TEST_PRECISION);
    260         }, IllegalStateException.class, msg);
    261     }
    262
    263     @Test
    264     void testCopy() {
    265         // arrange
    266         final RegionBSPTree2D tree = new RegionBSPTree2D(true);
    267         tree.getRoot().cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
    268
    269         // act
    270         final RegionBSPTree2D copy = tree.copy();
    271
    272         // assert
    273         Assertions.assertNotSame(tree, copy);
    274         Assertions.assertEquals(3, copy.count());
    275     }
    276
    277     @Test
    278     void testBoundaries() {
    279         // arrange
    280         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
    281                 .toTree();
    282
    283         // act
    284         final List<LineConvexSubset> segments = new ArrayList<>();
    285         tree.boundaries().forEach(segments::add);
    286
    287         // assert
    288         Assertions.assertEquals(4, segments.size());
    289     }
    290
    291     @Test
    292     void testGetBoundaries() {
    293         // arrange
    294         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
    295                 .toTree();
    296
    297         // act
    298         final List<LineConvexSubset> segments = tree.getBoundaries();
    299
    300         // assert
    301         Assertions.assertEquals(4, segments.size());
    302     }
    303
    304     @Test
    305     void testBoundaryStream() {
    306         // arrange
    307         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
    308                 .toTree();
    309
    310         // act
    311         final List<LineConvexSubset> segments = tree.boundaryStream().collect(Collectors.toList());
    312
    313         // assert
    314         Assertions.assertEquals(4, segments.size());
    315     }
    316
    317     @Test
    318     void testBoundaryStream_noBoundaries() {
    319         // arrange
    320         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    321
    322         // act
    323         final List<LineConvexSubset> segments = tree.boundaryStream().collect(Collectors.toList());
    324
    325         // assert
    326         Assertions.assertEquals(0, segments.size());
    327     }
    328
    329     @Test
    330     void testGetBounds_hasBounds() {
    331         // arrange
    332         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.of(2, 3), Vector2D.of(5, 8), TEST_PRECISION)
    333                 .toTree();
    334
    335         // act
    336         final Bounds2D bounds = tree.getBounds();
    337
    338         // assert
    339         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 3), bounds.getMin(), TEST_EPS);
    340         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(5, 8), bounds.getMax(), TEST_EPS);
    341     }
    342
    343     @Test
    344     void testGetBounds_noBounds() {
    345         // act/assert
    346         Assertions.assertNull(RegionBSPTree2D.empty().getBounds());
    347         Assertions.assertNull(RegionBSPTree2D.full().getBounds());
    348
    349         final RegionBSPTree2D halfFull = RegionBSPTree2D.empty();
    350         halfFull.getRoot().insertCut(Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION));
    351         Assertions.assertNull(halfFull.getBounds());
    352     }
    353
    354     @Test
    355     void testGetBoundaryPaths_cachesResult() {
    356         // arrange
    357         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    358         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    359
    360         // act
    361         final List<LinePath> a = tree.getBoundaryPaths();
    362         final List<LinePath> b = tree.getBoundaryPaths();
    363
    364         // assert
    365         Assertions.assertSame(a, b);
    366     }
    367
    368     @Test
    369     void testGetBoundaryPaths_recomputesResultOnChange() {
    370         // arrange
    371         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    372         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    373
    374         // act
    375         final List<LinePath> a = tree.getBoundaryPaths();
    376         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION));
    377         final List<LinePath> b = tree.getBoundaryPaths();
    378
    379         // assert
    380         Assertions.assertNotSame(a, b);
    381     }
    382
    383     @Test
    384     void testGetBoundaryPaths_isUnmodifiable() {
    385         // arrange
    386         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    387         tree.insert(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    388
    389         // act/assert
    390         Assertions.assertThrows(UnsupportedOperationException.class, () -> tree.getBoundaryPaths().add(LinePath.builder(null).build()));
    391     }
    392
    393     @Test
    394     void testAdd_convexArea() {
    395         // arrange
    396         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    397
    398         // act
    399         tree.add(ConvexArea.convexPolygonFromVertices(Arrays.asList(
    400                     Vector2D.ZERO, Vector2D.of(2, 0),
    401                     Vector2D.of(2, 2), Vector2D.of(0, 2)
    402                 ), TEST_PRECISION));
    403         tree.add(ConvexArea.convexPolygonFromVertices(Arrays.asList(
    404                 Vector2D.of(1, 1), Vector2D.of(3, 1),
    405                 Vector2D.of(3, 3), Vector2D.of(1, 3)
    406             ), TEST_PRECISION));
    407
    408         // assert
    409         Assertions.assertFalse(tree.isFull());
    410         Assertions.assertFalse(tree.isEmpty());
    411
    412         Assertions.assertEquals(7, tree.getSize(), TEST_EPS);
    413         Assertions.assertEquals(12, tree.getBoundarySize(), TEST_EPS);
    414         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 1.5), tree.getCentroid(), TEST_EPS);
    415
    416         checkClassify(tree, RegionLocation.INSIDE,
    417                 Vector2D.of(1, 1), Vector2D.of(1.5, 1.5), Vector2D.of(2, 2));
    418     }
    419
    420     @Test
    421     void testToConvex_full() {
    422         // arrange
    423         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    424
    425         // act
    426         final List<ConvexArea> result = tree.toConvex();
    427
    428         // assert
    429         Assertions.assertEquals(1, result.size());
    430         Assertions.assertTrue(result.get(0).isFull());
    431     }
    432
    433     @Test
    434     void testToConvex_empty() {
    435         // arrange
    436         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    437
    438         // act
    439         final List<ConvexArea> result = tree.toConvex();
    440
    441         // assert
    442         Assertions.assertEquals(0, result.size());
    443     }
    444
    445     @Test
    446     void testToConvex_halfSpace() {
    447         // arrange
    448         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    449         tree.getRoot().insertCut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
    450
    451         // act
    452         final List<ConvexArea> result = tree.toConvex();
    453
    454         // assert
    455         Assertions.assertEquals(1, result.size());
    456
    457         final ConvexArea area = result.get(0);
    458         Assertions.assertFalse(area.isFull());
    459         Assertions.assertFalse(area.isEmpty());
    460
    461         checkClassify(area, RegionLocation.INSIDE, Vector2D.of(0, 1));
    462         checkClassify(area, RegionLocation.BOUNDARY, Vector2D.ZERO);
    463         checkClassify(area, RegionLocation.OUTSIDE, Vector2D.of(0, -1));
    464     }
    465
    466     @Test
    467     void testToConvex_quadrantComplement() {
    468         // arrange
    469         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    470         tree.getRoot().cut(Lines.fromPointAndAngle(Vector2D.ZERO, Math.PI, TEST_PRECISION))
    471             .getPlus().cut(Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION));
    472
    473         tree.complement();
    474
    475         // act
    476         final List<ConvexArea> result = tree.toConvex();
    477
    478         // assert
    479         Assertions.assertEquals(1, result.size());
    480
    481         final ConvexArea area = result.get(0);
    482         Assertions.assertFalse(area.isFull());
    483         Assertions.assertFalse(area.isEmpty());
    484
    485         checkClassify(area, RegionLocation.INSIDE, Vector2D.of(1, 1));
    486         checkClassify(area, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1));
    487         checkClassify(area, RegionLocation.OUTSIDE, Vector2D.of(1, -1), Vector2D.of(-1, -1), Vector2D.of(-1, 1));
    488     }
    489
    490     @Test
    491     void testToConvex_square() {
    492         // arrange
    493         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).toTree();
    494
    495         // act
    496         final List<ConvexArea> result = tree.toConvex();
    497
    498         // assert
    499         Assertions.assertEquals(1, result.size());
    500
    501         final ConvexArea area = result.get(0);
    502         Assertions.assertFalse(area.isFull());
    503         Assertions.assertFalse(area.isEmpty());
    504
    505         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
    506         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
    507
    508         checkClassify(area, RegionLocation.INSIDE, Vector2D.of(0.5, 0.5));
    509         checkClassify(area, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 1));
    510         checkClassify(area, RegionLocation.OUTSIDE,
    511                 Vector2D.of(0.5, -1), Vector2D.of(0.5, 2),
    512                 Vector2D.of(-1, 0.5), Vector2D.of(2, 0.5));
    513     }
    514
    515     @Test
    516     void testToConvex_multipleConvexAreas() {
    517         // arrange
    518         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    519         tree.insert(Arrays.asList(
    520                     Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION),
    521
    522                     Lines.segmentFromPoints(Vector2D.of(1, 1), Vector2D.of(0, 1), TEST_PRECISION),
    523                     Lines.segmentFromPoints(Vector2D.of(0, 1), Vector2D.ZERO, TEST_PRECISION),
    524
    525                     Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 0), TEST_PRECISION),
    526                     Lines.segmentFromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), TEST_PRECISION)
    527                 ));
    528
    529         // act
    530         final List<ConvexArea> result = tree.toConvex();
    531
    532         // assert
    533         result.sort((a, b) ->
    534                 Vector2D.COORDINATE_ASCENDING_ORDER.compare(a.getCentroid(), b.getCentroid()));
    535
    536         Assertions.assertEquals(2, result.size());
    537
    538         final ConvexArea firstArea = result.get(0);
    539         Assertions.assertFalse(firstArea.isFull());
    540         Assertions.assertFalse(firstArea.isEmpty());
    541
    542         Assertions.assertEquals(0.5, firstArea.getSize(), TEST_EPS);
    543         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.0 / 3.0, 2.0 / 3.0), firstArea.getCentroid(), TEST_EPS);
    544
    545         checkClassify(firstArea, RegionLocation.INSIDE, Vector2D.of(1.0 / 3.0, 2.0 / 3.0));
    546         checkClassify(firstArea, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 1), Vector2D.of(0.5, 0.5));
    547         checkClassify(firstArea, RegionLocation.OUTSIDE,
    548                 Vector2D.of(0.25, -1), Vector2D.of(0.25, 2),
    549                 Vector2D.of(-1, 0.5), Vector2D.of(0.75, 0.5));
    550
    551         final ConvexArea secondArea = result.get(1);
    552         Assertions.assertFalse(secondArea.isFull());
    553         Assertions.assertFalse(secondArea.isEmpty());
    554
    555         Assertions.assertEquals(0.5, secondArea.getSize(), TEST_EPS);
    556         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2.0 / 3.0, 1.0 / 3.0), secondArea.getCentroid(), TEST_EPS);
    557
    558         checkClassify(secondArea, RegionLocation.INSIDE, Vector2D.of(2.0 / 3.0, 1.0 / 3.0));
    559         checkClassify(secondArea, RegionLocation.BOUNDARY, Vector2D.ZERO, Vector2D.of(1, 1), Vector2D.of(0.5, 0.5));
    560         checkClassify(secondArea, RegionLocation.OUTSIDE,
    561                 Vector2D.of(0.75, -1), Vector2D.of(0.75, 2),
    562                 Vector2D.of(2, 0.5), Vector2D.of(0.25, 0.5));
    563     }
    564
    565     @Test
    566     void testGetNodeRegion() {
    567         // arrange
    568         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    569
    570         final RegionNode2D root = tree.getRoot();
    571         root.cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
    572
    573         final RegionNode2D minus = root.getMinus();
    574         minus.cut(Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION));
    575
    576         final Vector2D origin = Vector2D.ZERO;
    577
    578         final Vector2D a = Vector2D.of(1, 0);
    579         final Vector2D b = Vector2D.of(1, 1);
    580         final Vector2D c = Vector2D.of(0, 1);
    581         final Vector2D d = Vector2D.of(-1, 1);
    582         final Vector2D e = Vector2D.of(-1, 0);
    583         final Vector2D f = Vector2D.of(-1, -1);
    584         final Vector2D g = Vector2D.of(0, -1);
    585         final Vector2D h = Vector2D.of(1, -1);
    586
    587         // act/assert
    588         checkConvexArea(root.getNodeRegion(), Arrays.asList(origin, a, b, c, d, e, f, g, h), Collections.emptyList());
    589
    590         checkConvexArea(minus.getNodeRegion(), Arrays.asList(b, c, d), Arrays.asList(f, g, h));
    591         checkConvexArea(root.getPlus().getNodeRegion(), Arrays.asList(f, g, h), Arrays.asList(b, c, d));
    592
    593         checkConvexArea(minus.getMinus().getNodeRegion(), Collections.singletonList(d), Arrays.asList(a, b, f, g, h));
    594         checkConvexArea(minus.getPlus().getNodeRegion(), Collections.singletonList(b), Arrays.asList(d, e, f, g, h));
    595     }
    596
    597     @Test
    598     void testSplit_full() {
    599         // arrange
    600         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    601
    602         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.25 * Math.PI, TEST_PRECISION);
    603
    604         // act
    605         final Split<RegionBSPTree2D> split = tree.split(splitter);
    606
    607         // assert
    608         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    609
    610         checkClassify(split.getMinus(), RegionLocation.INSIDE, Vector2D.of(0, 1));
    611         checkClassify(split.getMinus(), RegionLocation.OUTSIDE, Vector2D.of(1, -1));
    612
    613         final List<LinePath> minusBoundaryList = split.getMinus().getBoundaryPaths();
    614         Assertions.assertEquals(1, minusBoundaryList.size());
    615
    616         final LinePath minusBoundary = minusBoundaryList.get(0);
    617         Assertions.assertEquals(1, minusBoundary.getElements().size());
    618         Assertions.assertTrue(minusBoundary.isInfinite());
    619         Assertions.assertSame(splitter, minusBoundary.getStart().getLine());
    620
    621         checkClassify(split.getPlus(), RegionLocation.OUTSIDE, Vector2D.of(0, 1));
    622         checkClassify(split.getPlus(), RegionLocation.INSIDE, Vector2D.of(1, -1));
    623
    624         final List<LinePath> plusBoundaryList = split.getPlus().getBoundaryPaths();
    625         Assertions.assertEquals(1, plusBoundaryList.size());
    626
    627         final LinePath plusBoundary = minusBoundaryList.get(0);
    628         Assertions.assertEquals(1, plusBoundary.getElements().size());
    629         Assertions.assertTrue(plusBoundary.isInfinite());
    630         Assertions.assertSame(splitter, plusBoundary.getStart().getLine());
    631     }
    632
    633     @Test
    634     void testSplit_empty() {
    635         // arrange
    636         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    637
    638         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.25 * Math.PI, TEST_PRECISION);
    639
    640         // act
    641         final Split<RegionBSPTree2D> split = tree.split(splitter);
    642
    643         // assert
    644         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
    645
    646         Assertions.assertNull(split.getMinus());
    647         Assertions.assertNull(split.getPlus());
    648     }
    649
    650     @Test
    651     void testSplit_bothSides() {
    652         // arrange
    653         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), TEST_PRECISION)
    654                 .toTree();
    655
    656         final Line splitter = Lines.fromPointAndAngle(Vector2D.ZERO, 0.25 * Math.PI, TEST_PRECISION);
    657
    658         // act
    659         final Split<RegionBSPTree2D> split = tree.split(splitter);
    660
    661         // assert
    662         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    663
    664         final List<LinePath> minusPath = split.getMinus().getBoundaryPaths();
    665         Assertions.assertEquals(1, minusPath.size());
    666         checkVertices(minusPath.get(0), Vector2D.ZERO, Vector2D.of(1, 1),
    667                 Vector2D.of(0, 1), Vector2D.ZERO);
    668
    669         final List<LinePath> plusPath = split.getPlus().getBoundaryPaths();
    670         Assertions.assertEquals(1, plusPath.size());
    671         checkVertices(plusPath.get(0), Vector2D.ZERO, Vector2D.of(2, 0),
    672                 Vector2D.of(2, 1), Vector2D.of(1, 1), Vector2D.ZERO);
    673     }
    674
    675     @Test
    676     void testSplit_plusSideOnly() {
    677         // arrange
    678         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), TEST_PRECISION)
    679                 .toTree();
    680
    681         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.25 * Math.PI, TEST_PRECISION);
    682
    683         // act
    684         final Split<RegionBSPTree2D> split = tree.split(splitter);
    685
    686         // assert
    687         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    688
    689         Assertions.assertNull(split.getMinus());
    690
    691         final List<LinePath> plusPath = split.getPlus().getBoundaryPaths();
    692         Assertions.assertEquals(1, plusPath.size());
    693         checkVertices(plusPath.get(0), Vector2D.ZERO, Vector2D.of(2, 0),
    694                 Vector2D.of(2, 1), Vector2D.of(0, 1), Vector2D.ZERO);
    695     }
    696
    697     @Test
    698     void testSplit_minusSideOnly() {
    699         // arrange
    700         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), TEST_PRECISION)
    701                 .toTree();
    702
    703         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.25 * Math.PI, TEST_PRECISION)
    704                 .reverse();
    705
    706         // act
    707         final Split<RegionBSPTree2D> split = tree.split(splitter);
    708
    709         // assert
    710         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    711
    712         final List<LinePath> minusPath = split.getMinus().getBoundaryPaths();
    713         Assertions.assertEquals(1, minusPath.size());
    714         checkVertices(minusPath.get(0), Vector2D.ZERO, Vector2D.of(2, 0),
    715                 Vector2D.of(2, 1), Vector2D.of(0, 1), Vector2D.ZERO);
    716
    717         Assertions.assertNull(split.getPlus());
    718     }
    719
    720     @Test
    721     void testGeometricProperties_full() {
    722         // arrange
    723         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    724
    725         // act/assert
    726         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    727         Assertions.assertNull(tree.getCentroid());
    728
    729         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    730
    731         Assertions.assertEquals(0, tree.getBoundaries().size());
    732         Assertions.assertEquals(0, tree.getBoundaryPaths().size());
    733     }
    734
    735     @Test
    736     void testGeometricProperties_empty() {
    737         // arrange
    738         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    739
    740         // act/assert
    741         Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
    742         Assertions.assertNull(tree.getCentroid());
    743
    744         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    745
    746         Assertions.assertEquals(0, tree.getBoundaries().size());
    747         Assertions.assertEquals(0, tree.getBoundaryPaths().size());
    748     }
    749
    750     @Test
    751     void testGeometricProperties_halfSpace() {
    752         // arrange
    753         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    754         tree.getRoot().cut(X_AXIS);
    755
    756         // act/assert
    757         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    758         Assertions.assertNull(tree.getCentroid());
    759
    760         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
    761
    762         final List<LineConvexSubset> segments = tree.getBoundaries();
    763         Assertions.assertEquals(1, segments.size());
    764
    765         final LineConvexSubset segment = segments.get(0);
    766         Assertions.assertSame(X_AXIS, segment.getLine());
    767         Assertions.assertNull(segment.getStartPoint());
    768         Assertions.assertNull(segment.getEndPoint());
    769
    770         final List<LinePath> paths = tree.getBoundaryPaths();
    771         Assertions.assertEquals(1, paths.size());
    772
    773         final LinePath path = paths.get(0);
    774         Assertions.assertEquals(1, path.getElements().size());
    775         assertSegmentsEqual(segment, path.getStart());
    776     }
    777
    778     @Test
    779     void testGeometricProperties_complementedHalfSpace() {
    780         // arrange
    781         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    782         tree.getRoot().cut(X_AXIS);
    783
    784         tree.complement();
    785
    786         // act/assert
    787         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    788         Assertions.assertNull(tree.getCentroid());
    789
    790         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
    791
    792         final List<LineConvexSubset> segments = tree.getBoundaries();
    793         Assertions.assertEquals(1, segments.size());
    794
    795         final LineConvexSubset segment = segments.get(0);
    796         Assertions.assertEquals(X_AXIS.reverse(), segment.getLine());
    797         Assertions.assertNull(segment.getStartPoint());
    798         Assertions.assertNull(segment.getEndPoint());
    799
    800         final List<LinePath> paths = tree.getBoundaryPaths();
    801         Assertions.assertEquals(1, paths.size());
    802
    803         final LinePath path = paths.get(0);
    804         Assertions.assertEquals(1, path.getElements().size());
    805         assertSegmentsEqual(segment, path.getElements().get(0));
    806     }
    807
    808     @Test
    809     void testGeometricProperties_quadrant() {
    810         // arrange
    811         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    812         tree.getRoot().cut(X_AXIS)
    813             .getMinus().cut(Y_AXIS);
    814
    815         // act/assert
    816         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    817         Assertions.assertNull(tree.getCentroid());
    818
    819         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
    820
    821         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
    822         Assertions.assertEquals(2, segments.size());
    823
    824         segments.sort(SEGMENT_COMPARATOR);
    825
    826         final LineConvexSubset firstSegment = segments.get(0);
    827         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, firstSegment.getStartPoint(), TEST_EPS);
    828         Assertions.assertNull(firstSegment.getEndPoint());
    829         Assertions.assertSame(Y_AXIS, firstSegment.getLine());
    830
    831         final LineConvexSubset secondSegment = segments.get(1);
    832         Assertions.assertNull(secondSegment.getStartPoint());
    833         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, secondSegment.getEndPoint(), TEST_EPS);
    834         Assertions.assertSame(X_AXIS, secondSegment.getLine());
    835
    836         final List<LinePath> paths = tree.getBoundaryPaths();
    837         Assertions.assertEquals(1, paths.size());
    838
    839         final LinePath path = paths.get(0);
    840         Assertions.assertEquals(2, path.getElements().size());
    841         assertSegmentsEqual(secondSegment, path.getElements().get(0));
    842         assertSegmentsEqual(firstSegment, path.getElements().get(1));
    843     }
    844
    845     @Test
    846     void testGeometricProperties_mixedCutRule() {
    847         // arrange
    848         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    849
    850         tree.getRoot().cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.25 * Math.PI, TEST_PRECISION),
    851                 RegionCutRule.INHERIT);
    852
    853         tree.getRoot()
    854             .getPlus().cut(X_AXIS, RegionCutRule.MINUS_INSIDE)
    855                 .getMinus().cut(Lines.fromPointAndAngle(Vector2D.of(1, 0), 0.5 * Math.PI, TEST_PRECISION));
    856
    857         tree.getRoot()
    858             .getMinus().cut(Lines.fromPointAndAngle(Vector2D.ZERO, 0.5 * Math.PI, TEST_PRECISION), RegionCutRule.PLUS_INSIDE)
    859                 .getPlus().cut(Lines.fromPointAndAngle(Vector2D.of(1, 1), Math.PI, TEST_PRECISION))
    860                     .getMinus().cut(Lines.fromPointAndAngle(Vector2D.of(0.5, 0.5), 0.75 * Math.PI, TEST_PRECISION), RegionCutRule.INHERIT);
    861
    862         // act/assert
    863         Assertions.assertEquals(1, tree.getSize(), TEST_EPS);
    864         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), tree.getCentroid(), TEST_EPS);
    865
    866         Assertions.assertEquals(4, tree.getBoundarySize(), TEST_EPS);
    867
    868         final List<LinePath> paths = tree.getBoundaryPaths();
    869         Assertions.assertEquals(1, paths.size());
    870
    871         final LinePath path = paths.get(0);
    872         Assertions.assertEquals(4, path.getElements().size());
    873
    874         final List<Vector2D> vertices = path.getVertexSequence();
    875         Assertions.assertEquals(5, vertices.size());
    876         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(0), TEST_EPS);
    877         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), vertices.get(1), TEST_EPS);
    878         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), vertices.get(2), TEST_EPS);
    879         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 1), vertices.get(3), TEST_EPS);
    880         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(4), TEST_EPS);
    881     }
    882
    883     @Test
    884     void testGeometricProperties_complementedQuadrant() {
    885         // arrange
    886         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    887         tree.getRoot().cut(X_AXIS)
    888             .getMinus().cut(Y_AXIS);
    889
    890         tree.complement();
    891
    892         // act/assert
    893         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    894         Assertions.assertNull(tree.getCentroid());
    895
    896         GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
    897
    898         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
    899         Assertions.assertEquals(2, segments.size());
    900
    901         segments.sort(SEGMENT_COMPARATOR);
    902
    903         final LineConvexSubset firstSegment = segments.get(0);
    904         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, firstSegment.getStartPoint(), TEST_EPS);
    905         Assertions.assertNull(firstSegment.getEndPoint());
    906         Assertions.assertEquals(X_AXIS.reverse(), firstSegment.getLine());
    907
    908         final LineConvexSubset secondSegment = segments.get(1);
    909         Assertions.assertNull(secondSegment.getStartPoint());
    910         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, secondSegment.getEndPoint(), TEST_EPS);
    911         Assertions.assertEquals(Y_AXIS.reverse(), secondSegment.getLine());
    912
    913         final List<LinePath> paths = tree.getBoundaryPaths();
    914         Assertions.assertEquals(1, paths.size());
    915
    916         final LinePath path = paths.get(0);
    917         Assertions.assertEquals(2, path.getElements().size());
    918         assertSegmentsEqual(secondSegment, path.getElements().get(0));
    919         assertSegmentsEqual(firstSegment, path.getElements().get(1));
    920     }
    921
    922     @Test
    923     void testGeometricProperties_closedRegion() {
    924         // arrange
    925         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    926         tree.insert(LinePath.builder(TEST_PRECISION)
    927                 .appendVertices(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(2, 1))
    928                 .close());
    929
    930         // act/assert
    931         Assertions.assertEquals(0.5, tree.getSize(), TEST_EPS);
    932         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1.0 / 3.0), tree.getCentroid(), TEST_EPS);
    933
    934         Assertions.assertEquals(1.0 + Math.sqrt(2) + Math.sqrt(5), tree.getBoundarySize(), TEST_EPS);
    935
    936         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
    937         segments.sort(SEGMENT_COMPARATOR);
    938
    939         Assertions.assertEquals(3, segments.size());
    940
    941         checkFiniteSegment(segments.get(0), Vector2D.ZERO, Vector2D.of(1, 0));
    942         checkFiniteSegment(segments.get(1), Vector2D.of(1, 0), Vector2D.of(2, 1));
    943         checkFiniteSegment(segments.get(2), Vector2D.of(2, 1), Vector2D.ZERO);
    944
    945         final List<LinePath> paths = tree.getBoundaryPaths();
    946         Assertions.assertEquals(1, paths.size());
    947
    948         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(2, 1), Vector2D.ZERO);
    949     }
    950
    951     @Test
    952     void testGeometricProperties_complementedClosedRegion() {
    953         // arrange
    954         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    955         tree.insert(LinePath.builder(TEST_PRECISION)
    956                 .appendVertices(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(2, 1))
    957                 .close());
    958
    959         tree.complement();
    960
    961         // act/assert
    962         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    963         Assertions.assertNull(tree.getCentroid());
    964
    965         Assertions.assertEquals(1.0 + Math.sqrt(2) + Math.sqrt(5), tree.getBoundarySize(), TEST_EPS);
    966
    967         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
    968         segments.sort(SEGMENT_COMPARATOR);
    969
    970         Assertions.assertEquals(3, segments.size());
    971
    972         checkFiniteSegment(segments.get(0), Vector2D.ZERO, Vector2D.of(2, 1));
    973         checkFiniteSegment(segments.get(1), Vector2D.of(1, 0), Vector2D.ZERO);
    974         checkFiniteSegment(segments.get(2), Vector2D.of(2, 1), Vector2D.of(1, 0));
    975
    976         final List<LinePath> paths = tree.getBoundaryPaths();
    977         Assertions.assertEquals(1, paths.size());
    978
    979         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(2, 1), Vector2D.of(1, 0), Vector2D.ZERO);
    980     }
    981
    982     @Test
    983     void testGeometricProperties_regionWithHole() {
    984         // arrange
    985         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(3, 3), TEST_PRECISION)
    986                 .toTree();
    987         final RegionBSPTree2D inner = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION)
    988                 .toTree();
    989
    990         tree.difference(inner);
    991
    992         // act/assert
    993         Assertions.assertEquals(8, tree.getSize(), TEST_EPS);
    994         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 1.5), tree.getCentroid(), TEST_EPS);
    995
    996         Assertions.assertEquals(16, tree.getBoundarySize(), TEST_EPS);
    997
    998         final List<LinePath> paths = tree.getBoundaryPaths();
    999         Assertions.assertEquals(2, paths.size());
    1000
    1001         checkVertices(paths.get(0), Vector2D.of(0, 3), Vector2D.ZERO, Vector2D.of(3, 0),
    1002                 Vector2D.of(3, 3), Vector2D.of(0, 3));
    1003         checkVertices(paths.get(1), Vector2D.of(1, 1), Vector2D.of(1, 2), Vector2D.of(2, 2),
    1004                 Vector2D.of(2, 1), Vector2D.of(1, 1));
    1005     }
    1006
    1007     @Test
    1008     void testGeometricProperties_complementedRegionWithHole() {
    1009         // arrange
    1010         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(3, 3), TEST_PRECISION)
    1011                 .toTree();
    1012         final RegionBSPTree2D inner = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION)
    1013                 .toTree();
    1014
    1015         tree.difference(inner);
    1016
    1017         tree.complement();
    1018
    1019         // act/assert
    1020         GeometryTestUtils.assertPositiveInfinity(tree.getSize());
    1021         Assertions.assertNull(tree.getCentroid());
    1022
    1023         Assertions.assertEquals(16, tree.getBoundarySize(), TEST_EPS);
    1024
    1025         final List<LinePath> paths = tree.getBoundaryPaths();
    1026         Assertions.assertEquals(2, paths.size());
    1027
    1028         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(0, 3), Vector2D.of(3, 3),
    1029                 Vector2D.of(3, 0), Vector2D.ZERO);
    1030         checkVertices(paths.get(1), Vector2D.of(1, 1), Vector2D.of(2, 1), Vector2D.of(2, 2),
    1031                 Vector2D.of(1, 2), Vector2D.of(1, 1));
    1032     }
    1033
    1034     @Test
    1035     void testFrom_boundaries() {
    1036         // act
    1037         final RegionBSPTree2D tree = RegionBSPTree2D.from(Arrays.asList(
    1038                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).span(),
    1039                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION)
    1040                         .rayFrom(Vector2D.ZERO)
    1041                 ));
    1042
    1043         // assert
    1044         Assertions.assertFalse(tree.isFull());
    1045         Assertions.assertFalse(tree.isEmpty());
    1046
    1047         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
    1048
    1049         checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(-1, 1));
    1050         checkClassify(tree, RegionLocation.OUTSIDE,
    1051                 Vector2D.of(1, 1), Vector2D.of(1, -1), Vector2D.of(-1, -1));
    1052     }
    1053
    1054     @Test
    1055     void testFrom_boundaries_fullIsTrue() {
    1056         // act
    1057         final RegionBSPTree2D tree = RegionBSPTree2D.from(Arrays.asList(
    1058                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).span(),
    1059                     Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION)
    1060                         .rayFrom(Vector2D.ZERO)
    1061                 ), true);
    1062
    1063         // assert
    1064         Assertions.assertFalse(tree.isFull());
    1065         Assertions.assertFalse(tree.isEmpty());
    1066
    1067         Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
    1068
    1069         checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(-1, 1));
    1070         checkClassify(tree, RegionLocation.OUTSIDE,
    1071                 Vector2D.of(1, 1), Vector2D.of(1, -1), Vector2D.of(-1, -1));
    1072     }
    1073
    1074     @Test
    1075     void testFrom_boundaries_noBoundaries() {
    1076         // act/assert
    1077         Assertions.assertTrue(RegionBSPTree2D.from(Collections.emptyList()).isEmpty());
    1078         Assertions.assertTrue(RegionBSPTree2D.from(Collections.emptyList(), true).isFull());
    1079         Assertions.assertTrue(RegionBSPTree2D.from(Collections.emptyList(), false).isEmpty());
    1080     }
    1081
    1082     @Test
    1083     void testToList() {
    1084         // arrange
    1085         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).toTree();
    1086
    1087         // act
    1088         final BoundaryList2D list = tree.toList();
    1089
    1090         // assert
    1091         Assertions.assertEquals(4, list.toList().count());
    1092         Assertions.assertEquals(1, list.toTree().getSize(), TEST_EPS);
    1093     }
    1094
    1095     @Test
    1096     void testToList_fullAndEmpty() {
    1097         // act/assert
    1098         Assertions.assertEquals(0, RegionBSPTree2D.full().toList().count());
    1099         Assertions.assertEquals(0, RegionBSPTree2D.empty().toList().count());
    1100     }
    1101
    1102     @Test
    1103     void testToTree_returnsSameInstance() {
    1104         // arrange
    1105         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 2), TEST_PRECISION).toTree();
    1106
    1107         // act/assert
    1108         Assertions.assertSame(tree, tree.toTree());
    1109     }
    1110
    1111     @Test
    1112     void testProject_fullAndEmpty() {
    1113         // act/assert
    1114         Assertions.assertNull(RegionBSPTree2D.full().project(Vector2D.ZERO));
    1115         Assertions.assertNull(RegionBSPTree2D.empty().project(Vector2D.of(1, 2)));
    1116     }
    1117
    1118     @Test
    1119     void testProject_halfSpace() {
    1120         // arrange
    1121         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    1122         tree.getRoot().cut(X_AXIS);
    1123
    1124         // act/assert
    1125         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, tree.project(Vector2D.ZERO), TEST_EPS);
    1126         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-1, 0), tree.project(Vector2D.of(-1, 0)), TEST_EPS);
    1127         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 0),
    1128                 tree.project(Vector2D.of(2, -1)), TEST_EPS);
    1129         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-3, 0),
    1130                 tree.project(Vector2D.of(-3, 1)), TEST_EPS);
    1131     }
    1132
    1133     @Test
    1134     void testProject_rect() {
    1135         // arrange
    1136         final RegionBSPTree2D tree = Parallelogram.axisAligned(
    1137                     Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
    1138
    1139         // act/assert
    1140         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), tree.project(Vector2D.ZERO), TEST_EPS);
    1141         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), tree.project(Vector2D.of(1, 0)), TEST_EPS);
    1142         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 1), tree.project(Vector2D.of(1.5, 0)), TEST_EPS);
    1143         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 1), tree.project(Vector2D.of(2, 0)), TEST_EPS);
    1144         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 1), tree.project(Vector2D.of(3, 0)), TEST_EPS);
    1145
    1146         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), tree.project(Vector2D.of(1, 3)), TEST_EPS);
    1147         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), tree.project(Vector2D.of(1, 3)), TEST_EPS);
    1148         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 2), tree.project(Vector2D.of(1.5, 3)), TEST_EPS);
    1149         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), tree.project(Vector2D.of(2, 3)), TEST_EPS);
    1150         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 2), tree.project(Vector2D.of(3, 3)), TEST_EPS);
    1151
    1152         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1.5), tree.project(Vector2D.of(0, 1.5)), TEST_EPS);
    1153         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1.5), tree.project(Vector2D.of(1.5, 1.5)), TEST_EPS);
    1154         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 1.5), tree.project(Vector2D.of(3, 1.5)), TEST_EPS);
    1155     }
    1156
    1157     @Test
    1158     void testLinecast_empty() {
    1159         // arrange
    1160         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1161
    1162         // act/assert
    1163         LinecastChecker2D.with(tree)
    1164             .expectNothing()
    1165             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    1166
    1167         LinecastChecker2D.with(tree)
    1168             .expectNothing()
    1169             .whenGiven(Lines.segmentFromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    1170     }
    1171
    1172     @Test
    1173     void testLinecast_full() {
    1174         // arrange
    1175         final RegionBSPTree2D tree = RegionBSPTree2D.full();
    1176
    1177         // act/assert
    1178         LinecastChecker2D.with(tree)
    1179             .expectNothing()
    1180             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    1181
    1182         LinecastChecker2D.with(tree)
    1183             .expectNothing()
    1184             .whenGiven(Lines.segmentFromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    1185     }
    1186
    1187     @Test
    1188     void testLinecast() {
    1189         // arrange
    1190         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
    1191                 .toTree();
    1192
    1193         // act/assert
    1194         LinecastChecker2D.with(tree)
    1195             .expectNothing()
    1196             .whenGiven(Lines.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
    1197
    1198         LinecastChecker2D.with(tree)
    1199             .expect(Vector2D.ZERO, Vector2D.Unit.MINUS_X)
    1200             .and(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
    1201             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
    1202             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
    1203             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
    1204
    1205         LinecastChecker2D.with(tree)
    1206             .expect(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
    1207             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
    1208             .whenGiven(Lines.segmentFromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
    1209     }
    1210
    1211     @Test
    1212     void testLinecast_complementedTree() {
    1213         // arrange
    1214         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
    1215                 .toTree();
    1216
    1217         tree.complement();
    1218
    1219         // act/assert
    1220         LinecastChecker2D.with(tree)
    1221             .expectNothing()
    1222             .whenGiven(Lines.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
    1223
    1224         LinecastChecker2D.with(tree)
    1225             .expect(Vector2D.ZERO, Vector2D.Unit.PLUS_Y)
    1226             .and(Vector2D.ZERO, Vector2D.Unit.PLUS_X)
    1227             .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X)
    1228             .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_Y)
    1229             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
    1230
    1231         LinecastChecker2D.with(tree)
    1232             .expect(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X)
    1233             .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_Y)
    1234             .whenGiven(Lines.segmentFromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
    1235     }
    1236
    1237     @Test
    1238     void testLinecast_complexRegion() {
    1239         // arrange
    1240         final RegionBSPTree2D a = LinePath.fromVertexLoop(Arrays.asList(
    1241                     Vector2D.ZERO, Vector2D.of(0, 1),
    1242                     Vector2D.of(0.5, 1), Vector2D.of(0.5, 0)
    1243                 ), TEST_PRECISION).toTree();
    1244         a.complement();
    1245
    1246         final RegionBSPTree2D b = LinePath.fromVertexLoop(Arrays.asList(
    1247                 Vector2D.of(0.5, 0), Vector2D.of(0.5, 1),
    1248                 Vector2D.of(1, 1), Vector2D.of(1, 0)
    1249             ), TEST_PRECISION).toTree();
    1250         b.complement();
    1251
    1252         final RegionBSPTree2D c = LinePath.fromVertexLoop(Arrays.asList(
    1253                 Vector2D.of(0.5, 0.5), Vector2D.of(1.5, 0.5),
    1254                 Vector2D.of(1.5, 1.5), Vector2D.of(0.5, 1.5)
    1255             ), TEST_PRECISION).toTree();
    1256
    1257         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1258         tree.union(a, b);
    1259         tree.union(c);
    1260
    1261         // act/assert
    1262         LinecastChecker2D.with(tree)
    1263             .expect(Vector2D.of(1.5, 1.5), Vector2D.Unit.PLUS_Y)
    1264             .and(Vector2D.of(1.5, 1.5), Vector2D.Unit.PLUS_X)
    1265             .whenGiven(Lines.segmentFromPoints(Vector2D.of(0.25, 0.25), Vector2D.of(2, 2), TEST_PRECISION));
    1266     }
    1267
    1268     @Test
    1269     void testLinecast_removesDuplicatePoints() {
    1270         // arrange
    1271         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1272         tree.insert(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION).span());
    1273         tree.insert(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).span());
    1274
    1275         // act/assert
    1276         LinecastChecker2D.with(tree)
    1277             .expect(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
    1278             .whenGiven(Lines.fromPoints(Vector2D.of(1, 1), Vector2D.of(-1, -1), TEST_PRECISION));
    1279
    1280         LinecastChecker2D.with(tree)
    1281             .expect(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
    1282             .whenGiven(Lines.segmentFromPoints(Vector2D.of(1, 1), Vector2D.of(-1, -1), TEST_PRECISION));
    1283     }
    1284
    1285     @Test
    1286     void testTransform() {
    1287         // arrange
    1288         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(3, 2), TEST_PRECISION)
    1289                 .toTree();
    1290
    1291         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.createScale(0.5, 2)
    1292                 .rotate(Angle.PI_OVER_TWO)
    1293                 .translate(Vector2D.of(0, -1));
    1294
    1295         // act
    1296         tree.transform(transform);
    1297
    1298         // assert
    1299         final List<LinePath> paths = tree.getBoundaryPaths();
    1300         Assertions.assertEquals(1, paths.size());
    1301
    1302         final LinePath path = paths.get(0);
    1303         Assertions.assertEquals(4, path.getElements().size());
    1304         checkFiniteSegment(path.getElements().get(0), Vector2D.of(-4, -0.5), Vector2D.of(-2, -0.5));
    1305         checkFiniteSegment(path.getElements().get(1), Vector2D.of(-2, -0.5), Vector2D.of(-2, 0.5));
    1306         checkFiniteSegment(path.getElements().get(2), Vector2D.of(-2, 0.5), Vector2D.of(-4, 0.5));
    1307         checkFiniteSegment(path.getElements().get(3), Vector2D.of(-4, 0.5), Vector2D.of(-4, -0.5));
    1308     }
    1309
    1310     @Test
    1311     void testTransform_halfSpace() {
    1312         // arrange
    1313         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
    1314         tree.getRoot().insertCut(Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION));
    1315
    1316         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.createScale(0.5, 2)
    1317                 .rotate(Angle.PI_OVER_TWO)
    1318                 .translate(Vector2D.of(1, 0));
    1319
    1320         // act
    1321         tree.transform(transform);
    1322
    1323         // assert
    1324         final List<LinePath> paths = tree.getBoundaryPaths();
    1325         Assertions.assertEquals(1, paths.size());
    1326
    1327         final LinePath path = paths.get(0);
    1328         Assertions.assertEquals(1, path.getElements().size());
    1329         final LineConvexSubset segment = path.getStart();
    1330         Assertions.assertNull(segment.getStartPoint());
    1331         Assertions.assertNull(segment.getEndPoint());
    1332
    1333         final Line expectedLine = Lines.fromPointAndAngle(Vector2D.of(-1, 0), Angle.PI_OVER_TWO, TEST_PRECISION);
    1334         Assertions.assertTrue(expectedLine.eq(segment.getLine(), expectedLine.getPrecision()));
    1335     }
    1336
    1337     @Test
    1338     void testTransform_fullAndEmpty() {
    1339         // arrange
    1340         final RegionBSPTree2D full = RegionBSPTree2D.full();
    1341         final RegionBSPTree2D empty = RegionBSPTree2D.empty();
    1342
    1343         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.createRotation(Angle.PI_OVER_TWO);
    1344
    1345         // act
    1346         full.transform(transform);
    1347         empty.transform(transform);
    1348
    1349         // assert
    1350         Assertions.assertTrue(full.isFull());
    1351         Assertions.assertTrue(empty.isEmpty());
    1352     }
    1353
    1354     @Test
    1355     void testTransform_reflection() {
    1356         // arrange
    1357         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
    1358
    1359         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.from(v -> Vector2D.of(-v.getX(), v.getY()));
    1360
    1361         // act
    1362         tree.transform(transform);
    1363
    1364         // assert
    1365         final List<LinePath> paths = tree.getBoundaryPaths();
    1366         Assertions.assertEquals(1, paths.size());
    1367
    1368         final LinePath path = paths.get(0);
    1369         Assertions.assertEquals(4, path.getElements().size());
    1370         checkFiniteSegment(path.getElements().get(0), Vector2D.of(-2, 1), Vector2D.of(-1, 1));
    1371         checkFiniteSegment(path.getElements().get(1), Vector2D.of(-1, 1), Vector2D.of(-1, 2));
    1372         checkFiniteSegment(path.getElements().get(2), Vector2D.of(-1, 2), Vector2D.of(-2, 2));
    1373         checkFiniteSegment(path.getElements().get(3), Vector2D.of(-2, 2), Vector2D.of(-2, 1));
    1374     }
    1375
    1376     @Test
    1377     void testTransform_doubleReflection() {
    1378         // arrange
    1379         final RegionBSPTree2D tree = Parallelogram.axisAligned(
    1380                     Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
    1381
    1382         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.from(Vector2D::negate);
    1383
    1384         // act
    1385         tree.transform(transform);
    1386
    1387         // assert
    1388         final List<LinePath> paths = tree.getBoundaryPaths();
    1389         Assertions.assertEquals(1, paths.size());
    1390
    1391         final LinePath path = paths.get(0);
    1392         Assertions.assertEquals(4, path.getElements().size());
    1393         checkFiniteSegment(path.getElements().get(0), Vector2D.of(-2, -2), Vector2D.of(-1, -2));
    1394         checkFiniteSegment(path.getElements().get(1), Vector2D.of(-1, -2), Vector2D.of(-1, -1));
    1395         checkFiniteSegment(path.getElements().get(2), Vector2D.of(-1, -1), Vector2D.of(-2, -1));
    1396         checkFiniteSegment(path.getElements().get(3), Vector2D.of(-2, -1), Vector2D.of(-2, -2));
    1397     }
    1398
    1399     @Test
    1400     void testBooleanOperations() {
    1401         // arrange
    1402         final RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(3, 3), TEST_PRECISION).toTree();
    1403         RegionBSPTree2D temp;
    1404
    1405         // act
    1406         temp = Parallelogram.axisAligned(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).toTree();
    1407         temp.complement();
    1408         tree.intersection(temp);
    1409
    1410         temp = Parallelogram.axisAligned(Vector2D.of(3, 0), Vector2D.of(6, 3), TEST_PRECISION).toTree();
    1411         tree.union(temp);
    1412
    1413         temp = Parallelogram.axisAligned(Vector2D.of(2, 1), Vector2D.of(5, 2), TEST_PRECISION).toTree();
    1414         tree.difference(temp);
    1415
    1416         temp.setFull();
    1417         tree.xor(temp);
    1418
    1419         // assert
    1420         final List<LinePath> paths = tree.getBoundaryPaths();
    1421         Assertions.assertEquals(2, paths.size());
    1422
    1423         checkVertices(paths.get(0), Vector2D.ZERO, Vector2D.of(0, 3), Vector2D.of(6, 3),
    1424                 Vector2D.of(6, 0), Vector2D.ZERO);
    1425
    1426         checkVertices(paths.get(1), Vector2D.of(1, 1), Vector2D.of(5, 1), Vector2D.of(5, 2),
    1427                 Vector2D.of(1, 2), Vector2D.of(1, 1));
    1428     }
    1429
    1430     private static void assertSegmentsEqual(final LineConvexSubset expected, final LineConvexSubset actual) {
    1431         Assertions.assertEquals(expected.getLine(), actual.getLine());
    1432
    1433         final Vector2D expectedStart = expected.getStartPoint();
    1434         final Vector2D expectedEnd = expected.getEndPoint();
    1435
    1436         if (expectedStart != null) {
    1437             EuclideanTestUtils.assertCoordinatesEqual(expectedStart, actual.getStartPoint(), TEST_EPS);
    1438         } else {
    1439             Assertions.assertNull(actual.getStartPoint());
    1440         }
    1441
    1442         if (expectedEnd != null) {
    1443             EuclideanTestUtils.assertCoordinatesEqual(expectedEnd, actual.getEndPoint(), TEST_EPS);
    1444         } else {
    1445             Assertions.assertNull(actual.getEndPoint());
    1446         }
    1447     }
    1448
    1449     private static void checkFiniteSegment(final LineConvexSubset segment, final Vector2D start, final Vector2D end) {
    1450         EuclideanTestUtils.assertCoordinatesEqual(start, segment.getStartPoint(), TEST_EPS);
    1451         EuclideanTestUtils.assertCoordinatesEqual(end, segment.getEndPoint(), TEST_EPS);
    1452     }
    1453
    1454     private static void checkClassify(final Region<Vector2D> region, final RegionLocation loc, final Vector2D... points) {
    1455         for (final Vector2D point : points) {
    1456             final String msg = "Unexpected location for point " + point;
    1457
    1458             Assertions.assertEquals(loc, region.classify(point), msg);
    1459         }
    1460     }
    1461
    1462     private static void checkConvexArea(final ConvexArea area, final List<Vector2D> inside, final List<Vector2D> outside) {
    1463         checkClassify(area, RegionLocation.INSIDE, inside.toArray(new Vector2D[0]));
    1464         checkClassify(area, RegionLocation.OUTSIDE, outside.toArray(new Vector2D[0]));
    1465     }
    1466
    1467     /** Assert that the given path is finite and contains the given vertices.
    1468      * @param path
    1469      * @param vertices
    1470      */
    1471     private static void checkVertices(final LinePath path, final Vector2D... vertices) {
    1472         Assertions.assertTrue(path.isFinite(), "Line segment path is not finite");
    1473
    1474         final List<Vector2D> actual = path.getVertexSequence();
    1475
    1476         Assertions.assertEquals(vertices.length, actual.size(), "Vertex lists have different lengths");
    1477
    1478         for (int i  = 0; i < vertices.length; ++i) {
    1479             EuclideanTestUtils.assertCoordinatesEqual(vertices[i], actual.get(i), TEST_EPS);
    1480         }
    1481     }
    1482 }