1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.geometry.euclidean.twod.shape;
18
19 import java.util.ArrayList;
20 import java.util.Comparator;
21 import java.util.List;
22
23 import org.apache.commons.geometry.core.GeometryTestUtils;
24 import org.apache.commons.geometry.core.RegionLocation;
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.LinecastPoint2D;
29 import org.apache.commons.geometry.euclidean.twod.Lines;
30 import org.apache.commons.geometry.euclidean.twod.PolarCoordinates;
31 import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
32 import org.apache.commons.geometry.euclidean.twod.Vector2D;
33 import org.apache.commons.geometry.euclidean.twod.path.LinePath;
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 CircleTest {
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 private static final Comparator<LineConvexSubset> SEGMENT_DIRECTION_COMPARATOR =
47 (a, b) -> Vector2D.COORDINATE_ASCENDING_ORDER.compare(
48 a.getLine().getDirection(),
49 b.getLine().getDirection());
50
51 @Test
52 void testFrom() {
53
54 final Vector2D center = Vector2D.of(1, 2);
55
56
57 final Circle c = Circle.from(center, 3, TEST_PRECISION);
58
59
60 Assertions.assertFalse(c.isFull());
61 Assertions.assertFalse(c.isEmpty());
62
63 Assertions.assertSame(center, c.getCenter());
64 Assertions.assertSame(center, c.getCentroid());
65
66 Assertions.assertEquals(3, c.getRadius(), 0.0);
67
68 Assertions.assertSame(TEST_PRECISION, c.getPrecision());
69 }
70
71 @Test
72 void testFrom_illegalCenter() {
73
74 Assertions.assertThrows(IllegalArgumentException.class, () -> Circle.from(Vector2D.of(Double.POSITIVE_INFINITY, 1), 1, TEST_PRECISION));
75 Assertions.assertThrows(IllegalArgumentException.class, () -> Circle.from(Vector2D.of(Double.NaN, 1), 1, TEST_PRECISION));
76 }
77
78 @Test
79 void testFrom_illegalRadius() {
80
81 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
82
83
84 Assertions.assertThrows(IllegalArgumentException.class, () -> Circle.from(Vector2D.ZERO, -1, TEST_PRECISION));
85 Assertions.assertThrows(IllegalArgumentException.class, () -> Circle.from(Vector2D.ZERO, 0, TEST_PRECISION));
86 Assertions.assertThrows(IllegalArgumentException.class, () -> Circle.from(Vector2D.ZERO, Double.POSITIVE_INFINITY, TEST_PRECISION));
87 Assertions.assertThrows(IllegalArgumentException.class, () -> Circle.from(Vector2D.ZERO, Double.NaN, TEST_PRECISION));
88 Assertions.assertThrows(IllegalArgumentException.class, () -> Circle.from(Vector2D.ZERO, 1e-3, precision));
89 }
90
91 @Test
92 void testGeometricProperties() {
93
94 final double r = 2;
95 final Circle c = Circle.from(Vector2D.of(1, 2), r, TEST_PRECISION);
96
97
98 Assertions.assertEquals(2 * Math.PI * r, c.getBoundarySize(), TEST_EPS);
99 Assertions.assertEquals(Math.PI * r * r, c.getSize(), TEST_EPS);
100 }
101
102 @Test
103 void testClassify() {
104
105 final Circle c = Circle.from(Vector2D.of(1, 2), 1, TEST_PRECISION);
106
107
108 EuclideanTestUtils.assertRegionLocation(c, RegionLocation.INSIDE,
109 Vector2D.of(1, 2),
110 Vector2D.of(0.5, 2), Vector2D.of(1.5, 2),
111 Vector2D.of(1, 1.5), Vector2D.of(1, 2.5),
112 Vector2D.of(0.5, 1.5), Vector2D.of(1.5, 2.5),
113 Vector2D.of(0.5, 2.5), Vector2D.of(1.5, 1.5));
114
115 EuclideanTestUtils.assertRegionLocation(c, RegionLocation.OUTSIDE,
116 Vector2D.of(-0.5, 2), Vector2D.of(2.5, 2),
117 Vector2D.of(1, 0.5), Vector2D.of(1, 3.5),
118 Vector2D.of(0.25, 1.25), Vector2D.of(1.75, 2.75),
119 Vector2D.of(0.25, 2.75), Vector2D.of(1.75, 1.25));
120
121 for (double angle = 0; angle < Angle.TWO_PI; angle += 0.1) {
122 EuclideanTestUtils.assertRegionLocation(c, RegionLocation.BOUNDARY,
123 c.getCenter().add(PolarCoordinates.of(1, angle).toCartesian()));
124 }
125 }
126
127 @Test
128 void testContains() {
129
130 final Circle c = Circle.from(Vector2D.of(1, 2), 1, TEST_PRECISION);
131
132
133 checkContains(c, true,
134 Vector2D.of(1, 2),
135 Vector2D.of(0.5, 2), Vector2D.of(1.5, 2),
136 Vector2D.of(1, 1.5), Vector2D.of(1, 2.5),
137 Vector2D.of(0.5, 1.5), Vector2D.of(1.5, 2.5),
138 Vector2D.of(0.5, 2.5), Vector2D.of(1.5, 1.5));
139
140 for (double angle = 0; angle < Angle.TWO_PI; angle += 0.1) {
141 checkContains(c, true,
142 c.getCenter().add(PolarCoordinates.of(1, angle).toCartesian()));
143 }
144
145 checkContains(c, false,
146 Vector2D.of(-0.5, 2), Vector2D.of(2.5, 2),
147 Vector2D.of(1, 0.5), Vector2D.of(1, 3.5),
148 Vector2D.of(0.25, 1.25), Vector2D.of(1.75, 2.75),
149 Vector2D.of(0.25, 2.75), Vector2D.of(1.75, 1.25));
150 }
151
152 @Test
153 void testProject() {
154
155 final Vector2D center = Vector2D.of(1.5, 2.5);
156 final double radius = 3;
157 final Circle c = Circle.from(center, radius, TEST_PRECISION);
158
159 EuclideanTestUtils.permute(-4, 4, 1, (x, y) -> {
160 final Vector2D pt = Vector2D.of(x, y);
161
162
163 final Vector2D projection = c.project(pt);
164
165
166 Assertions.assertEquals(radius, center.distance(projection), TEST_EPS);
167 EuclideanTestUtils.assertCoordinatesEqual(center.directionTo(pt),
168 center.directionTo(projection), TEST_EPS);
169 });
170 }
171
172 @Test
173 void testProject_argumentEqualsCenter() {
174
175 final Circle c = Circle.from(Vector2D.of(1, 2), 2, TEST_PRECISION);
176
177
178 final Vector2D projection = c.project(Vector2D.of(1, 2));
179
180
181 EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 2), projection, TEST_EPS);
182 }
183
184 @Test
185 void testIntersections() {
186
187 final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
188 final double sqrt3 = Math.sqrt(3);
189
190
191
192 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 4), Vector2D.of(5, 4), TEST_PRECISION));
193 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 3), Vector2D.of(5, 3), TEST_PRECISION),
194 Vector2D.of(2, 3));
195 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 2), Vector2D.of(5, 2), TEST_PRECISION),
196 Vector2D.of(2 - sqrt3, 2), Vector2D.of(2 + sqrt3, 2));
197 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 1), Vector2D.of(5, 1), TEST_PRECISION),
198 Vector2D.of(0, 1), Vector2D.of(4, 1));
199 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 0), Vector2D.of(5, 0), TEST_PRECISION),
200 Vector2D.of(2 - sqrt3, 0), Vector2D.of(2 + sqrt3, 0));
201 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, -1), Vector2D.of(5, -1), TEST_PRECISION),
202 Vector2D.of(2, -1));
203 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, -2), Vector2D.of(5, -2), TEST_PRECISION));
204
205
206 checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, -2), Vector2D.of(-1, 5), TEST_PRECISION));
207 checkIntersections(c, Lines.fromPoints(Vector2D.of(0, -2), Vector2D.of(0, 5), TEST_PRECISION),
208 Vector2D.of(0, 1));
209 checkIntersections(c, Lines.fromPoints(Vector2D.of(1, -2), Vector2D.of(1, 5), TEST_PRECISION),
210 Vector2D.of(1, 1 - sqrt3), Vector2D.of(1, 1 + sqrt3));
211 checkIntersections(c, Lines.fromPoints(Vector2D.of(2, -2), Vector2D.of(2, 5), TEST_PRECISION),
212 Vector2D.of(2, -1), Vector2D.of(2, 3));
213 checkIntersections(c, Lines.fromPoints(Vector2D.of(3, -2), Vector2D.of(3, 5), TEST_PRECISION),
214 Vector2D.of(3, 1 - sqrt3), Vector2D.of(3, 1 + sqrt3));
215 checkIntersections(c, Lines.fromPoints(Vector2D.of(4, -2), Vector2D.of(4, 5), TEST_PRECISION),
216 Vector2D.of(4, 1));
217 checkIntersections(c, Lines.fromPoints(Vector2D.of(5, -2), Vector2D.of(5, 5), TEST_PRECISION));
218
219
220 final Vector2D center = c.getCenter();
221 checkIntersections(c, Lines.fromPoints(Vector2D.ZERO, c.getCenter(), TEST_PRECISION),
222 center.withNorm(center.norm() - c.getRadius()), center.withNorm(center.norm() + c.getRadius()));
223 }
224
225 @Test
226 void testLinecast() {
227
228 final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
229 final double sqrt3 = Math.sqrt(3);
230
231
232 checkLinecast(c, Lines.segmentFromPoints(Vector2D.of(-1, 0), Vector2D.of(5, 0), TEST_PRECISION),
233 Vector2D.of(2 - sqrt3, 0), Vector2D.of(2 + sqrt3, 0));
234 checkLinecast(c, Lines.segmentFromPoints(Vector2D.of(-1, 3), Vector2D.of(5, 3), TEST_PRECISION),
235 Vector2D.of(2, 3));
236 checkLinecast(c, Lines.segmentFromPoints(Vector2D.of(-1, -2), Vector2D.of(5, -2), TEST_PRECISION));
237 }
238
239 @Test
240 void testLinecast_intersectionsNotInSegment() {
241
242 final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
243 final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION);
244
245
246 checkLinecast(c, line.segment(-1, 0));
247 checkLinecast(c, line.segment(1.5, 2.5));
248 checkLinecast(c, line.segment(1.5, 2.5));
249 checkLinecast(c, line.segment(4, 5));
250 }
251
252 @Test
253 void testLinecast_segmentPointOnBoundary() {
254
255 final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
256 final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION);
257 final double sqrt3 = Math.sqrt(3);
258 final double start = 2 - sqrt3;
259 final double end = 2 + sqrt3;
260
261
262 checkLinecast(c, line.segment(start, 2), Vector2D.of(start, 0));
263 checkLinecast(c, line.segment(start, end), Vector2D.of(start, 0), Vector2D.of(end, 0));
264 checkLinecast(c, line.segment(end, 5), Vector2D.of(end, 0));
265 }
266
267 @Test
268 void testToTree_threeSegments() {
269
270 final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
271
272
273 final RegionBSPTree2D tree = c.toTree(3);
274
275
276 checkBasicApproximationProperties(c, tree);
277
278 final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
279 segments.sort(SEGMENT_DIRECTION_COMPARATOR);
280
281 Assertions.assertEquals(3, segments.size());
282
283 final double inc = Angle.TWO_PI / 3.0;
284 final Vector2D p0 = Vector2D.of(4, 1);
285 final Vector2D p1 = Vector2D.of(
286 (2 * Math.cos(inc)) + 2,
287 (2 * Math.sin(inc)) + 1);
288 final Vector2D p2 = Vector2D.of(
289 (2 * Math.cos(2 * inc)) + 2,
290 (2 * Math.sin(2 * inc)) + 1);
291
292 assertFiniteSegment(segments.get(0), p0, p1);
293 assertFiniteSegment(segments.get(1), p1, p2);
294 assertFiniteSegment(segments.get(2), p2, p0);
295 }
296
297 @Test
298 void testToTree_fourSegments() {
299
300 final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
301
302
303 final RegionBSPTree2D tree = c.toTree(4);
304
305
306 checkBasicApproximationProperties(c, tree);
307
308 final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
309 segments.sort(SEGMENT_DIRECTION_COMPARATOR);
310
311 Assertions.assertEquals(4, segments.size());
312
313 final Vector2D p0 = Vector2D.of(4, 1);
314 final Vector2D p1 = Vector2D.of(2, 3);
315 final Vector2D p2 = Vector2D.of(0, 1);
316 final Vector2D p3 = Vector2D.of(2, -1);
317
318 assertFiniteSegment(segments.get(0), p1, p2);
319 assertFiniteSegment(segments.get(1), p0, p1);
320 assertFiniteSegment(segments.get(2), p2, p3);
321 assertFiniteSegment(segments.get(3), p3, p0);
322 }
323
324 @Test
325 void testToTree_multipleApproximationSizes() {
326
327 final Circle c = Circle.from(Vector2D.of(-3, 5), 10, TEST_PRECISION);
328
329 final int min = 5;
330 final int max = 100;
331
332 RegionBSPTree2D tree;
333
334 double sizeDiff;
335 double prevSizeDiff = Double.POSITIVE_INFINITY;
336
337 for (int n = min; n <= max; ++n) {
338
339 tree = c.toTree(n);
340
341
342 checkBasicApproximationProperties(c, tree);
343
344
345 sizeDiff = c.getSize() - tree.getSize();
346 Assertions.assertTrue(sizeDiff < prevSizeDiff, "Expected size difference to decrease");
347
348 prevSizeDiff = sizeDiff;
349 }
350 }
351
352 @Test
353 void testToTree_closeApproximation() {
354
355 final Circle c = Circle.from(Vector2D.of(-2, 0), 1, TEST_PRECISION);
356
357
358 final RegionBSPTree2D tree = c.toTree(100);
359
360
361 checkBasicApproximationProperties(c, tree);
362
363 final double eps = 5e-3;
364 Assertions.assertEquals(c.getSize(), tree.getSize(), eps);
365 Assertions.assertEquals(c.getBoundarySize(), tree.getBoundarySize(), eps);
366 EuclideanTestUtils.assertCoordinatesEqual(c.getCentroid(), tree.getCentroid(), eps);
367 }
368
369 @Test
370 void testToTree_invalidSegmentCount() {
371
372 final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
373 final String baseMsg = "Circle approximation segment number must be greater than or equal to 3; was ";
374
375
376 GeometryTestUtils.assertThrowsWithMessage(() -> {
377 c.toTree(2);
378 }, IllegalArgumentException.class, baseMsg + "2");
379 GeometryTestUtils.assertThrowsWithMessage(() -> {
380 c.toTree(-1);
381 }, IllegalArgumentException.class, baseMsg + "-1");
382 }
383
384 @Test
385 void testHashCode() {
386
387 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
388
389 final Circle a = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
390 final Circle b = Circle.from(Vector2D.of(1, 1), 3, TEST_PRECISION);
391 final Circle c = Circle.from(Vector2D.of(1, 2), 4, TEST_PRECISION);
392 final Circle d = Circle.from(Vector2D.of(1, 2), 3, precision);
393 final Circle e = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
394
395
396 final int hash = a.hashCode();
397
398
399 Assertions.assertEquals(hash, a.hashCode());
400
401 Assertions.assertNotEquals(hash, b.hashCode());
402 Assertions.assertNotEquals(hash, c.hashCode());
403 Assertions.assertNotEquals(hash, d.hashCode());
404
405 Assertions.assertEquals(hash, e.hashCode());
406 }
407
408 @Test
409 void testEquals() {
410
411 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
412
413 final Circle a = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
414 final Circle b = Circle.from(Vector2D.of(1, 1), 3, TEST_PRECISION);
415 final Circle c = Circle.from(Vector2D.of(1, 2), 4, TEST_PRECISION);
416 final Circle d = Circle.from(Vector2D.of(1, 2), 3, precision);
417 final Circle e = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
418
419
420 GeometryTestUtils.assertSimpleEqualsCases(a);
421
422 Assertions.assertNotEquals(a, b);
423 Assertions.assertNotEquals(a, c);
424 Assertions.assertNotEquals(a, d);
425
426 Assertions.assertEquals(a, e);
427 }
428
429 @Test
430 void testToString() {
431
432 final Circle c = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
433
434
435 final String str = c.toString();
436
437
438 Assertions.assertEquals("Circle[center= (1.0, 2.0), radius= 3.0]", str);
439 }
440
441 private static void checkContains(final Circle circle, final boolean contains, final Vector2D... pts) {
442 for (final Vector2D pt : pts) {
443 Assertions.assertEquals(contains, circle.contains(pt),
444 "Expected circle to " + (contains ? "" : "not") + "contain point " + pt);
445 }
446 }
447
448 private static void checkIntersections(final Circle circle, final Line line, final Vector2D... expectedPts) {
449
450
451 final List<Vector2D> actualPtsForward = circle.intersections(line);
452 final List<Vector2D> actualPtsReverse = circle.intersections(line.reverse());
453
454 final Vector2D actualFirstForward = circle.firstIntersection(line);
455 final Vector2D actualFirstReverse = circle.firstIntersection(line.reverse());
456
457
458 final int len = expectedPts.length;
459
460
461 Assertions.assertEquals(len, actualPtsForward.size());
462 Assertions.assertEquals(len, actualPtsReverse.size());
463
464 for (int i = 0; i < len; ++i) {
465 EuclideanTestUtils.assertCoordinatesEqual(expectedPts[i], actualPtsForward.get(i), TEST_EPS);
466 Assertions.assertEquals(circle.getRadius(), circle.getCenter().distance(actualPtsForward.get(i)), TEST_EPS);
467
468 EuclideanTestUtils.assertCoordinatesEqual(expectedPts[len - i - 1], actualPtsReverse.get(i), TEST_EPS);
469 Assertions.assertEquals(circle.getRadius(), circle.getCenter().distance(actualPtsReverse.get(i)), TEST_EPS);
470 }
471
472
473 if (len > 0) {
474 Assertions.assertNotNull(actualFirstForward);
475 Assertions.assertNotNull(actualFirstReverse);
476
477 EuclideanTestUtils.assertCoordinatesEqual(expectedPts[0], actualFirstForward, TEST_EPS);
478 EuclideanTestUtils.assertCoordinatesEqual(expectedPts[len - 1], actualFirstReverse, TEST_EPS);
479 } else {
480 Assertions.assertNull(actualFirstForward);
481 Assertions.assertNull(actualFirstReverse);
482 }
483 }
484
485 private static void checkLinecast(final Circle c, final LineConvexSubset segment, final Vector2D... expectedPts) {
486
487 final List<LinecastPoint2D> results = c.linecast(segment);
488 Assertions.assertEquals(expectedPts.length, results.size());
489
490 LinecastPoint2D actual;
491 Vector2D expected;
492 for (int i = 0; i < expectedPts.length; ++i) {
493 expected = expectedPts[i];
494 actual = results.get(i);
495
496 EuclideanTestUtils.assertCoordinatesEqual(expected, actual.getPoint(), TEST_EPS);
497 EuclideanTestUtils.assertCoordinatesEqual(c.getCenter().directionTo(expected), actual.getNormal(), TEST_EPS);
498 Assertions.assertSame(segment.getLine(), actual.getLine());
499 }
500
501
502 final LinecastPoint2D firstResult = c.linecastFirst(segment);
503 if (expectedPts.length > 0) {
504 Assertions.assertEquals(results.get(0), firstResult);
505 } else {
506 Assertions.assertNull(firstResult);
507 }
508 }
509
510
511
512
513 private static void checkBasicApproximationProperties(final Circle c, final RegionBSPTree2D tree) {
514 Assertions.assertFalse(tree.isFull());
515 Assertions.assertFalse(tree.isEmpty());
516
517
518 final List<LinePath> paths = tree.getBoundaryPaths();
519 Assertions.assertEquals(1, paths.size());
520
521 final LinePath path = paths.get(0);
522 Assertions.assertTrue(path.isFinite());
523
524 for (final Vector2D vertex : path.getVertexSequence()) {
525 Assertions.assertTrue(c.contains(vertex), "Expected vertex to be contained in circle: " + vertex);
526 }
527
528
529 EuclideanTestUtils.assertRegionLocation(c, RegionLocation.INSIDE, tree.getCentroid());
530
531
532 Assertions.assertTrue(tree.getSize() < c.getSize(), "Expected approximation area to be less than circle");
533 }
534
535 private static void assertFiniteSegment(final LineConvexSubset segment, final Vector2D start, final Vector2D end) {
536 Assertions.assertFalse(segment.isInfinite());
537 Assertions.assertTrue(segment.isFinite());
538
539 EuclideanTestUtils.assertCoordinatesEqual(start, segment.getStartPoint(), TEST_EPS);
540 EuclideanTestUtils.assertCoordinatesEqual(end, segment.getEndPoint(), TEST_EPS);
541 }
542 }