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