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