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
25 import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
26 import org.apache.commons.geometry.euclidean.twod.Line;
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.Segment;
30 import org.apache.commons.geometry.euclidean.twod.Vector2D;
31 import org.apache.commons.geometry.euclidean.twod.path.AbstractLinePathConnector.ConnectableLineSubset;
32 import org.apache.commons.numbers.angle.Angle;
33 import org.apache.commons.numbers.core.Precision;
34 import org.junit.jupiter.api.Assertions;
35 import org.junit.jupiter.api.Test;
36
37 class AbstractLinePathConnectorTest {
38
39 private static final double TEST_EPS = 1e-10;
40
41 private static final Precision.DoubleEquivalence TEST_PRECISION =
42 Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
43
44 private static final Line Y_AXIS = Lines.fromPointAndAngle(Vector2D.ZERO, Angle.PI_OVER_TWO,
45 TEST_PRECISION);
46
47 private final TestConnector connector = new TestConnector();
48
49 @Test
50 void testConnectAll_emptyCollection() {
51
52 final List<LinePath> paths = connector.connectAll(Collections.emptyList());
53
54
55 Assertions.assertEquals(0, paths.size());
56 }
57
58 @Test
59 void testConnectAll_singleInfiniteLine() {
60
61 final LineConvexSubset segment = Y_AXIS.span();
62
63
64 final List<LinePath> paths = connector.connectAll(Collections.singletonList(segment));
65
66
67 Assertions.assertEquals(1, paths.size());
68
69 final LinePath path = paths.get(0);
70 Assertions.assertEquals(1, path.getElements().size());
71 Assertions.assertSame(segment, path.getStart());
72 }
73
74 @Test
75 void testConnectAll_singleHalfInfiniteLine_noEndPoint() {
76
77 final LineConvexSubset segment = Y_AXIS.rayFrom(Vector2D.ZERO);
78
79
80 final List<LinePath> paths = connector.connectAll(Collections.singletonList(segment));
81
82
83 Assertions.assertEquals(1, paths.size());
84
85 final LinePath path = paths.get(0);
86 Assertions.assertEquals(1, path.getElements().size());
87 Assertions.assertSame(segment, path.getStart());
88 }
89
90 @Test
91 void testConnectAll_singleHalfInfiniteLine_noStartPoint() {
92
93 final LineConvexSubset segment = Y_AXIS.reverseRayTo(Vector2D.ZERO);
94
95
96 final List<LinePath> paths = connector.connectAll(Collections.singletonList(segment));
97
98
99 Assertions.assertEquals(1, paths.size());
100
101 final LinePath path = paths.get(0);
102 Assertions.assertEquals(1, path.getElements().size());
103 Assertions.assertSame(segment, path.getStart());
104 }
105
106 @Test
107 void testConnectAll_disjointSegments() {
108
109 final LineConvexSubset a = Y_AXIS.segment(Vector2D.of(0, 1), Vector2D.of(0, 2));
110 final LineConvexSubset b = Y_AXIS.segment(Vector2D.of(0, -1), Vector2D.ZERO);
111
112 final List<LineConvexSubset> segments = Arrays.asList(a, b);
113
114
115 final List<LinePath> paths = connector.connectAll(segments);
116
117
118 Assertions.assertEquals(2, paths.size());
119
120 assertFinitePath(paths.get(0), Vector2D.of(0, -1), Vector2D.ZERO);
121 assertFinitePath(paths.get(1), Vector2D.of(0, 1), Vector2D.of(0, 2));
122 }
123
124 @Test
125 void testConnectAll_singleClosedPath() {
126
127 final LinePath input = LinePath.builder(TEST_PRECISION)
128 .appendVertices(Vector2D.of(1, 1), Vector2D.ZERO, Vector2D.of(1, 0))
129 .close();
130
131 final List<LineConvexSubset> segments = new ArrayList<>(input.getElements());
132 shuffle(segments);
133
134
135 final List<LinePath> paths = connector.connectAll(segments);
136
137
138 Assertions.assertEquals(1, paths.size());
139
140 assertFinitePath(paths.get(0),
141 Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(1, 1), Vector2D.ZERO);
142 }
143
144 @Test
145 void testConnectAll_multipleClosedPaths() {
146
147 final LinePath a = LinePath.builder(TEST_PRECISION)
148 .appendVertices(Vector2D.of(1, 1), Vector2D.ZERO, Vector2D.of(1, 0))
149 .close();
150
151 final LinePath b = LinePath.builder(TEST_PRECISION)
152 .appendVertices(Vector2D.of(0, 1), Vector2D.of(-1, 0), Vector2D.of(-0.5, 0))
153 .close();
154
155 final LinePath c = LinePath.builder(TEST_PRECISION)
156 .appendVertices(Vector2D.of(1, 3), Vector2D.of(0, 2), Vector2D.of(1, 2))
157 .close();
158
159 final List<LineConvexSubset> segments = new ArrayList<>();
160 segments.addAll(a.getElements());
161 segments.addAll(b.getElements());
162 segments.addAll(c.getElements());
163
164 shuffle(segments);
165
166
167 final List<LinePath> paths = connector.connectAll(segments);
168
169
170 Assertions.assertEquals(3, paths.size());
171
172 assertFinitePath(paths.get(0),
173 Vector2D.of(-1, 0), Vector2D.of(-0.5, 0), Vector2D.of(0, 1), Vector2D.of(-1, 0));
174
175 assertFinitePath(paths.get(1),
176 Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(1, 1), Vector2D.ZERO);
177
178 assertFinitePath(paths.get(2),
179 Vector2D.of(0, 2), Vector2D.of(1, 2), Vector2D.of(1, 3), Vector2D.of(0, 2));
180 }
181
182 @Test
183 void testConnectAll_singleOpenPath() {
184
185 final LinePath input = LinePath.builder(TEST_PRECISION)
186 .appendVertices(Vector2D.of(1, 1), Vector2D.ZERO, Vector2D.of(1, 0))
187 .build();
188
189 final List<LineConvexSubset> segments = new ArrayList<>(input.getElements());
190 shuffle(segments);
191
192
193 final List<LinePath> paths = connector.connectAll(segments);
194
195
196 Assertions.assertEquals(1, paths.size());
197
198 assertFinitePath(paths.get(0),
199 Vector2D.of(1, 1), Vector2D.ZERO, Vector2D.of(1, 0));
200 }
201
202 @Test
203 void testConnectAll_mixOfOpenConnectedAndInfinite() {
204
205 final LineConvexSubset inputYInf = Y_AXIS.reverseRayTo(Vector2D.ZERO);
206 final LineConvexSubset inputXInf = Lines.fromPoints(Vector2D.ZERO, Vector2D.Unit.MINUS_X, TEST_PRECISION)
207 .rayFrom(Vector2D.ZERO);
208
209 final LinePath closedPath = LinePath.builder(TEST_PRECISION)
210 .appendVertices(Vector2D.of(0, 2), Vector2D.of(1, 2), Vector2D.of(1, 3))
211 .close();
212
213 final LinePath openPath = LinePath.builder(TEST_PRECISION)
214 .appendVertices(Vector2D.of(-1, 3), Vector2D.of(0, 1), Vector2D.of(1, 1))
215 .build();
216
217 final List<LineConvexSubset> segments = new ArrayList<>();
218 segments.add(inputYInf);
219 segments.add(inputXInf);
220 segments.addAll(closedPath.getElements());
221 segments.addAll(openPath.getElements());
222
223 shuffle(segments);
224
225
226 final List<LinePath> paths = connector.connectAll(segments);
227
228
229 Assertions.assertEquals(3, paths.size());
230
231 assertFinitePath(paths.get(0),
232 Vector2D.of(-1, 3), Vector2D.of(0, 1), Vector2D.of(1, 1));
233
234 final LinePath infPath = paths.get(1);
235 Assertions.assertTrue(infPath.isInfinite());
236 Assertions.assertEquals(2, infPath.getElements().size());
237 Assertions.assertSame(inputYInf, infPath.getElements().get(0));
238 Assertions.assertSame(inputXInf, infPath.getElements().get(1));
239
240 assertFinitePath(paths.get(2),
241 Vector2D.of(0, 2), Vector2D.of(1, 2), Vector2D.of(1, 3), Vector2D.of(0, 2));
242 }
243
244 @Test
245 void testConnectAll_pathWithSinglePoint() {
246
247 final Vector2D p0 = Vector2D.ZERO;
248
249 final List<LineConvexSubset> segments = Collections.singletonList(Lines.fromPointAndAngle(p0, 0, TEST_PRECISION).segment(p0, p0));
250
251
252 final List<LinePath> paths = connector.connectAll(segments);
253
254
255 Assertions.assertEquals(1, paths.size());
256
257 assertFinitePath(paths.get(0), p0, p0);
258 }
259
260 @Test
261 void testConnectAll_pathWithPointLikeConnectedSegments() {
262
263 final Vector2D p0 = Vector2D.ZERO;
264 final Vector2D p1 = Vector2D.of(1, 0);
265 final Vector2D p2 = Vector2D.of(1, 1);
266
267 final Vector2D almostP0 = Vector2D.of(-1e-20, -1e-20);
268 final Vector2D almostP1 = Vector2D.of(1 - 1e-15, 0);
269
270 final LinePath input = LinePath.builder(TEST_PRECISION)
271 .appendVertices(p0, p1)
272 .append(Lines.fromPointAndAngle(p1, 0.25 * Math.PI, TEST_PRECISION).segment(p1, p1))
273 .append(Lines.fromPointAndAngle(p1, -0.25 * Math.PI, TEST_PRECISION).segment(almostP1, almostP1))
274 .append(p2)
275 .append(p0)
276 .append(Lines.fromPointAndAngle(Vector2D.ZERO, -Angle.PI_OVER_TWO, TEST_PRECISION)
277 .segment(almostP0, almostP0))
278 .build();
279
280 final List<LineConvexSubset> segments = new ArrayList<>(input.getElements());
281 shuffle(segments);
282
283
284 final List<LinePath> paths = connector.connectAll(segments);
285
286
287 Assertions.assertEquals(1, paths.size());
288
289 assertFinitePath(paths.get(0), p0, p1, almostP1, p1, p2, p0, almostP0);
290 }
291
292 @Test
293 void testConnectAll_flatLineRegion() {
294
295 final Vector2D p0 = Vector2D.ZERO;
296 final Vector2D p1 = Vector2D.of(1, 0);
297
298 final Segment seg0 = Lines.segmentFromPoints(p0, p1, TEST_PRECISION);
299 final Segment seg1 = Lines.segmentFromPoints(p1, p0, TEST_PRECISION);
300 final LineConvexSubset seg2 = Lines.fromPointAndAngle(p1, Angle.PI_OVER_TWO, TEST_PRECISION).segment(p1, p1);
301 final LineConvexSubset seg3 = Lines.fromPointAndAngle(p0, -Angle.PI_OVER_TWO, TEST_PRECISION).segment(p0, p0);
302
303 final List<LineConvexSubset> segments = new ArrayList<>(Arrays.asList(seg0, seg1, seg2, seg3));
304 shuffle(segments);
305
306
307 final List<LinePath> paths = connector.connectAll(segments);
308
309
310 Assertions.assertEquals(1, paths.size());
311
312 final LinePath path = paths.get(0);
313 Assertions.assertSame(seg0, path.getElements().get(0));
314 Assertions.assertSame(seg2, path.getElements().get(1));
315 Assertions.assertSame(seg1, path.getElements().get(2));
316 Assertions.assertSame(seg3, path.getElements().get(3));
317 }
318
319 @Test
320 void testConnectAll_singlePointRegion() {
321
322 final Vector2D p0 = Vector2D.of(1, 0);
323
324 final LineConvexSubset seg0 = Lines.fromPointAndAngle(p0, 0.0, TEST_PRECISION).segment(p0, p0);
325 final LineConvexSubset seg1 = Lines.fromPointAndAngle(p0, Angle.PI_OVER_TWO, TEST_PRECISION).segment(p0, p0);
326 final LineConvexSubset seg2 = Lines.fromPointAndAngle(p0, Math.PI, TEST_PRECISION).segment(p0, p0);
327 final LineConvexSubset seg3 = Lines.fromPointAndAngle(p0, -Angle.PI_OVER_TWO, TEST_PRECISION).segment(p0, p0);
328
329 final List<LineConvexSubset> segments = new ArrayList<>(Arrays.asList(seg0, seg1, seg2, seg3));
330 shuffle(segments);
331
332
333 final List<LinePath> paths = connector.connectAll(segments);
334
335
336 Assertions.assertEquals(1, paths.size());
337
338 final LinePath path = paths.get(0);
339 Assertions.assertSame(seg2, path.getElements().get(0));
340 Assertions.assertSame(seg3, path.getElements().get(1));
341 Assertions.assertSame(seg0, path.getElements().get(2));
342 Assertions.assertSame(seg1, path.getElements().get(3));
343 }
344
345 @Test
346 void testConnectAll_pathWithPointLikeUnconnectedSegments() {
347
348 final Vector2D p0 = Vector2D.ZERO;
349 final Vector2D p1 = Vector2D.of(1, 0);
350
351 final LineConvexSubset seg0 = Lines.fromPointAndAngle(p1, 0.0, TEST_PRECISION).segment(p1, p1);
352 final LineConvexSubset seg1 = Lines.fromPointAndAngle(p1, 0.25 * Math.PI, TEST_PRECISION).segment(p1, p1);
353 final LineConvexSubset seg2 = Lines.fromPointAndAngle(p0, 0, TEST_PRECISION).segment(p0, p0);
354
355 final List<LineConvexSubset> segments = new ArrayList<>(Arrays.asList(seg0, seg1, seg2));
356
357 shuffle(segments);
358
359
360 final List<LinePath> paths = connector.connectAll(segments);
361
362
363 Assertions.assertEquals(2, paths.size());
364
365 final LinePath path0 = paths.get(0);
366 Assertions.assertEquals(1, path0.getElements().size());
367 Assertions.assertSame(seg2, path0.getElements().get(0));
368
369 final LinePath path1 = paths.get(1);
370 Assertions.assertEquals(2, path1.getElements().size());
371 Assertions.assertSame(seg0, path1.getElements().get(0));
372 Assertions.assertSame(seg1, path1.getElements().get(1));
373 }
374
375 @Test
376 void testConnectAll_pathStartingWithPoint() {
377
378 final Vector2D p0 = Vector2D.ZERO;
379 final Vector2D p1 = Vector2D.of(1, 0);
380 final Vector2D p2 = Vector2D.of(1, 1);
381
382 final LineConvexSubset seg0 = Lines.fromPointAndAngle(p0, Math.PI, TEST_PRECISION).segment(p0, p0);
383 final LineConvexSubset seg1 = Lines.segmentFromPoints(p0, p1, TEST_PRECISION);
384 final LineConvexSubset seg2 = Lines.segmentFromPoints(p1, p2, TEST_PRECISION);
385
386 final List<LineConvexSubset> segments = new ArrayList<>(Arrays.asList(seg0, seg1, seg2));
387
388 shuffle(segments);
389
390
391 final List<LinePath> paths = connector.connectAll(segments);
392
393
394 Assertions.assertEquals(1, paths.size());
395
396 final LinePath path = paths.get(0);
397 Assertions.assertSame(seg0, path.getElements().get(0));
398 Assertions.assertSame(seg1, path.getElements().get(1));
399 Assertions.assertSame(seg2, path.getElements().get(2));
400 }
401
402 @Test
403 void testConnectAll_intersectingPaths() {
404
405 final LinePath a = LinePath.builder(TEST_PRECISION)
406 .appendVertices(Vector2D.of(-1, 1), Vector2D.of(0.5, 0), Vector2D.of(-1, -1))
407 .build();
408
409 final LinePath b = LinePath.builder(TEST_PRECISION)
410 .appendVertices(Vector2D.of(1, 1), Vector2D.of(-0.5, 0), Vector2D.of(1, -1))
411 .build();
412
413 final List<LineConvexSubset> segments = new ArrayList<>();
414 segments.addAll(a.getElements());
415 segments.addAll(b.getElements());
416
417 shuffle(segments);
418
419
420 final List<LinePath> paths = connector.connectAll(segments);
421
422
423 Assertions.assertEquals(2, paths.size());
424
425 assertFinitePath(paths.get(0),
426 Vector2D.of(-1, 1), Vector2D.of(0.5, 0), Vector2D.of(-1, -1));
427
428 assertFinitePath(paths.get(1),
429 Vector2D.of(1, 1), Vector2D.of(-0.5, 0), Vector2D.of(1, -1));
430 }
431
432 @Test
433 void testInstancesCanBeReused() {
434
435 final LineConvexSubset a = Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
436 final LineConvexSubset b = Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y, TEST_PRECISION);
437
438
439 final List<LinePath> firstPaths = connector.connectAll(Collections.singletonList(a));
440 final List<LinePath> secondPaths = connector.connectAll(Collections.singletonList(b));
441
442
443 Assertions.assertEquals(1, firstPaths.size());
444 Assertions.assertEquals(1, secondPaths.size());
445
446 Assertions.assertSame(a, firstPaths.get(0).getElements().get(0));
447 Assertions.assertSame(b, secondPaths.get(0).getElements().get(0));
448 }
449
450 @Test
451 void testAdd() {
452
453 final LineConvexSubset a = Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
454 final LineConvexSubset b = Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.of(1, 1), TEST_PRECISION);
455 final LineConvexSubset c = Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.of(2, 0), TEST_PRECISION);
456
457
458 connector.add(Arrays.asList(a, b));
459 connector.add(Collections.singletonList(c));
460
461 final List<LinePath> paths = connector.connectAll();
462
463
464 Assertions.assertEquals(2, paths.size());
465
466 assertFinitePath(paths.get(0), Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(2, 0));
467 assertFinitePath(paths.get(1), Vector2D.Unit.PLUS_X, Vector2D.of(1, 1));
468 }
469
470 @Test
471 void testConnect() {
472
473 final LineConvexSubset a = Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
474 final LineConvexSubset b = Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.of(1, 1), TEST_PRECISION);
475 final LineConvexSubset c = Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.of(2, 0), TEST_PRECISION);
476
477
478 connector.connect(Arrays.asList(a, b));
479 connector.connect(Collections.singletonList(c));
480
481 final List<LinePath> paths = connector.connectAll();
482
483
484 Assertions.assertEquals(2, paths.size());
485
486 assertFinitePath(paths.get(0), Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, 1));
487 assertFinitePath(paths.get(1), Vector2D.Unit.PLUS_X, Vector2D.of(2, 0));
488 }
489
490 @Test
491 void testConnectableSegment_hashCode() {
492
493 final LineConvexSubset segA = Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
494 final LineConvexSubset segB = Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.of(1, 1), TEST_PRECISION);
495
496 final ConnectableLineSubset a = new ConnectableLineSubset(segA);
497
498
499 final int hash = a.hashCode();
500
501
502 Assertions.assertEquals(hash, a.hashCode());
503
504 Assertions.assertNotEquals(hash, new ConnectableLineSubset(segB).hashCode());
505 Assertions.assertNotEquals(hash, new ConnectableLineSubset(Vector2D.Unit.PLUS_X).hashCode());
506
507 Assertions.assertEquals(hash, new ConnectableLineSubset(segA).hashCode());
508 }
509
510 @Test
511 void testConnectableSegment_equals() {
512
513 final LineConvexSubset segA = Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
514 final LineConvexSubset segB = Lines.segmentFromPoints(Vector2D.Unit.PLUS_X, Vector2D.of(1, 1), TEST_PRECISION);
515
516 final ConnectableLineSubset a = new ConnectableLineSubset(segA);
517
518
519 Assertions.assertEquals(a, a);
520
521 Assertions.assertFalse(a.equals(null));
522 Assertions.assertFalse(a.equals(new Object()));
523
524 Assertions.assertNotEquals(a, new ConnectableLineSubset(segB));
525 Assertions.assertNotEquals(a, new ConnectableLineSubset(Vector2D.Unit.PLUS_X));
526
527 Assertions.assertEquals(a, new ConnectableLineSubset(segA));
528 }
529
530 private static List<LineConvexSubset> shuffle(final List<LineConvexSubset> segments) {
531 return shuffle(segments, 1);
532 }
533
534 private static List<LineConvexSubset> shuffle(final List<LineConvexSubset> segments, final int seed) {
535 Collections.shuffle(segments, new Random(seed));
536
537 return segments;
538 }
539
540 private static void assertFinitePath(final LinePath path, final Vector2D... vertices) {
541 Assertions.assertFalse(path.isInfinite());
542 Assertions.assertTrue(path.isFinite());
543
544 assertPathVertices(path, vertices);
545 }
546
547 private static void assertPathVertices(final LinePath path, final Vector2D... vertices) {
548 final List<Vector2D> expectedVertices = Arrays.asList(vertices);
549 final List<Vector2D> actualVertices = path.getVertexSequence();
550
551 final String msg = "Expected path vertices to equal " + expectedVertices + " but was " + actualVertices;
552 Assertions.assertEquals(expectedVertices.size(), actualVertices.size(), msg);
553
554 for (int i = 0; i < expectedVertices.size(); ++i) {
555 EuclideanTestUtils.assertCoordinatesEqual(expectedVertices.get(i), actualVertices.get(i), TEST_EPS);
556 }
557 }
558
559 private static class TestConnector extends AbstractLinePathConnector {
560
561 @Override
562 protected ConnectableLineSubset selectConnection(final ConnectableLineSubset incoming, final List<ConnectableLineSubset> outgoing) {
563
564 return outgoing.get(0);
565 }
566 }
567 }