1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
50 final List<LineConvexSubset> segments = new ArrayList<>();
51
52
53 final List<LinePath> paths = connector.connectAll(segments);
54
55
56 Assertions.assertEquals(0, paths.size());
57 });
58 }
59
60 @Test
61 void testConnectAll_singleFiniteSegment() {
62 runWithMaxAndMin(connector -> {
63
64 final List<LineConvexSubset> segments = Collections.singletonList(
65 Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION)
66 );
67
68
69 final List<LinePath> paths = connector.connectAll(segments);
70
71
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
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
88 final List<LinePath> paths = connector.connectAll(segments);
89
90
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
102 final List<LineConvexSubset> segments = shuffle(createSquare(Vector2D.ZERO, 1, 1));
103
104
105 final List<LinePath> paths = connector.connectAll(segments);
106
107
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
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
132 final List<LinePath> paths = connector.connectAll(segments);
133
134
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
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
157 final List<LinePath> paths = connector.connectAll(segments);
158
159
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
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
181 final List<LinePath> paths = connector.connectAll(segments);
182
183
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
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
204 final List<LinePath> paths = connector.connectAll(segments);
205
206
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
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
230 final List<LinePath> paths = connector.connectAll(segments);
231
232
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
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
251 final List<LinePath> paths = InteriorAngleLinePathConnector.connectMaximized(segments);
252
253
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
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
272 final List<LinePath> paths = InteriorAngleLinePathConnector.connectMinimized(segments);
273
274
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
285
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 }