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