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.List;
    23  import java.util.regex.Pattern;
    24  import java.util.stream.Collectors;
    25
    26  import org.apache.commons.geometry.core.GeometryTestUtils;
    27  import org.apache.commons.geometry.core.RegionLocation;
    28  import org.apache.commons.geometry.core.partitioning.Split;
    29  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    30  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    31  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    32  import org.apache.commons.numbers.angle.Angle;
    33  import org.apache.commons.numbers.core.Precision;
    34  import org.junit.jupiter.api.Assertions;
    35  import org.junit.jupiter.api.Test;
    36
    37  class ConvexAreaTest {
    38
    39      private static final double TEST_EPS = 1e-10;
    40
    41      private static final Precision.DoubleEquivalence TEST_PRECISION =
    42              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    43
    44      @Test
    45      void testFull() {
    46          // act
    47          final ConvexArea area = ConvexArea.full();
    48
    49          // assert
    50          Assertions.assertTrue(area.isFull());
    51          Assertions.assertFalse(area.isEmpty());
    52
    53          Assertions.assertEquals(0.0, area.getBoundarySize(), TEST_EPS);
    54          GeometryTestUtils.assertPositiveInfinity(area.getSize());
    55          Assertions.assertNull(area.getCentroid());
    56          Assertions.assertNull(area.getBounds());
    57      }
    58
    59      @Test
    60      void testBoundaryStream() {
    61          // arrange
    62          final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION);
    63          final ConvexArea area = ConvexArea.fromBounds(line);
    64
    65          // act
    66          final List<LineConvexSubset> segments = area.boundaryStream().collect(Collectors.toList());
    67
    68          // assert
    69          Assertions.assertEquals(1, segments.size());
    70          final LineConvexSubset segment = segments.get(0);
    71          Assertions.assertNull(segment.getStartPoint());
    72          Assertions.assertNull(segment.getEndPoint());
    73          Assertions.assertSame(line, segment.getLine());
    74      }
    75
    76      @Test
    77      void testBoundaryStream_full() {
    78          // arrange
    79          final ConvexArea area = ConvexArea.full();
    80
    81          // act
    82          final List<LineConvexSubset> segments = area.boundaryStream().collect(Collectors.toList());
    83
    84          // assert
    85          Assertions.assertEquals(0, segments.size());
    86      }
    87
    88      @Test
    89      void testToList() {
    90          // arrange
    91          final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    92                      Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1)
    93                  ), TEST_PRECISION);
    94
    95          // act
    96          final BoundaryList2D list = area.toList();
    97
    98          // assert
    99          Assertions.assertEquals(3, list.count());
    100         Assertions.assertEquals(area.getBoundaries(), list.getBoundaries());
    101     }
    102
    103     @Test
    104     void testToList_full() {
    105         // arrange
    106         final ConvexArea area = ConvexArea.full();
    107
    108         // act
    109         final BoundaryList2D list = area.toList();
    110
    111         // assert
    112         Assertions.assertEquals(0, list.count());
    113     }
    114
    115     @Test
    116     void testToTree() {
    117         // arrange
    118         final ConvexArea area = ConvexArea.fromBounds(
    119                     Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION),
    120                     Lines.fromPointAndAngle(Vector2D.of(1, 0), Angle.PI_OVER_TWO, TEST_PRECISION),
    121                     Lines.fromPointAndAngle(Vector2D.of(1, 1), Math.PI, TEST_PRECISION),
    122                     Lines.fromPointAndAngle(Vector2D.of(0, 1), -Angle.PI_OVER_TWO, TEST_PRECISION)
    123                 );
    124
    125         // act
    126         final RegionBSPTree2D tree = area.toTree();
    127
    128         // assert
    129         Assertions.assertFalse(tree.isFull());
    130         Assertions.assertFalse(tree.isEmpty());
    131
    132         Assertions.assertEquals(1, tree.getSize(), TEST_EPS);
    133         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), tree.getCentroid(), TEST_EPS);
    134     }
    135
    136     @Test
    137     void testToTree_full() {
    138         // arrange
    139         final ConvexArea area = ConvexArea.full();
    140
    141         // act
    142         final RegionBSPTree2D tree = area.toTree();
    143
    144         // assert
    145         Assertions.assertTrue(tree.isFull());
    146         Assertions.assertFalse(tree.isEmpty());
    147     }
    148
    149     @Test
    150     void testTransform_full() {
    151         // arrange
    152         final AffineTransformMatrix2D transform = AffineTransformMatrix2D.createScale(3);
    153         final ConvexArea area = ConvexArea.full();
    154
    155         // act
    156         final ConvexArea transformed = area.transform(transform);
    157
    158         // assert
    159         Assertions.assertSame(area, transformed);
    160     }
    161
    162     @Test
    163     void testTransform_infinite() {
    164         // arrange
    165         final AffineTransformMatrix2D mat = AffineTransformMatrix2D
    166                 .createRotation(Vector2D.of(0, 1), Angle.PI_OVER_TWO)
    167                 .scale(Vector2D.of(3, 2));
    168
    169         final ConvexArea area = ConvexArea.fromBounds(
    170                 Lines.fromPointAndAngle(Vector2D.ZERO, 0.25 * Math.PI, TEST_PRECISION),
    171                 Lines.fromPointAndAngle(Vector2D.ZERO, -0.25 * Math.PI, TEST_PRECISION));
    172
    173         // act
    174         final ConvexArea transformed = area.transform(mat);
    175
    176         // assert
    177         Assertions.assertNotSame(area, transformed);
    178
    179         final List<LinePath> paths = transformed.getBoundaryPaths();
    180         Assertions.assertEquals(1, paths.size());
    181
    182         final List<LineConvexSubset> segments = paths.get(0).getElements();
    183         Assertions.assertEquals(2, segments.size());
    184
    185         final LineConvexSubset firstSegment = segments.get(0);
    186         Assertions.assertNull(firstSegment.getStartPoint());
    187         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 2), firstSegment.getEndPoint(), TEST_EPS);
    188         Assertions.assertEquals(Math.atan2(2, 3), firstSegment.getLine().getAngle(), TEST_EPS);
    189
    190         final LineConvexSubset secondSegment = segments.get(1);
    191         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 2), secondSegment.getStartPoint(), TEST_EPS);
    192         Assertions.assertNull(secondSegment.getEndPoint());
    193         Assertions.assertEquals(Math.atan2(2, -3), secondSegment.getLine().getAngle(), TEST_EPS);
    194     }
    195
    196     @Test
    197     void testTransform_finite() {
    198         // arrange
    199         final AffineTransformMatrix2D mat = AffineTransformMatrix2D.createScale(Vector2D.of(1, 2));
    200
    201         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    202                     Vector2D.of(1, 1), Vector2D.of(2, 1),
    203                     Vector2D.of(2, 2), Vector2D.of(1, 2)
    204                 ), TEST_PRECISION);
    205
    206         // act
    207         final ConvexArea transformed = area.transform(mat);
    208
    209         // assert
    210         Assertions.assertNotSame(area, transformed);
    211
    212         final List<LineConvexSubset> segments = transformed.getBoundaries();
    213         Assertions.assertEquals(4, segments.size());
    214
    215         Assertions.assertEquals(2, transformed.getSize(), TEST_EPS);
    216         Assertions.assertEquals(6, transformed.getBoundarySize(), TEST_EPS);
    217         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 3), transformed.getCentroid(), TEST_EPS);
    218
    219         EuclideanTestUtils.assertRegionLocation(transformed, RegionLocation.BOUNDARY,
    220                 Vector2D.of(1, 2), Vector2D.of(2, 2), Vector2D.of(2, 4), Vector2D.of(1, 4));
    221         EuclideanTestUtils.assertRegionLocation(transformed, RegionLocation.INSIDE, transformed.getCentroid());
    222     }
    223
    224     @Test
    225     void testTransform_finite_withSingleReflection() {
    226         // arrange
    227         final AffineTransformMatrix2D mat = AffineTransformMatrix2D.createScale(Vector2D.of(-1, 2));
    228
    229         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    230                     Vector2D.of(1, 1), Vector2D.of(2, 1),
    231                     Vector2D.of(2, 2), Vector2D.of(1, 2)
    232                 ), TEST_PRECISION);
    233
    234         // act
    235         final ConvexArea transformed = area.transform(mat);
    236
    237         // assert
    238         Assertions.assertNotSame(area, transformed);
    239
    240         final List<LineConvexSubset> segments = transformed.getBoundaries();
    241         Assertions.assertEquals(4, segments.size());
    242
    243         Assertions.assertEquals(2, transformed.getSize(), TEST_EPS);
    244         Assertions.assertEquals(6, transformed.getBoundarySize(), TEST_EPS);
    245         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-1.5, 3), transformed.getCentroid(), TEST_EPS);
    246
    247         EuclideanTestUtils.assertRegionLocation(transformed, RegionLocation.BOUNDARY,
    248                 Vector2D.of(-1, 2), Vector2D.of(-2, 2), Vector2D.of(-2, 4), Vector2D.of(-1, 4));
    249         EuclideanTestUtils.assertRegionLocation(transformed, RegionLocation.INSIDE, transformed.getCentroid());
    250     }
    251
    252     @Test
    253     void testTransform_finite_withDoubleReflection() {
    254         // arrange
    255         final AffineTransformMatrix2D mat = AffineTransformMatrix2D.createScale(Vector2D.of(-1, -2));
    256
    257         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    258                     Vector2D.of(1, 1), Vector2D.of(2, 1),
    259                     Vector2D.of(2, 2), Vector2D.of(1, 2)
    260                 ), TEST_PRECISION);
    261
    262         // act
    263         final ConvexArea transformed = area.transform(mat);
    264
    265         // assert
    266         Assertions.assertNotSame(area, transformed);
    267
    268         final List<LineConvexSubset> segments = transformed.getBoundaries();
    269         Assertions.assertEquals(4, segments.size());
    270
    271         Assertions.assertEquals(2, transformed.getSize(), TEST_EPS);
    272         Assertions.assertEquals(6, transformed.getBoundarySize(), TEST_EPS);
    273         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-1.5, -3), transformed.getCentroid(), TEST_EPS);
    274
    275         EuclideanTestUtils.assertRegionLocation(transformed, RegionLocation.BOUNDARY,
    276                 Vector2D.of(-1, -2), Vector2D.of(-2, -2), Vector2D.of(-2, -4), Vector2D.of(-1, -4));
    277         EuclideanTestUtils.assertRegionLocation(transformed, RegionLocation.INSIDE, transformed.getCentroid());
    278     }
    279
    280     @Test
    281     void testGetVertices_full() {
    282         // arrange
    283         final ConvexArea area = ConvexArea.full();
    284
    285         // act/assert
    286         Assertions.assertEquals(0, area.getVertices().size());
    287     }
    288
    289     @Test
    290     void testGetVertices_twoParallelLines() {
    291         // arrange
    292         final ConvexArea area = ConvexArea.fromBounds(
    293                     Lines.fromPointAndAngle(Vector2D.of(0, 1), Math.PI, TEST_PRECISION),
    294                     Lines.fromPointAndAngle(Vector2D.of(0, -1), 0.0, TEST_PRECISION)
    295                 );
    296
    297         // act/assert
    298         Assertions.assertEquals(0, area.getVertices().size());
    299     }
    300
    301     @Test
    302     void testGetVertices_infiniteWithVertices() {
    303         // arrange
    304         final ConvexArea area = ConvexArea.fromBounds(
    305                     Lines.fromPointAndAngle(Vector2D.of(0, 1), Math.PI, TEST_PRECISION),
    306                     Lines.fromPointAndAngle(Vector2D.of(0, -1), 0.0, TEST_PRECISION),
    307                     Lines.fromPointAndAngle(Vector2D.of(1, 0), Angle.PI_OVER_TWO, TEST_PRECISION)
    308                 );
    309
    310         // act
    311         final List<Vector2D> vertices = area.getVertices();
    312
    313         // assert
    314         Assertions.assertEquals(2, vertices.size());
    315
    316         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, -1), vertices.get(0), TEST_EPS);
    317         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), vertices.get(1), TEST_EPS);
    318     }
    319
    320     @Test
    321     void testGetVertices_finite() {
    322         // arrange
    323         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    324                     Vector2D.ZERO,
    325                     Vector2D.Unit.PLUS_X,
    326                     Vector2D.Unit.PLUS_Y
    327                 ), TEST_PRECISION);
    328
    329         // act
    330         final List<Vector2D> vertices = area.getVertices();
    331
    332         // assert
    333         Assertions.assertEquals(3, vertices.size());
    334
    335         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(0), TEST_EPS);
    336         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_X, vertices.get(1), TEST_EPS);
    337         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.Unit.PLUS_Y, vertices.get(2), TEST_EPS);
    338     }
    339
    340     @Test
    341     void testGetVertices_mismatchedEndpoints() {
    342         // This test checks the case where we have a valid set of boundary segments but
    343         // with a small mismatch in the endpoints of some of the segments (possibly due
    344         // to floating point errors).
    345
    346         // arrange
    347         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
    348
    349         final Vector2D p1 = Vector2D.ZERO;
    350         final Vector2D p2 = Vector2D.of(0.99, 0);
    351         final Vector2D p3 = Vector2D.of(1, 0.002);
    352         final Vector2D p4 = Vector2D.of(0.995, -0.001);
    353         final Vector2D p5 = Vector2D.of(1, 1);
    354
    355         final ConvexArea area = new ConvexArea(Arrays.asList(
    356                     Lines.segmentFromPoints(p1, p2, precision),
    357                     Lines.segmentFromPoints(p2, p3, precision),
    358                     Lines.segmentFromPoints(p4, p5, precision),
    359                     Lines.segmentFromPoints(p5, p1, precision)
    360                 ));
    361
    362         // act
    363         final List<Vector2D> vertices = area.getVertices();
    364
    365         // assert
    366         Assertions.assertEquals(Arrays.asList(p1, p2, p3, p5), vertices);
    367     }
    368
    369     @Test
    370     void testGetBounds_infinite() {
    371         // act/assert
    372         Assertions.assertNull(ConvexArea.full().getBounds());
    373         Assertions.assertNull(ConvexArea.fromBounds(
    374                 Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION)).getBounds());
    375     }
    376
    377     @Test
    378     void testGetBounds_square() {
    379         // arrange
    380         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(-1, -1), 2, 1));
    381
    382         // act
    383         final Bounds2D bounds = area.getBounds();
    384
    385         // assert
    386         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-1, -1), bounds.getMin(), TEST_EPS);
    387         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), bounds.getMax(), TEST_EPS);
    388     }
    389
    390     @Test
    391     void testProject_full() {
    392         // arrange
    393         final ConvexArea area = ConvexArea.full();
    394
    395         // act/assert
    396         Assertions.assertNull(area.project(Vector2D.ZERO));
    397         Assertions.assertNull(area.project(Vector2D.Unit.PLUS_X));
    398     }
    399
    400     @Test
    401     void testProject_halfSpace() {
    402         // arrange
    403         final ConvexArea area = ConvexArea.fromBounds(
    404                 Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION));
    405
    406         // act/assert
    407         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 1), area.project(Vector2D.of(1, 1)), TEST_EPS);
    408         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 2), area.project(Vector2D.of(-2, 2)), TEST_EPS);
    409         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, -3), area.project(Vector2D.of(1, -3)), TEST_EPS);
    410         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, -4), area.project(Vector2D.of(-2, -4)), TEST_EPS);
    411     }
    412
    413     @Test
    414     void testProject_square() {
    415         // arrange
    416         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.ZERO, 1, 1));
    417
    418         // act/assert
    419         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), area.project(Vector2D.of(1, 1)), TEST_EPS);
    420         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), area.project(Vector2D.of(2, 2)), TEST_EPS);
    421
    422         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, area.project(Vector2D.ZERO), TEST_EPS);
    423         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, area.project(Vector2D.of(-1, -1)), TEST_EPS);
    424
    425         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 0.5), area.project(Vector2D.of(0.1, 0.5)), TEST_EPS);
    426         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.2, 1), area.project(Vector2D.of(0.2, 0.9)), TEST_EPS);
    427
    428         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0), area.project(Vector2D.of(0.5, 0.5)), TEST_EPS);
    429     }
    430
    431     @Test
    432     void testTrim_full() {
    433         // arrange
    434         final ConvexArea area = ConvexArea.full();
    435         final Segment segment = Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION);
    436
    437         // act
    438         final LineConvexSubset trimmed = area.trim(segment);
    439
    440         // assert
    441         Assertions.assertSame(segment, trimmed);
    442     }
    443
    444     @Test
    445     void testTrim_halfSpace() {
    446         // arrange
    447         final ConvexArea area = ConvexArea.fromBounds(Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION));
    448         final LineConvexSubset segment = Lines.fromPoints(Vector2D.Unit.MINUS_Y, Vector2D.Unit.PLUS_Y, TEST_PRECISION).span();
    449
    450         // act
    451         final LineConvexSubset trimmed = area.trim(segment);
    452
    453         // assert
    454         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, trimmed.getStartPoint(), TEST_EPS);
    455         GeometryTestUtils.assertPositiveInfinity(trimmed.getSubspaceEnd());
    456     }
    457
    458     @Test
    459     void testTrim_square() {
    460         // arrange
    461         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.ZERO, 1, 1));
    462         final LineConvexSubset segment = Lines.fromPoints(Vector2D.of(0.5, 0), Vector2D.of(0.5, 1), TEST_PRECISION).span();
    463
    464         // act
    465         final LineConvexSubset trimmed = area.trim(segment);
    466
    467         // assert
    468         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0), trimmed.getStartPoint(), TEST_EPS);
    469         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 1), trimmed.getEndPoint(), TEST_EPS);
    470     }
    471
    472     @Test
    473     void testTrim_segmentOutsideOfRegion() {
    474         // arrange
    475         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.ZERO, 1, 1));
    476         final LineConvexSubset segment = Lines.fromPoints(Vector2D.of(-0.5, 0), Vector2D.of(-0.5, 1), TEST_PRECISION).span();
    477
    478         // act
    479         final LineConvexSubset trimmed = area.trim(segment);
    480
    481         // assert
    482         Assertions.assertNull(trimmed);
    483     }
    484
    485     @Test
    486     void testTrim_segmentDirectlyOnBoundaryOfRegion() {
    487         // arrange
    488         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.ZERO, 1, 1));
    489         final LineConvexSubset segment = Lines.fromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), TEST_PRECISION).span();
    490
    491         // act
    492         final LineConvexSubset trimmed = area.trim(segment);
    493
    494         // assert
    495         Assertions.assertNull(trimmed);
    496     }
    497
    498     @Test
    499     void testSplit_full() {
    500         // arrange
    501         final ConvexArea input = ConvexArea.full();
    502
    503         final Line splitter = Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION);
    504
    505         // act
    506         final Split<ConvexArea> split = input.split(splitter);
    507
    508         // act
    509         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    510
    511         final ConvexArea minus = split.getMinus();
    512         Assertions.assertFalse(minus.isFull());
    513         Assertions.assertFalse(minus.isEmpty());
    514
    515         GeometryTestUtils.assertPositiveInfinity(minus.getBoundarySize());
    516         GeometryTestUtils.assertPositiveInfinity(minus.getSize());
    517         Assertions.assertNull(minus.getCentroid());
    518
    519         final List<LineConvexSubset> minusSegments = minus.getBoundaries();
    520         Assertions.assertEquals(1, minusSegments.size());
    521         Assertions.assertEquals(splitter, minusSegments.get(0).getLine());
    522
    523         final ConvexArea plus = split.getPlus();
    524         Assertions.assertFalse(plus.isFull());
    525         Assertions.assertFalse(plus.isEmpty());
    526
    527         GeometryTestUtils.assertPositiveInfinity(plus.getBoundarySize());
    528         GeometryTestUtils.assertPositiveInfinity(plus.getSize());
    529         Assertions.assertNull(plus.getCentroid());
    530
    531         final List<LineConvexSubset> plusSegments = plus.getBoundaries();
    532         Assertions.assertEquals(1, plusSegments.size());
    533         Assertions.assertEquals(splitter, plusSegments.get(0).getLine().reverse());
    534     }
    535
    536     @Test
    537     void testSplit_halfSpace_split() {
    538         // arrange
    539         final ConvexArea area = ConvexArea.fromBounds(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    540         final Line splitter = Lines.fromPointAndAngle(Vector2D.ZERO, 0.25 * Math.PI, TEST_PRECISION);
    541
    542         // act
    543         final Split<ConvexArea> split = area.split(splitter);
    544
    545         // assert
    546         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    547
    548         final ConvexArea minus = split.getMinus();
    549         Assertions.assertFalse(minus.isFull());
    550         Assertions.assertFalse(minus.isEmpty());
    551
    552         GeometryTestUtils.assertPositiveInfinity(minus.getBoundarySize());
    553         GeometryTestUtils.assertPositiveInfinity(minus.getSize());
    554         Assertions.assertNull(minus.getCentroid());
    555
    556         Assertions.assertEquals(2, minus.getBoundaries().size());
    557
    558         final ConvexArea plus = split.getPlus();
    559         Assertions.assertFalse(plus.isFull());
    560         Assertions.assertFalse(plus.isEmpty());
    561
    562         GeometryTestUtils.assertPositiveInfinity(plus.getBoundarySize());
    563         GeometryTestUtils.assertPositiveInfinity(plus.getSize());
    564         Assertions.assertNull(plus.getCentroid());
    565
    566         Assertions.assertEquals(2, plus.getBoundaries().size());
    567     }
    568
    569     @Test
    570     void testSplit_halfSpace_splitOnBoundary() {
    571         // arrange
    572         final ConvexArea area = ConvexArea.fromBounds(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    573         final Line splitter = Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
    574
    575         // act
    576         final Split<ConvexArea> split = area.split(splitter);
    577
    578         // assert
    579         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    580
    581         Assertions.assertSame(area, split.getMinus());
    582         Assertions.assertNull(split.getPlus());
    583     }
    584
    585     @Test
    586     void testSplit_halfSpace_splitOnBoundaryWithReversedSplitter() {
    587         // arrange
    588         final ConvexArea area = ConvexArea.fromBounds(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    589         final Line splitter = Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).reverse();
    590
    591         // act
    592         final Split<ConvexArea> split = area.split(splitter);
    593
    594         // assert
    595         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    596
    597         Assertions.assertNull(split.getMinus());
    598         Assertions.assertSame(area, split.getPlus());
    599     }
    600
    601     @Test
    602     void testSplit_square_split() {
    603         // arrange
    604         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(1, 1), 2, 1));
    605         final Line splitter = Lines.fromPointAndAngle(Vector2D.of(2, 1), Angle.PI_OVER_TWO, TEST_PRECISION);
    606
    607         // act
    608         final Split<ConvexArea> split = area.split(splitter);
    609
    610         // assert
    611         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    612
    613         final ConvexArea minus = split.getMinus();
    614         Assertions.assertFalse(minus.isFull());
    615         Assertions.assertFalse(minus.isEmpty());
    616
    617         Assertions.assertEquals(4, minus.getBoundarySize(), TEST_EPS);
    618         Assertions.assertEquals(1, minus.getSize(), TEST_EPS);
    619         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1.5, 1.5), minus.getCentroid(), TEST_EPS);
    620
    621         Assertions.assertEquals(4, minus.getBoundaries().size());
    622
    623         final ConvexArea plus = split.getPlus();
    624         Assertions.assertFalse(plus.isFull());
    625         Assertions.assertFalse(plus.isEmpty());
    626
    627         Assertions.assertEquals(4, plus.getBoundarySize(), TEST_EPS);
    628         Assertions.assertEquals(1, plus.getSize(), TEST_EPS);
    629         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2.5, 1.5), plus.getCentroid(), TEST_EPS);
    630
    631         Assertions.assertEquals(4, plus.getBoundaries().size());
    632     }
    633
    634     @Test
    635     void testSplit_square_splitOnVertices() {
    636         // arrange
    637         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(1, 1), 1, 1));
    638         final Line splitter = Lines.fromPoints(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION);
    639
    640         // act
    641         final Split<ConvexArea> split = area.split(splitter);
    642
    643         // assert
    644         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    645
    646         final ConvexArea minus = split.getMinus();
    647         Assertions.assertFalse(minus.isFull());
    648         Assertions.assertFalse(minus.isEmpty());
    649
    650         Assertions.assertEquals(2 + Math.sqrt(2), minus.getBoundarySize(), TEST_EPS);
    651         Assertions.assertEquals(0.5, minus.getSize(), TEST_EPS);
    652         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(4.0 / 3.0, 5.0 / 3.0), minus.getCentroid(), TEST_EPS);
    653
    654         Assertions.assertEquals(3, minus.getBoundaries().size());
    655
    656         final ConvexArea plus = split.getPlus();
    657         Assertions.assertFalse(plus.isFull());
    658         Assertions.assertFalse(plus.isEmpty());
    659
    660         Assertions.assertEquals(2 + Math.sqrt(2), plus.getBoundarySize(), TEST_EPS);
    661         Assertions.assertEquals(0.5, plus.getSize(), TEST_EPS);
    662         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(5.0 / 3.0, 4.0 / 3.0), plus.getCentroid(), TEST_EPS);
    663
    664         Assertions.assertEquals(3, plus.getBoundaries().size());
    665     }
    666
    667     @Test
    668     void testSplit_square_splitOnVerticesWithReversedSplitter() {
    669         // arrange
    670         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(1, 1), 1, 1));
    671         final Line splitter = Lines.fromPoints(Vector2D.of(1, 1), Vector2D.of(2, 2), TEST_PRECISION).reverse();
    672
    673         // act
    674         final Split<ConvexArea> split = area.split(splitter);
    675
    676         // assert
    677         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    678
    679         final ConvexArea minus = split.getMinus();
    680         Assertions.assertFalse(minus.isFull());
    681         Assertions.assertFalse(minus.isEmpty());
    682
    683         Assertions.assertEquals(2 + Math.sqrt(2), minus.getBoundarySize(), TEST_EPS);
    684         Assertions.assertEquals(0.5, minus.getSize(), TEST_EPS);
    685         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(5.0 / 3.0, 4.0 / 3.0), minus.getCentroid(), TEST_EPS);
    686
    687         Assertions.assertEquals(3, minus.getBoundaries().size());
    688
    689         final ConvexArea plus = split.getPlus();
    690         Assertions.assertFalse(plus.isFull());
    691         Assertions.assertFalse(plus.isEmpty());
    692
    693         Assertions.assertEquals(2 + Math.sqrt(2), plus.getBoundarySize(), TEST_EPS);
    694         Assertions.assertEquals(0.5, plus.getSize(), TEST_EPS);
    695         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(4.0 / 3.0, 5.0 / 3.0), plus.getCentroid(), TEST_EPS);
    696
    697         Assertions.assertEquals(3, plus.getBoundaries().size());
    698     }
    699
    700     @Test
    701     void testSplit_square_entirelyOnMinus() {
    702         // arrange
    703         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(1, 1), 1, 1));
    704         final Line splitter = Lines.fromPoints(Vector2D.of(3, 1), Vector2D.of(3, 2), TEST_PRECISION);
    705
    706         // act
    707         final Split<ConvexArea> split = area.split(splitter);
    708
    709         // assert
    710         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    711         Assertions.assertSame(area, split.getMinus());
    712         Assertions.assertNull(split.getPlus());
    713     }
    714
    715     @Test
    716     void testSplit_square_onMinusBoundary() {
    717         // arrange
    718         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(1, 1), 1, 1));
    719         final Line splitter = Lines.fromPoints(Vector2D.of(2, 1), Vector2D.of(2, 2), TEST_PRECISION);
    720
    721         // act
    722         final Split<ConvexArea> split = area.split(splitter);
    723
    724         // assert
    725         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    726         Assertions.assertSame(area, split.getMinus());
    727         Assertions.assertNull(split.getPlus());
    728     }
    729
    730     @Test
    731     void testSplit_square_entirelyOnPlus() {
    732         // arrange
    733         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(1, 1), 1, 1));
    734         final Line splitter = Lines.fromPoints(Vector2D.of(0, 1), Vector2D.of(0, 2), TEST_PRECISION);
    735
    736         // act
    737         final Split<ConvexArea> split = area.split(splitter);
    738
    739         // assert
    740         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    741         Assertions.assertNull(split.getMinus());
    742         Assertions.assertSame(area, split.getPlus());
    743     }
    744
    745     @Test
    746     void testSplit_square_onPlusBoundary() {
    747         // arrange
    748         final ConvexArea area = ConvexArea.fromBounds(createSquareBoundingLines(Vector2D.of(1, 1), 1, 1));
    749         final Line splitter = Lines.fromPoints(Vector2D.of(1, 1), Vector2D.of(1, 2), TEST_PRECISION);
    750
    751         // act
    752         final Split<ConvexArea> split = area.split(splitter);
    753
    754         // assert
    755         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    756         Assertions.assertNull(split.getMinus());
    757         Assertions.assertSame(area, split.getPlus());
    758     }
    759
    760     @Test
    761     void testSplit_fannedLines() {
    762         // arrange
    763         final Line a = Lines.fromPointAndDirection(
    764                 Vector2D.of(0.00600526260605261, -0.3392565140336253),
    765                 Vector2D.of(0.9998433697734339, 0.017698472253402094), TEST_PRECISION);
    766         final Line b = Lines.fromPointAndDirection(
    767                 Vector2D.of(-0.05020576603061953, 1.7524758059156824),
    768                 Vector2D.of(0.9995898847600798, 0.02863672965494457), TEST_PRECISION);
    769
    770         final ConvexArea area = ConvexArea.fromBounds(a, b.reverse());
    771
    772         final Line splitter = Lines.fromPointAndDirection(
    773                 Vector2D.of(0.01581855191043128, -2.5270731411451215),
    774                 Vector2D.of(0.999980409069402, 0.006259510954681248), TEST_PRECISION);
    775
    776         // act
    777         final Split<ConvexArea> split = area.split(splitter);
    778
    779         // assert
    780         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    781         Assertions.assertSame(area, split.getMinus());
    782         Assertions.assertNull(split.getPlus());
    783     }
    784
    785     @Test
    786     void testSplit_trimmedSplitterDiscrepancy() {
    787         // The following example came from a failed invocation of the Sphere.toTree() method.
    788         // This test checks the case where the splitter trimmed to the area is non-empty but
    789         // the boundaries split by the splitter all lies on a single side.
    790
    791         // arrange
    792         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-10);
    793
    794         final Vector2D p1 = Vector2D.of(-100.27622744776312, -39.236143934478704);
    795         final Vector2D p2 = Vector2D.of(-100.23149336840831, -39.28090397981739);
    796         final Vector2D p3 = Vector2D.of(-96.28607710958399, -39.25486984391497);
    797         final ConvexArea area = ConvexArea.fromBounds(
    798                     Lines.fromPointAndDirection(p1, Vector2D.of(-0.00601644753700725, -0.9999819010157307), precision),
    799                     Lines.fromPoints(p1, p2, precision),
    800                     Lines.fromPoints(p2, p3, precision),
    801                     Lines.fromPointAndDirection(p3, Vector2D.of(0.9999648811047153, 0.008380725340508379), precision)
    802                 );
    803
    804         final Line splitter = Lines.fromPointAndDirection(
    805                 Vector2D.of(-68.9981806624852, -70.04669274578112),
    806                 Vector2D.of(0.7124186895479748, -0.7017546656651072),
    807                 precision);
    808
    809         // act
    810         final Split<ConvexArea> minusSplit = area.split(splitter);
    811         final Split<ConvexArea> plusSplit = area.split(splitter.reverse());
    812
    813         // assert
    814         Assertions.assertEquals(SplitLocation.MINUS, minusSplit.getLocation());
    815
    816         Assertions.assertSame(area, minusSplit.getMinus());
    817         Assertions.assertNull(minusSplit.getPlus());
    818
    819         Assertions.assertEquals(SplitLocation.PLUS, plusSplit.getLocation());
    820
    821         Assertions.assertNull(plusSplit.getMinus());
    822         Assertions.assertSame(area, plusSplit.getPlus());
    823     }
    824
    825     @Test
    826     void testLinecast_full() {
    827         // arrange
    828         final ConvexArea area = ConvexArea.full();
    829
    830         // act/assert
    831         LinecastChecker2D.with(area)
    832             .expectNothing()
    833             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    834
    835         LinecastChecker2D.with(area)
    836             .expectNothing()
    837             .whenGiven(Lines.segmentFromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
    838     }
    839
    840     @Test
    841     void testLinecast() {
    842         // arrange
    843         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    844                     Vector2D.ZERO, Vector2D.of(1, 0),
    845                     Vector2D.of(1, 1), Vector2D.of(0, 1)
    846                 ), TEST_PRECISION);
    847
    848         // act/assert
    849         LinecastChecker2D.with(area)
    850             .expectNothing()
    851             .whenGiven(Lines.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
    852
    853         LinecastChecker2D.with(area)
    854             .expect(Vector2D.ZERO, Vector2D.Unit.MINUS_X)
    855             .and(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
    856             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
    857             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
    858             .whenGiven(Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
    859
    860         LinecastChecker2D.with(area)
    861             .expect(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
    862             .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
    863             .whenGiven(Lines.segmentFromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
    864     }
    865
    866     @Test
    867     void testToString() {
    868         // arrange
    869         final ConvexArea area = ConvexArea.full();
    870
    871         // act
    872         final String str = area.toString();
    873
    874         // assert
    875         Assertions.assertTrue(str.contains("ConvexArea"));
    876         Assertions.assertTrue(str.contains("boundaries= "));
    877     }
    878
    879     @Test
    880     void testConvexPolygonFromVertices_notEnoughUniqueVertices() {
    881         // arrange
    882         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-3);
    883
    884         final Pattern unclosedPattern = Pattern.compile("Cannot construct convex polygon from unclosed path.*");
    885         final Pattern notEnoughElementsPattern =
    886                 Pattern.compile("Cannot construct convex polygon from path with less than 3 elements.*");
    887         final Pattern nonConvexPattern = Pattern.compile("Cannot construct convex polygon from non-convex path.*");
    888
    889         final Pattern singleVertexPattern =
    890                 Pattern.compile("Unable to create line path; only a single unique vertex provided.*");
    891
    892         // act/assert
    893         GeometryTestUtils.assertThrowsWithMessage(() -> {
    894             ConvexArea.convexPolygonFromVertices(Collections.emptyList(), precision);
    895         }, IllegalArgumentException.class, unclosedPattern);
    896
    897         GeometryTestUtils.assertThrowsWithMessage(() -> {
    898             ConvexArea.convexPolygonFromVertices(Collections.singletonList(Vector2D.ZERO), precision);
    899         }, IllegalStateException.class, singleVertexPattern);
    900
    901         GeometryTestUtils.assertThrowsWithMessage(() -> {
    902             ConvexArea.convexPolygonFromVertices(Arrays.asList(Vector2D.ZERO, Vector2D.of(1e-4, 1e-4)), precision);
    903         }, IllegalStateException.class, singleVertexPattern);
    904
    905         GeometryTestUtils.assertThrowsWithMessage(() -> {
    906             ConvexArea.convexPolygonFromVertices(Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X), precision);
    907         }, IllegalArgumentException.class, notEnoughElementsPattern);
    908
    909         GeometryTestUtils.assertThrowsWithMessage(() -> {
    910             ConvexArea.convexPolygonFromVertices(
    911                     Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, 1e-4)), precision);
    912         }, IllegalArgumentException.class, notEnoughElementsPattern);
    913
    914         GeometryTestUtils.assertThrowsWithMessage(() -> {
    915             ConvexArea.convexPolygonFromVertices(
    916                     Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, -1)), precision);
    917         }, IllegalArgumentException.class, nonConvexPattern);
    918     }
    919
    920     @Test
    921     void testConvexPolygonFromVertices_triangle() {
    922         // arrange
    923         final Vector2D p0 = Vector2D.of(1, 2);
    924         final Vector2D p1 = Vector2D.of(2, 2);
    925         final Vector2D p2 = Vector2D.of(2, 3);
    926
    927         // act
    928         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(p0, p1, p2), TEST_PRECISION);
    929
    930         // assert
    931         Assertions.assertFalse(area.isFull());
    932         Assertions.assertFalse(area.isEmpty());
    933
    934         Assertions.assertEquals(0.5, area.getSize(), TEST_EPS);
    935         Assertions.assertEquals(2 + Math.sqrt(2), area.getBoundarySize(), TEST_EPS);
    936         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.centroid(p0, p1, p2), area.getCentroid(), TEST_EPS);
    937     }
    938
    939     @Test
    940     void testConvexPolygonFromVertices_square_closeRequired() {
    941         // act
    942         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    943                     Vector2D.ZERO,
    944                     Vector2D.Unit.PLUS_X,
    945                     Vector2D.of(1, 1),
    946                     Vector2D.of(0, 1)
    947                 ), TEST_PRECISION);
    948
    949         // assert
    950         Assertions.assertFalse(area.isFull());
    951         Assertions.assertFalse(area.isEmpty());
    952
    953         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
    954         Assertions.assertEquals(4, area.getBoundarySize(), TEST_EPS);
    955         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
    956     }
    957
    958     @Test
    959     void testConvexPolygonFromVertices_square_closeNotRequired() {
    960         // act
    961         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    962                     Vector2D.ZERO,
    963                     Vector2D.Unit.PLUS_X,
    964                     Vector2D.of(1, 1),
    965                     Vector2D.of(0, 1),
    966                     Vector2D.ZERO
    967                 ), TEST_PRECISION);
    968
    969         // assert
    970         Assertions.assertFalse(area.isFull());
    971         Assertions.assertFalse(area.isEmpty());
    972
    973         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
    974         Assertions.assertEquals(4, area.getBoundarySize(), TEST_EPS);
    975         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
    976     }
    977
    978     @Test
    979     void testConvexPolygonFromVertices_handlesDuplicatePoints() {
    980         // arrange
    981         final double eps = 1e-3;
    982         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(eps);
    983
    984         // act
    985         final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
    986                     Vector2D.ZERO,
    987                     Vector2D.of(1e-4, 1e-4),
    988                     Vector2D.Unit.PLUS_X,
    989                     Vector2D.of(1, 1e-4),
    990                     Vector2D.of(1, 1),
    991                     Vector2D.of(0, 1),
    992                     Vector2D.of(1e-4, 1),
    993                     Vector2D.of(1e-4, 1e-4)
    994                 ), precision);
    995
    996         // assert
    997         Assertions.assertFalse(area.isFull());
    998         Assertions.assertFalse(area.isEmpty());
    999
    1000         Assertions.assertEquals(1, area.getSize(), eps);
    1001         Assertions.assertEquals(4, area.getBoundarySize(), eps);
    1002         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), eps);
    1003     }
    1004
    1005     @Test
    1006     void testConvexPolygonFromPath() {
    1007         // act
    1008         final ConvexArea area = ConvexArea.convexPolygonFromPath(LinePath.fromVertexLoop(
    1009                 Arrays.asList(
    1010                         Vector2D.ZERO,
    1011                         Vector2D.Unit.PLUS_X,
    1012                         Vector2D.of(1, 1),
    1013                         Vector2D.Unit.PLUS_Y
    1014                 ), TEST_PRECISION));
    1015
    1016         // assert
    1017         Assertions.assertFalse(area.isFull());
    1018         Assertions.assertFalse(area.isEmpty());
    1019
    1020         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
    1021         Assertions.assertEquals(4, area.getBoundarySize(), TEST_EPS);
    1022         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
    1023     }
    1024
    1025     @Test
    1026     void testConvexPolygonFromVertices_notConvex() {
    1027         // arrange
    1028         final Pattern msgPattern = Pattern.compile("Cannot construct convex polygon from non-convex path.*");
    1029
    1030         // act/assert
    1031         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1032             ConvexArea.convexPolygonFromVertices(Arrays.asList(
    1033                         Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(2, 0)
    1034                     ), TEST_PRECISION);
    1035         }, IllegalArgumentException.class, msgPattern);
    1036
    1037         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1038             ConvexArea.convexPolygonFromVertices(Arrays.asList(
    1039                         Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(1, -1)
    1040                     ), TEST_PRECISION);
    1041         }, IllegalArgumentException.class, msgPattern);
    1042
    1043         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1044             ConvexArea.convexPolygonFromVertices(
    1045                     Arrays.asList(
    1046                             Vector2D.ZERO,
    1047                             Vector2D.Unit.PLUS_Y,
    1048                             Vector2D.of(1, 1),
    1049                             Vector2D.Unit.PLUS_X
    1050                     ), TEST_PRECISION);
    1051         }, IllegalArgumentException.class, msgPattern);
    1052
    1053         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1054             ConvexArea.convexPolygonFromVertices(Arrays.asList(
    1055                         Vector2D.ZERO, Vector2D.of(2, 0),
    1056                         Vector2D.of(2, 2), Vector2D.of(1, 1),
    1057                         Vector2D.of(1.5, 1)
    1058                     ), TEST_PRECISION);
    1059         }, IllegalArgumentException.class, msgPattern);
    1060     }
    1061
    1062     @Test
    1063     void testConvexPolygonFromPath_invalidPaths() {
    1064         // arrange
    1065         final Pattern unclosedPattern = Pattern.compile("Cannot construct convex polygon from unclosed path.*");
    1066         final Pattern notEnoughElementsPattern =
    1067                 Pattern.compile("Cannot construct convex polygon from path with less than 3 elements.*");
    1068         final Pattern nonConvexPattern = Pattern.compile("Cannot construct convex polygon from non-convex path.*");
    1069
    1070         // act/assert
    1071         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1072             ConvexArea.convexPolygonFromPath(LinePath.empty());
    1073         }, IllegalArgumentException.class, unclosedPattern);
    1074
    1075         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1076             ConvexArea.convexPolygonFromPath(LinePath.fromVertices(
    1077                     Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X), TEST_PRECISION));
    1078         }, IllegalArgumentException.class, unclosedPattern);
    1079
    1080         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1081             ConvexArea.convexPolygonFromPath(LinePath.fromVertices(
    1082                     Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.ZERO), TEST_PRECISION));
    1083         }, IllegalArgumentException.class, notEnoughElementsPattern);
    1084
    1085         GeometryTestUtils.assertThrowsWithMessage(() -> {
    1086             ConvexArea.convexPolygonFromPath(LinePath.fromVertexLoop(
    1087                     Arrays.asList(
    1088                             Vector2D.ZERO,
    1089                             Vector2D.Unit.PLUS_Y,
    1090                             Vector2D.of(1, 1),
    1091                             Vector2D.Unit.PLUS_X
    1092                     ), TEST_PRECISION));
    1093         }, IllegalArgumentException.class, nonConvexPattern);
    1094     }
    1095
    1096     @Test
    1097     void testFromBounds_noLines() {
    1098         // act
    1099         final ConvexArea area = ConvexArea.fromBounds(Collections.emptyList());
    1100
    1101         // assert
    1102         Assertions.assertSame(ConvexArea.full(), area);
    1103     }
    1104
    1105     @Test
    1106     void testFromBounds_singleLine() {
    1107         // arrange
    1108         final Line line = Lines.fromPoints(Vector2D.of(0, 1), Vector2D.of(1, 3), TEST_PRECISION);
    1109
    1110         // act
    1111         final ConvexArea area = ConvexArea.fromBounds(line);
    1112
    1113         // assert
    1114         Assertions.assertFalse(area.isFull());
    1115         Assertions.assertFalse(area.isEmpty());
    1116
    1117         GeometryTestUtils.assertPositiveInfinity(area.getBoundarySize());
    1118         GeometryTestUtils.assertPositiveInfinity(area.getSize());
    1119         Assertions.assertNull(area.getCentroid());
    1120
    1121         final List<LineConvexSubset> segments = area.getBoundaries();
    1122         Assertions.assertEquals(1, segments.size());
    1123         Assertions.assertSame(line, segments.get(0).getLine());
    1124
    1125         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.INSIDE, Vector2D.of(-1, 1), Vector2D.of(0, 2));
    1126         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.BOUNDARY, Vector2D.of(0, 1), Vector2D.of(2, 5));
    1127         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.OUTSIDE, Vector2D.ZERO, Vector2D.of(2, 3));
    1128     }
    1129
    1130     @Test
    1131     void testFromBounds_twoLines() {
    1132         // arrange
    1133         final Line a = Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION);
    1134         final Line b = Lines.fromPointAndAngle(Vector2D.ZERO, Math.PI, TEST_PRECISION);
    1135
    1136         // act
    1137         final ConvexArea area = ConvexArea.fromBounds(a, b);
    1138
    1139         // assert
    1140         Assertions.assertFalse(area.isFull());
    1141         Assertions.assertFalse(area.isEmpty());
    1142
    1143         GeometryTestUtils.assertPositiveInfinity(area.getBoundarySize());
    1144         GeometryTestUtils.assertPositiveInfinity(area.getSize());
    1145         Assertions.assertNull(area.getCentroid());
    1146
    1147         final List<LineConvexSubset> segments = area.getBoundaries();
    1148         Assertions.assertEquals(2, segments.size());
    1149
    1150         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.INSIDE, Vector2D.of(-1, -1));
    1151         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.BOUNDARY,
    1152                 Vector2D.ZERO, Vector2D.of(-1, 0), Vector2D.of(0, -1));
    1153         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.OUTSIDE,
    1154                 Vector2D.of(-1, 1), Vector2D.of(1, 1), Vector2D.of(1, -1));
    1155     }
    1156
    1157     @Test
    1158     void testFromBounds_triangle() {
    1159         // arrange
    1160         final Line a = Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION);
    1161         final Line b = Lines.fromPointAndAngle(Vector2D.ZERO, Math.PI, TEST_PRECISION);
    1162         final Line c = Lines.fromPointAndAngle(Vector2D.of(-2, 0), -0.25 * Math.PI, TEST_PRECISION);
    1163
    1164         // act
    1165         final ConvexArea area = ConvexArea.fromBounds(a, b, c);
    1166
    1167         // assert
    1168         Assertions.assertFalse(area.isFull());
    1169         Assertions.assertFalse(area.isEmpty());
    1170
    1171         Assertions.assertEquals(4 + (2 * Math.sqrt(2)), area.getBoundarySize(), TEST_EPS);
    1172         Assertions.assertEquals(2, area.getSize(), TEST_EPS);
    1173         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(-2.0 / 3.0, -2.0 / 3.0), area.getCentroid(), TEST_EPS);
    1174
    1175         final List<LineConvexSubset> segments = area.getBoundaries();
    1176         Assertions.assertEquals(3, segments.size());
    1177
    1178         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.INSIDE, Vector2D.of(-0.5, -0.5));
    1179         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.BOUNDARY,
    1180                 Vector2D.ZERO, Vector2D.of(-1, 0), Vector2D.of(0, -1));
    1181         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.OUTSIDE,
    1182                 Vector2D.of(-1, 1), Vector2D.of(1, 1), Vector2D.of(1, -1), Vector2D.of(-2, -2));
    1183     }
    1184
    1185     @Test
    1186     void testFromBounds_square() {
    1187         // arrange
    1188         final List<Line> square = createSquareBoundingLines(Vector2D.ZERO, 1, 1);
    1189
    1190         // act
    1191         final ConvexArea area = ConvexArea.fromBounds(square);
    1192
    1193         // assert
    1194         Assertions.assertFalse(area.isFull());
    1195         Assertions.assertFalse(area.isEmpty());
    1196
    1197         Assertions.assertEquals(4, area.getBoundarySize(), TEST_EPS);
    1198         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
    1199         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
    1200
    1201         final List<LineConvexSubset> segments = area.getBoundaries();
    1202         Assertions.assertEquals(4, segments.size());
    1203
    1204         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.INSIDE, Vector2D.of(0.5, 0.5));
    1205         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.BOUNDARY,
    1206                 Vector2D.ZERO, Vector2D.of(1, 1),
    1207                 Vector2D.of(0.5, 0), Vector2D.of(0.5, 1),
    1208                 Vector2D.of(0, 0.5), Vector2D.of(1, 0.5));
    1209         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.OUTSIDE,
    1210                 Vector2D.of(-1, -1), Vector2D.of(2, 2));
    1211     }
    1212
    1213     @Test
    1214     void testFromBounds_square_extraLines() {
    1215         // arrange
    1216         final List<Line> extraLines = new ArrayList<>();
    1217         extraLines.add(Lines.fromPoints(Vector2D.of(10, 10), Vector2D.of(10, 11), TEST_PRECISION));
    1218         extraLines.add(Lines.fromPoints(Vector2D.of(-10, 10), Vector2D.of(-10, 9), TEST_PRECISION));
    1219         extraLines.add(Lines.fromPoints(Vector2D.of(0, 10), Vector2D.of(-1, 11), TEST_PRECISION));
    1220         extraLines.addAll(createSquareBoundingLines(Vector2D.ZERO, 1, 1));
    1221
    1222         // act
    1223         final ConvexArea area = ConvexArea.fromBounds(extraLines);
    1224
    1225         // assert
    1226         Assertions.assertFalse(area.isFull());
    1227         Assertions.assertFalse(area.isEmpty());
    1228
    1229         Assertions.assertEquals(4, area.getBoundarySize(), TEST_EPS);
    1230         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
    1231         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
    1232
    1233         final List<LineConvexSubset> segments = area.getBoundaries();
    1234         Assertions.assertEquals(4, segments.size());
    1235
    1236         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.INSIDE, Vector2D.of(0.5, 0.5));
    1237         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.BOUNDARY,
    1238                 Vector2D.ZERO, Vector2D.of(1, 1),
    1239                 Vector2D.of(0.5, 0), Vector2D.of(0.5, 1),
    1240                 Vector2D.of(0, 0.5), Vector2D.of(1, 0.5));
    1241         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.OUTSIDE,
    1242                 Vector2D.of(-1, -1), Vector2D.of(2, 2));
    1243     }
    1244
    1245     @Test
    1246     void testFromBounds_square_duplicateLines() {
    1247         // arrange
    1248         final List<Line> duplicateLines = new ArrayList<>();
    1249         duplicateLines.addAll(createSquareBoundingLines(Vector2D.ZERO, 1, 1));
    1250         duplicateLines.addAll(createSquareBoundingLines(Vector2D.ZERO, 1, 1));
    1251
    1252         // act
    1253         final ConvexArea area = ConvexArea.fromBounds(duplicateLines);
    1254
    1255         // assert
    1256         Assertions.assertFalse(area.isFull());
    1257         Assertions.assertFalse(area.isEmpty());
    1258
    1259         Assertions.assertEquals(4, area.getBoundarySize(), TEST_EPS);
    1260         Assertions.assertEquals(1, area.getSize(), TEST_EPS);
    1261         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), area.getCentroid(), TEST_EPS);
    1262
    1263         final List<LineConvexSubset> segments = area.getBoundaries();
    1264         Assertions.assertEquals(4, segments.size());
    1265
    1266         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.INSIDE, Vector2D.of(0.5, 0.5));
    1267         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.BOUNDARY,
    1268                 Vector2D.ZERO, Vector2D.of(1, 1),
    1269                 Vector2D.of(0.5, 0), Vector2D.of(0.5, 1),
    1270                 Vector2D.of(0, 0.5), Vector2D.of(1, 0.5));
    1271         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.OUTSIDE,
    1272                 Vector2D.of(-1, -1), Vector2D.of(2, 2));
    1273     }
    1274
    1275     @Test
    1276     void testFromBounds_duplicateLines_similarOrientation() {
    1277         // arrange
    1278         final Line a = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
    1279         final Line b = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
    1280         final Line c = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
    1281
    1282         // act
    1283         final ConvexArea area = ConvexArea.fromBounds(a, b, c);
    1284
    1285         // assert
    1286         Assertions.assertFalse(area.isFull());
    1287         Assertions.assertFalse(area.isEmpty());
    1288
    1289         GeometryTestUtils.assertPositiveInfinity(area.getBoundarySize());
    1290         GeometryTestUtils.assertPositiveInfinity(area.getSize());
    1291         Assertions.assertNull(area.getCentroid());
    1292
    1293         final List<LineConvexSubset> segments = area.getBoundaries();
    1294         Assertions.assertEquals(1, segments.size());
    1295
    1296         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.BOUNDARY, Vector2D.of(0, 1), Vector2D.of(1, 1), Vector2D.of(-1, 1));
    1297         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.INSIDE, Vector2D.of(0, 2), Vector2D.of(1, 2), Vector2D.of(-1, 2));
    1298         EuclideanTestUtils.assertRegionLocation(area, RegionLocation.OUTSIDE, Vector2D.of(0, 0), Vector2D.of(1, 0), Vector2D.of(-1, 0));
    1299     }
    1300
    1301     @Test
    1302     void testFromBounds_duplicateLines_differentOrientation() {
    1303         // arrange
    1304         final Line a = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
    1305         final Line b = Lines.fromPointAndAngle(Vector2D.of(0, 1), Math.PI, TEST_PRECISION);
    1306         final Line c = Lines.fromPointAndAngle(Vector2D.of(0, 1), 0.0, TEST_PRECISION);
    1307
    1308         // act/assert
    1309         Assertions.assertThrows(IllegalArgumentException.class, () -> ConvexArea.fromBounds(a, b, c));
    1310     }
    1311
    1312     @Test
    1313     void testFromBounds_boundsDoNotProduceAConvexRegion() {
    1314         // act/assert
    1315         Assertions.assertThrows(IllegalArgumentException.class, () -> ConvexArea.fromBounds(Arrays.asList(
    1316                 Lines.fromPointAndAngle(Vector2D.ZERO, 0.0, TEST_PRECISION),
    1317                 Lines.fromPointAndAngle(Vector2D.of(0, -1), Math.PI, TEST_PRECISION),
    1318                 Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO, TEST_PRECISION)
    1319         )));
    1320     }
    1321
    1322     private static List<Line> createSquareBoundingLines(final Vector2D lowerLeft, final double width, final double height) {
    1323         final Vector2D lowerRight = Vector2D.of(lowerLeft.getX() + width, lowerLeft.getY());
    1324         final Vector2D upperRight = Vector2D.of(lowerLeft.getX() + width, lowerLeft.getY() + height);
    1325         final Vector2D upperLeft = Vector2D.of(lowerLeft.getX(), lowerLeft.getY() + height);
    1326
    1327         return Arrays.asList(
    1328                     Lines.fromPoints(lowerLeft, lowerRight, TEST_PRECISION),
    1329                     Lines.fromPoints(upperRight, upperLeft, TEST_PRECISION),
    1330                     Lines.fromPoints(lowerRight, upperRight, TEST_PRECISION),
    1331                     Lines.fromPoints(upperLeft, lowerLeft, TEST_PRECISION)
    1332                 );
    1333     }
    1334 }