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