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.Random;
    24  import java.util.function.Consumer;
    25
    26  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    27  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    28  import org.apache.commons.geometry.euclidean.twod.Lines;
    29  import org.apache.commons.geometry.euclidean.twod.Ray;
    30  import org.apache.commons.geometry.euclidean.twod.ReverseRay;
    31  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    32  import org.apache.commons.geometry.euclidean.twod.path.InteriorAngleLinePathConnector.Maximize;
    33  import org.apache.commons.geometry.euclidean.twod.path.InteriorAngleLinePathConnector.Minimize;
    34  import org.apache.commons.numbers.angle.Angle;
    35  import org.apache.commons.numbers.core.Precision;
    36  import org.junit.jupiter.api.Assertions;
    37  import org.junit.jupiter.api.Test;
    38
    39  class InteriorAngleLinePathConnectorTest {
    40
    41      private static final double TEST_EPS = 1e-10;
    42
    43      private static final Precision.DoubleEquivalence TEST_PRECISION =
    44              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    45
    46      @Test
    47      void testConnectAll_noSegments() {
    48          runWithMaxAndMin(connector -> {
    49              // arrange
    50              final List<LineConvexSubset> segments = new ArrayList<>();
    51
    52              // act
    53              final List<LinePath> paths = connector.connectAll(segments);
    54
    55              // assert
    56              Assertions.assertEquals(0, paths.size());
    57          });
    58      }
    59
    60      @Test
    61      void testConnectAll_singleFiniteSegment() {
    62          runWithMaxAndMin(connector -> {
    63              // arrange
    64              final List<LineConvexSubset> segments = Collections.singletonList(
    65                      Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION)
    66              );
    67
    68              // act
    69              final List<LinePath> paths = connector.connectAll(segments);
    70
    71              // assert
    72              Assertions.assertEquals(1, paths.size());
    73
    74              assertFinitePath(paths.get(0), Vector2D.ZERO, Vector2D.Unit.PLUS_X);
    75          });
    76      }
    77
    78      @Test
    79      void testConnectAll_dualConnectedSegments() {
    80          runWithMaxAndMin(connector -> {
    81              // arrange
    82              final List<LineConvexSubset> segments = Arrays.asList(
    83                          Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION),
    84                          Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.ZERO, TEST_PRECISION)
    85                      );
    86
    87              // act
    88              final List<LinePath> paths = connector.connectAll(segments);
    89
    90              // assert
    91              Assertions.assertEquals(1, paths.size());
    92
    93              Assertions.assertTrue(paths.get(0).isClosed());
    94              assertFinitePath(paths.get(0), Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.ZERO);
    95          });
    96      }
    97
    98      @Test
    99      void testConnectAll_singleFiniteSegmentLoop() {
    100         runWithMaxAndMin(connector -> {
    101             // arrange
    102             final List<LineConvexSubset> segments = shuffle(createSquare(Vector2D.ZERO, 1, 1));
    103
    104             // act
    105             final List<LinePath> paths = connector.connectAll(segments);
    106
    107             // assert
    108             Assertions.assertEquals(1, paths.size());
    109
    110             assertFinitePath(paths.get(0),
    111                     Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, 1),
    112                     Vector2D.of(0, 1), Vector2D.ZERO);
    113         });
    114     }
    115
    116     @Test
    117     void testConnectAll_disjointPaths() {
    118         runWithMaxAndMin(connector -> {
    119             // arrange
    120             final List<LineConvexSubset> segments = new ArrayList<>(createSquare(Vector2D.ZERO, 1, 1));
    121
    122             final Vector2D pt = Vector2D.of(0, 2);
    123             final ReverseRay a = Lines.fromPointAndAngle(pt, 0.0, TEST_PRECISION).reverseRayTo(pt);
    124             final Ray b = Lines.fromPointAndAngle(pt, Angle.PI_OVER_TWO, TEST_PRECISION).rayFrom(pt);
    125
    126             segments.add(a);
    127             segments.add(b);
    128
    129             shuffle(segments);
    130
    131             // act
    132             final List<LinePath> paths = connector.connectAll(segments);
    133
    134             // assert
    135             Assertions.assertEquals(2, paths.size());
    136
    137             assertFinitePath(paths.get(0),
    138                     Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, 1),
    139                     Vector2D.of(0, 1), Vector2D.ZERO);
    140
    141             assertInfinitePath(paths.get(1), a, b, pt);
    142         });
    143     }
    144
    145     @Test
    146     void testConnectAll_squaresJoinedAtVertex_maximize() {
    147         // arrange
    148         final Maximize connector = new Maximize();
    149
    150         final List<LineConvexSubset> segments = new ArrayList<>();
    151         segments.addAll(createSquare(Vector2D.ZERO, 1, 1));
    152         segments.addAll(createSquare(Vector2D.of(1, 1), 1, 1));
    153
    154         shuffle(segments);
    155
    156         // act
    157         final List<LinePath> paths = connector.connectAll(segments);
    158
    159         // assert
    160         Assertions.assertEquals(1, paths.size());
    161
    162         assertFinitePath(paths.get(0),
    163                 Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, 1),
    164                 Vector2D.of(2, 1), Vector2D.of(2, 2),
    165                 Vector2D.of(1, 2), Vector2D.of(1, 1),
    166                 Vector2D.of(0, 1), Vector2D.ZERO);
    167     }
    168
    169     @Test
    170     void testConnectAll_multipleSegmentsAtVertex_maximize() {
    171         // arrange
    172         final Maximize connector = new Maximize();
    173
    174         final List<LineConvexSubset> segments = new ArrayList<>();
    175         segments.add(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(2, 2), TEST_PRECISION));
    176
    177         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(2, 4), TEST_PRECISION));
    178         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(1, 3), TEST_PRECISION));
    179
    180         // act
    181         final List<LinePath> paths = connector.connectAll(segments);
    182
    183         // assert
    184         Assertions.assertEquals(2, paths.size());
    185
    186         assertFinitePath(paths.get(0),
    187                 Vector2D.ZERO, Vector2D.of(2, 2), Vector2D.of(2, 4));
    188
    189         assertFinitePath(paths.get(1), Vector2D.of(2, 2), Vector2D.of(1, 3));
    190     }
    191
    192     @Test
    193     void testConnectAll_squaresJoinedAtVertex_minimize() {
    194         // arrange
    195         final Minimize connector = new Minimize();
    196
    197         final List<LineConvexSubset> segments = new ArrayList<>();
    198         segments.addAll(createSquare(Vector2D.ZERO, 1, 1));
    199         segments.addAll(createSquare(Vector2D.of(1, 1), 1, 1));
    200
    201         shuffle(segments);
    202
    203         // act
    204         final List<LinePath> paths = connector.connectAll(segments);
    205
    206         // assert
    207         Assertions.assertEquals(2, paths.size());
    208
    209         assertFinitePath(paths.get(0),
    210                 Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, 1),
    211                 Vector2D.of(0, 1), Vector2D.ZERO);
    212
    213         assertFinitePath(paths.get(1),
    214                 Vector2D.of(1, 1), Vector2D.of(2, 1), Vector2D.of(2, 2),
    215                 Vector2D.of(1, 2), Vector2D.of(1, 1));
    216     }
    217
    218     @Test
    219     void testConnectAll_multipleSegmentsAtVertex_minimize() {
    220         // arrange
    221         final Minimize connector = new Minimize();
    222
    223         final List<LineConvexSubset> segments = new ArrayList<>();
    224         segments.add(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(2, 2), TEST_PRECISION));
    225
    226         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(2, 4), TEST_PRECISION));
    227         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(1, 3), TEST_PRECISION));
    228
    229         // act
    230         final List<LinePath> paths = connector.connectAll(segments);
    231
    232         // assert
    233         Assertions.assertEquals(2, paths.size());
    234
    235         assertFinitePath(paths.get(0),
    236                 Vector2D.ZERO, Vector2D.of(2, 2), Vector2D.of(1, 3));
    237
    238         assertFinitePath(paths.get(1), Vector2D.of(2, 2), Vector2D.of(2, 4));
    239     }
    240
    241     @Test
    242     void testConnectMaximized() {
    243         // arrange
    244         final List<LineConvexSubset> segments = new ArrayList<>();
    245         segments.add(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(2, 2), TEST_PRECISION));
    246
    247         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(2, 4), TEST_PRECISION));
    248         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(1, 3), TEST_PRECISION));
    249
    250         // act
    251         final List<LinePath> paths = InteriorAngleLinePathConnector.connectMaximized(segments);
    252
    253         // assert
    254         Assertions.assertEquals(2, paths.size());
    255
    256         assertFinitePath(paths.get(0),
    257                 Vector2D.ZERO, Vector2D.of(2, 2), Vector2D.of(2, 4));
    258
    259         assertFinitePath(paths.get(1), Vector2D.of(2, 2), Vector2D.of(1, 3));
    260     }
    261
    262     @Test
    263     void testConnectMinimized() {
    264         // arrange
    265         final List<LineConvexSubset> segments = new ArrayList<>();
    266         segments.add(Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(2, 2), TEST_PRECISION));
    267
    268         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(2, 4), TEST_PRECISION));
    269         segments.add(Lines.segmentFromPoints(Vector2D.of(2, 2), Vector2D.of(1, 3), TEST_PRECISION));
    270
    271         // act
    272         final List<LinePath> paths = InteriorAngleLinePathConnector.connectMinimized(segments);
    273
    274         // assert
    275         Assertions.assertEquals(2, paths.size());
    276
    277         assertFinitePath(paths.get(0),
    278                 Vector2D.ZERO, Vector2D.of(2, 2), Vector2D.of(1, 3));
    279
    280         assertFinitePath(paths.get(1), Vector2D.of(2, 2), Vector2D.of(2, 4));
    281     }
    282
    283     /**
    284      * Run the given consumer function twice, once with a Maximize instance and once with
    285      * a Minimize instance.
    286      */
    287     private static void runWithMaxAndMin(final Consumer<? super InteriorAngleLinePathConnector> body) {
    288         body.accept(new Maximize());
    289         body.accept(new Minimize());
    290     }
    291
    292     private static List<LineConvexSubset> createSquare(final Vector2D lowerLeft, final double width, final double height) {
    293         final Vector2D lowerRight = Vector2D.of(lowerLeft.getX() + width, lowerLeft.getY());
    294         final Vector2D upperRight = Vector2D.of(lowerLeft.getX() + width, lowerLeft.getY() + height);
    295         final Vector2D upperLeft = Vector2D.of(lowerLeft.getX(), lowerLeft.getY() + height);
    296
    297         return Arrays.asList(
    298                     Lines.segmentFromPoints(lowerLeft, lowerRight, TEST_PRECISION),
    299                     Lines.segmentFromPoints(lowerRight, upperRight, TEST_PRECISION),
    300                     Lines.segmentFromPoints(upperRight, upperLeft, TEST_PRECISION),
    301                     Lines.segmentFromPoints(upperLeft, lowerLeft, TEST_PRECISION)
    302                 );
    303     }
    304
    305     private static List<LineConvexSubset> shuffle(final List<LineConvexSubset> segments) {
    306         return shuffle(segments, 1);
    307     }
    308
    309     private static List<LineConvexSubset> shuffle(final List<LineConvexSubset> segments, final int seed) {
    310         Collections.shuffle(segments, new Random(seed));
    311
    312         return segments;
    313     }
    314
    315     private static void assertInfinitePath(final LinePath path, final LineConvexSubset start, final LineConvexSubset end, final Vector2D... vertices) {
    316         Assertions.assertTrue(path.isInfinite());
    317         Assertions.assertFalse(path.isFinite());
    318
    319         Assertions.assertEquals(start, path.getStart());
    320         Assertions.assertEquals(end, path.getEnd());
    321
    322         assertPathVertices(path, vertices);
    323     }
    324
    325     private static void assertFinitePath(final LinePath path, final Vector2D... vertices) {
    326         Assertions.assertFalse(path.isInfinite());
    327         Assertions.assertTrue(path.isFinite());
    328
    329         assertPathVertices(path, vertices);
    330     }
    331
    332     private static void assertPathVertices(final LinePath path, final Vector2D... vertices) {
    333         final List<Vector2D> expectedVertices = Arrays.asList(vertices);
    334         final List<Vector2D> actualVertices = path.getVertexSequence();
    335
    336         final String msg = "Expected path vertices to equal " + expectedVertices + " but was " + actualVertices;
    337         Assertions.assertEquals(expectedVertices.size(), actualVertices.size(), msg);
    338
    339         for (int i = 0; i < expectedVertices.size(); ++i) {
    340             EuclideanTestUtils.assertCoordinatesEqual(expectedVertices.get(i), actualVertices.get(i), TEST_EPS);
    341         }
    342     }
    343 }