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 }