1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.geometry.euclidean.threed;
18
19 import java.util.ArrayList;
20 import java.util.Arrays;
21 import java.util.Collection;
22 import java.util.Collections;
23 import java.util.List;
24 import java.util.regex.Pattern;
25
26 import org.apache.commons.geometry.core.GeometryTestUtils;
27 import org.apache.commons.geometry.core.RegionLocation;
28 import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
29 import org.apache.commons.geometry.euclidean.twod.ConvexArea;
30 import org.apache.commons.geometry.euclidean.twod.Line;
31 import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
32 import org.apache.commons.geometry.euclidean.twod.Lines;
33 import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
34 import org.apache.commons.geometry.euclidean.twod.Vector2D;
35 import org.apache.commons.geometry.euclidean.twod.path.LinePath;
36 import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
37 import org.apache.commons.numbers.angle.Angle;
38 import org.apache.commons.numbers.core.Precision;
39 import org.junit.jupiter.api.Assertions;
40 import org.junit.jupiter.api.Test;
41
42 class PlanesTest {
43
44 private static final double TEST_EPS = 1e-10;
45
46 private static final Precision.DoubleEquivalence TEST_PRECISION =
47 Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
48
49 @Test
50 void testSubsetFromConvexArea() {
51
52 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
53 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
54 final ConvexArea area = ConvexArea.convexPolygonFromVertices(Arrays.asList(
55 Vector2D.of(1, 0),
56 Vector2D.of(3, 0),
57 Vector2D.of(3, 1),
58 Vector2D.of(1, 1)
59 ), TEST_PRECISION);
60
61
62 final PlaneConvexSubset sp = Planes.subsetFromConvexArea(plane, area);
63
64
65 Assertions.assertFalse(sp.isFull());
66 Assertions.assertFalse(sp.isEmpty());
67 Assertions.assertTrue(sp.isFinite());
68
69 Assertions.assertEquals(2, sp.getSize(), TEST_EPS);
70
71 Assertions.assertSame(plane, sp.getPlane());
72 Assertions.assertSame(plane, sp.getHyperplane());
73 assertConvexAreasEqual(area, sp.getEmbedded().getSubspaceRegion());
74 }
75
76 @Test
77 void testConvexPolygonFromVertices() {
78
79 final Vector3D p0 = Vector3D.of(1, 0, 0);
80 final Vector3D p1 = Vector3D.of(1, 1, 0);
81 final Vector3D p2 = Vector3D.of(1, 1, 2);
82
83
84 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(p0, p1, p2), TEST_PRECISION);
85
86
87 Assertions.assertTrue(sp instanceof Triangle3D);
88
89 Assertions.assertFalse(sp.isFull());
90 Assertions.assertFalse(sp.isEmpty());
91 Assertions.assertTrue(sp.isFinite());
92
93 Assertions.assertEquals(3, sp.getVertices().size());
94 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p0, p1, p2), sp.getVertices(), TEST_PRECISION);
95
96 Assertions.assertEquals(1, sp.getSize(), TEST_EPS);
97
98 checkPlane(sp.getPlane(), Vector3D.of(1, 0, 0), Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_Z);
99
100 checkPoints(sp, RegionLocation.OUTSIDE,
101 Vector3D.of(0, 1, 1), Vector3D.of(0, 1, 0), Vector3D.of(0, 1, -1),
102 Vector3D.of(0, 0, 1), Vector3D.of(0, 0, 0), Vector3D.of(0, 0, -1),
103 Vector3D.of(0, -1, 1), Vector3D.of(0, -1, 0), Vector3D.of(0, -1, -1));
104
105 checkPoints(sp, RegionLocation.OUTSIDE,
106 Vector3D.of(1, 1, -1),
107 Vector3D.of(1, 0, 1), Vector3D.of(1, 0, -1),
108 Vector3D.of(1, -1, 1), Vector3D.of(1, -1, 0), Vector3D.of(1, -1, -1));
109
110 checkPoints(sp, RegionLocation.BOUNDARY,
111 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, 0),
112 Vector3D.of(1, 0, 0));
113
114 checkPoints(sp, RegionLocation.INSIDE, Vector3D.of(1, 0.5, 0.5));
115
116 checkPoints(sp, RegionLocation.OUTSIDE,
117 Vector3D.of(2, 1, 1), Vector3D.of(2, 1, 0), Vector3D.of(2, 1, -1),
118 Vector3D.of(2, 0, 1), Vector3D.of(2, 0, 0), Vector3D.of(2, 0, -1),
119 Vector3D.of(2, -1, 1), Vector3D.of(2, -1, 0), Vector3D.of(2, -1, -1));
120 }
121
122 @Test
123 void testConvexPolygonFromVertices_duplicatePoints() {
124
125 final Vector3D p0 = Vector3D.of(1, 0, 0);
126 final Vector3D p1 = Vector3D.of(1, 1, 0);
127 final Vector3D p2 = Vector3D.of(1, 1, 2);
128 final Vector3D p3 = Vector3D.of(1, 0, 2);
129
130
131 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
132 p0,
133 Vector3D.of(1, 1e-15, 0),
134 p1,
135 p2,
136 p3,
137 Vector3D.of(1, 1e-15, 2),
138 Vector3D.of(1, 0, 1e-15)
139 ), TEST_PRECISION);
140
141
142 Assertions.assertTrue(sp instanceof VertexListConvexPolygon3D);
143
144 Assertions.assertFalse(sp.isFull());
145 Assertions.assertFalse(sp.isEmpty());
146 Assertions.assertTrue(sp.isFinite());
147
148 Assertions.assertEquals(4, sp.getVertices().size());
149 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p0, p1, p2, p3), sp.getVertices(), TEST_PRECISION);
150
151 Assertions.assertEquals(2, sp.getSize(), TEST_EPS);
152
153 checkPlane(sp.getPlane(), Vector3D.of(1, 0, 0), Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_Z);
154
155 checkPoints(sp, RegionLocation.OUTSIDE,
156 Vector3D.of(0, 1, 1), Vector3D.of(0, 1, 0), Vector3D.of(0, 1, -1),
157 Vector3D.of(0, 0, 1), Vector3D.of(0, 0, 0), Vector3D.of(0, 0, -1),
158 Vector3D.of(0, -1, 1), Vector3D.of(0, -1, 0), Vector3D.of(0, -1, -1));
159
160 checkPoints(sp, RegionLocation.OUTSIDE,
161 Vector3D.of(1, 1, -1),
162 Vector3D.of(1, -1, 1), Vector3D.of(1, 0, -1),
163 Vector3D.of(1, -1, 0), Vector3D.of(1, -1, -1));
164
165 checkPoints(sp, RegionLocation.BOUNDARY,
166 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, 0),
167 Vector3D.of(1, 0, 0), Vector3D.of(1, 0, 2));
168
169 checkPoints(sp, RegionLocation.INSIDE, Vector3D.of(1, 0.5, 1));
170
171 checkPoints(sp, RegionLocation.OUTSIDE,
172 Vector3D.of(2, 1, 1), Vector3D.of(2, 1, 0), Vector3D.of(2, 1, -1),
173 Vector3D.of(2, 0, 1), Vector3D.of(2, 0, 0), Vector3D.of(2, 0, -1),
174 Vector3D.of(2, -1, 1), Vector3D.of(2, -1, 0), Vector3D.of(2, -1, -1));
175 }
176
177 @Test
178 void testConvexPolygonFromVertices_nonPlanar() {
179
180 final Pattern nonPlanarPattern = Pattern.compile("Points do not define a plane.*");
181
182
183 GeometryTestUtils.assertThrowsWithMessage(() -> {
184 Planes.convexPolygonFromVertices(Collections.emptyList(), TEST_PRECISION);
185 }, IllegalArgumentException.class, nonPlanarPattern);
186
187 GeometryTestUtils.assertThrowsWithMessage(() -> {
188 Planes.convexPolygonFromVertices(Collections.singletonList(Vector3D.ZERO), TEST_PRECISION);
189 }, IllegalArgumentException.class, nonPlanarPattern);
190
191 GeometryTestUtils.assertThrowsWithMessage(() -> {
192 Planes.convexPolygonFromVertices(Arrays.asList(Vector3D.ZERO, Vector3D.of(1, 0, 0)), TEST_PRECISION);
193 }, IllegalArgumentException.class, nonPlanarPattern);
194
195 GeometryTestUtils.assertThrowsWithMessage(() -> {
196 Planes.convexPolygonFromVertices(
197 Arrays.asList(Vector3D.ZERO, Vector3D.of(1, 0, 0), Vector3D.of(1, 1e-15, 0)), TEST_PRECISION);
198 }, IllegalArgumentException.class, nonPlanarPattern);
199
200 GeometryTestUtils.assertThrowsWithMessage(() -> {
201 Planes.convexPolygonFromVertices(Arrays.asList(
202 Vector3D.ZERO,
203 Vector3D.of(1, 0, 1),
204 Vector3D.of(1, 1, 0),
205 Vector3D.of(0, 1, 1)
206 ), TEST_PRECISION);
207 }, IllegalArgumentException.class, nonPlanarPattern);
208 }
209
210 @Test
211 void testConvexPolygonFromVertices_nonConvex() {
212
213 final Pattern nonConvexPattern = Pattern.compile("Points do not define a convex region.*");
214
215
216 GeometryTestUtils.assertThrowsWithMessage(() -> {
217 Planes.convexPolygonFromVertices(Arrays.asList(
218 Vector3D.ZERO,
219 Vector3D.of(2, 0, 0),
220 Vector3D.of(2, 2, 0),
221 Vector3D.of(1, 1, 0),
222 Vector3D.of(1.5, 1, 0)
223 ), TEST_PRECISION);
224 }, IllegalArgumentException.class, nonConvexPattern);
225 }
226
227 @Test
228 void testTriangleFromVertices() {
229
230 final Triangle3D tri = Planes.triangleFromVertices(
231 Vector3D.of(1, 1, 1),
232 Vector3D.of(2, 1, 1),
233 Vector3D.of(2, 1, 2), TEST_PRECISION);
234
235
236 Assertions.assertEquals(0.5, tri.getSize(), TEST_EPS);
237 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(5.0 / 3.0, 1, 4.0 / 3.0),
238 tri.getCentroid(), TEST_EPS);
239 }
240
241 @Test
242 void testTriangleFromVertices_degenerateTriangles() {
243
244 final Pattern msg = Pattern.compile("^Points do not define a plane.*");
245
246
247 GeometryTestUtils.assertThrowsWithMessage(() -> {
248 Planes.triangleFromVertices(
249 Vector3D.ZERO,
250 Vector3D.of(1e-11, 0, 0),
251 Vector3D.of(0, 1e-11, 0),
252 TEST_PRECISION);
253 }, IllegalArgumentException.class, msg);
254
255 GeometryTestUtils.assertThrowsWithMessage(() -> {
256 Planes.triangleFromVertices(
257 Vector3D.ZERO,
258 Vector3D.of(1, 0, 0),
259 Vector3D.of(2, 0, 0),
260 TEST_PRECISION);
261 }, IllegalArgumentException.class, msg);
262 }
263
264 @Test
265 void testIndexedTriangles_singleTriangle_noFaces() {
266
267 final List<Triangle3D> tris = Planes.indexedTriangles(new Vector3D[0], new int[0][], TEST_PRECISION);
268
269
270 Assertions.assertEquals(0, tris.size());
271 }
272
273 @Test
274 void testIndexedTriangles_singleTriangle() {
275
276 final Vector3D[] vertices = {
277 Vector3D.ZERO,
278 Vector3D.of(1, 0, 0),
279 Vector3D.of(1, 1, 0)
280 };
281
282 final int[][] faceIndices = {
283 {0, 2, 1}
284 };
285
286
287 final List<Triangle3D> tris = Planes.indexedTriangles(Arrays.asList(vertices), faceIndices, TEST_PRECISION);
288
289
290 Assertions.assertEquals(1, tris.size());
291
292 final Triangle3D a = tris.get(0);
293 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_Z, a.getPlane().getNormal(), TEST_EPS);
294 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, a.getPoint1(), TEST_EPS);
295 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 0), a.getPoint2(), TEST_EPS);
296 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0), a.getPoint3(), TEST_EPS);
297 }
298
299 @Test
300 void testIndexedTriangles_multipleTriangles() {
301
302
303 final Vector3D[] vertices = {
304 Vector3D.ZERO,
305 Vector3D.of(1, 0, 0),
306 Vector3D.of(1, 1, 0),
307 Vector3D.of(0, 1, 0),
308 Vector3D.of(0.5, 0.5, 4)
309 };
310
311 final int[][] faceIndices = {
312 {0, 2, 1},
313 {0, 3, 2},
314 {0, 1, 4},
315 {1, 2, 4},
316 {2, 3, 4},
317 {3, 0, 4}
318 };
319
320
321 final List<Triangle3D> tris = Planes.indexedTriangles(vertices, faceIndices, TEST_PRECISION);
322
323
324 Assertions.assertEquals(6, tris.size());
325
326 final RegionBSPTree3D tree = RegionBSPTree3D.from(tris);
327 Assertions.assertEquals(4 / 3.0, tree.getSize(), TEST_EPS);
328
329 final Bounds3D bounds = tree.getBounds();
330 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, bounds.getMin(), TEST_EPS);
331 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 4), bounds.getMax(), TEST_EPS);
332 }
333
334 @Test
335 void testIndexedTriangles_invalidArgs() {
336
337 final Vector3D[] vertices = {
338 Vector3D.ZERO,
339 Vector3D.of(1, 0, 0),
340 Vector3D.of(1, 1, 0),
341 Vector3D.of(2, 0, 0)
342 };
343
344
345 GeometryTestUtils.assertThrowsWithMessage(() -> {
346 Planes.indexedTriangles(vertices, new int[][] {
347 {0}
348 }, TEST_PRECISION);
349 }, IllegalArgumentException.class,
350 "Invalid number of vertex indices for face at index 0: expected 3 but found 1");
351
352 GeometryTestUtils.assertThrowsWithMessage(() -> {
353 Planes.indexedTriangles(vertices, new int[][] {
354 {0, 1, 2, 0}
355 }, TEST_PRECISION);
356 }, IllegalArgumentException.class,
357 "Invalid number of vertex indices for face at index 0: expected 3 but found 4");
358
359 GeometryTestUtils.assertThrowsWithMessage(() -> {
360 Planes.indexedTriangles(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
361 {0, 1, 3}
362 }, TEST_PRECISION);
363 }, IllegalArgumentException.class, Pattern.compile("^Points do not define a plane: .*"));
364
365 Assertions.assertThrows(IndexOutOfBoundsException.class, () -> Planes.indexedTriangles(vertices, new int[][] {
366 {0, 1, 10}
367 }, TEST_PRECISION));
368 Assertions.assertThrows(IndexOutOfBoundsException.class, () -> Planes.indexedTriangles(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
369 {0, 1, 10}
370 }, TEST_PRECISION));
371 }
372
373 @Test
374 void testIndexedConvexPolygons_singleTriangle_noFaces() {
375
376 final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(new Vector3D[0], new int[0][], TEST_PRECISION);
377
378
379 Assertions.assertEquals(0, polys.size());
380 }
381
382 @Test
383 void testIndexedConvexPolygons_singleSquare() {
384
385 final Vector3D[] vertices = {
386 Vector3D.ZERO,
387 Vector3D.of(1, 0, 0),
388 Vector3D.of(1, 1, 0),
389 Vector3D.of(0, 1, 0)
390 };
391
392 final int[][] faceIndices = {
393 {0, 3, 2, 1}
394 };
395
396
397 final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(Arrays.asList(vertices), faceIndices,
398 TEST_PRECISION);
399
400
401 Assertions.assertEquals(1, polys.size());
402
403 final ConvexPolygon3D a = polys.get(0);
404 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(
405 Vector3D.ZERO,
406 Vector3D.of(0, 1, 0),
407 Vector3D.of(1, 1, 0),
408 Vector3D.of(1, 0, 0)
409 ), a.getVertices(), TEST_PRECISION);
410 }
411
412 @Test
413 void testIndexedConvexPolygons_mixedPolygons() {
414
415
416 final Vector3D[] vertices = {
417 Vector3D.ZERO,
418 Vector3D.of(1, 0, 0),
419 Vector3D.of(1, 1, 0),
420 Vector3D.of(0, 1, 0),
421 Vector3D.of(0.5, 0.5, 4)
422 };
423
424 final int[][] faceIndices = {
425 {0, 3, 2, 1},
426 {0, 1, 4},
427 {1, 2, 4},
428 {2, 3, 4},
429 {3, 0, 4}
430 };
431
432
433 final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(vertices, faceIndices, TEST_PRECISION);
434
435
436 Assertions.assertEquals(5, polys.size());
437
438 final RegionBSPTree3D tree = RegionBSPTree3D.from(polys);
439 Assertions.assertEquals(4 / 3.0, tree.getSize(), TEST_EPS);
440
441 final Bounds3D bounds = tree.getBounds();
442 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, bounds.getMin(), TEST_EPS);
443 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 4), bounds.getMax(), TEST_EPS);
444 }
445
446 @Test
447 void testIndexedConvexPolygons_cube() {
448
449 final Vector3D[] vertices = {
450 Vector3D.of(-0.5, -0.5, -0.5),
451 Vector3D.of(0.5, -0.5, -0.5),
452 Vector3D.of(0.5, 0.5, -0.5),
453 Vector3D.of(-0.5, 0.5, -0.5),
454
455 Vector3D.of(-0.5, -0.5, 0.5),
456 Vector3D.of(0.5, -0.5, 0.5),
457 Vector3D.of(0.5, 0.5, 0.5),
458 Vector3D.of(-0.5, 0.5, 0.5)
459 };
460
461 final int[][] faceIndices = {
462 {0, 4, 7, 3},
463 {1, 2, 6, 5},
464 {0, 1, 5, 4},
465 {3, 7, 6, 2},
466 {0, 3, 2, 1},
467 {4, 5, 6, 7}
468 };
469
470
471 final List<ConvexPolygon3D> polys = Planes.indexedConvexPolygons(Arrays.asList(vertices), faceIndices,
472 TEST_PRECISION);
473
474
475 Assertions.assertEquals(6, polys.size());
476
477 final RegionBSPTree3D tree = RegionBSPTree3D.from(polys);
478 Assertions.assertEquals(1.0, tree.getSize(), TEST_EPS);
479
480 final Bounds3D bounds = tree.getBounds();
481 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-0.5, -0.5, -0.5), bounds.getMin(), TEST_EPS);
482 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), bounds.getMax(), TEST_EPS);
483 }
484
485 @Test
486 void testIndexedConvexPolygons_invalidArgs() {
487
488 final Vector3D[] vertices = {
489 Vector3D.ZERO,
490 Vector3D.of(1, 0, 0),
491 Vector3D.of(1, 1, 0),
492 Vector3D.of(2, 0, 0)
493 };
494
495
496 GeometryTestUtils.assertThrowsWithMessage(() -> {
497 Planes.indexedConvexPolygons(vertices, new int[][] {
498 {0}
499 }, TEST_PRECISION);
500 }, IllegalArgumentException.class,
501 "Invalid number of vertex indices for face at index 0: required at least 3 but found 1");
502
503 GeometryTestUtils.assertThrowsWithMessage(() -> {
504 Planes.indexedConvexPolygons(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
505 {0, 1, 3}
506 }, TEST_PRECISION);
507 }, IllegalArgumentException.class, Pattern.compile("^Points do not define a plane: .*"));
508
509 Assertions.assertThrows(IndexOutOfBoundsException.class, () -> Planes.indexedConvexPolygons(vertices, new int[][] {
510 {0, 1, 10}
511 }, TEST_PRECISION));
512 Assertions.assertThrows(IndexOutOfBoundsException.class, () -> Planes.indexedConvexPolygons(new ArrayList<>(Arrays.asList(vertices)), new int[][] {
513 {0, 1, 10}
514 }, TEST_PRECISION));
515 }
516
517 @Test
518 void testConvexPolygonToTriangleFan_threeVertices() {
519
520 final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
521 final Vector3D p1 = Vector3D.ZERO;
522 final Vector3D p2 = Vector3D.of(1, 0, 0);
523 final Vector3D p3 = Vector3D.of(0, 1, 0);
524
525
526 final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3));
527
528
529 Assertions.assertEquals(1, tris.size());
530
531 final Triangle3D a = tris.get(0);
532 Assertions.assertSame(plane, a.getPlane());
533 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), a.getVertices(), TEST_PRECISION);
534 }
535
536 @Test
537 void testConvexPolygonToTriangleFan_fourVertices() {
538
539 final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
540 final Vector3D p1 = Vector3D.ZERO;
541 final Vector3D p2 = Vector3D.of(1, 0, 0);
542 final Vector3D p3 = Vector3D.of(1, 1, 0);
543 final Vector3D p4 = Vector3D.of(0, 1, 0);
544
545
546 final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3, p4));
547
548
549 Assertions.assertEquals(2, tris.size());
550
551 final Triangle3D a = tris.get(0);
552 Assertions.assertSame(plane, a.getPlane());
553 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p2, p3), a.getVertices(), TEST_PRECISION);
554
555 final Triangle3D b = tris.get(1);
556 Assertions.assertSame(plane, b.getPlane());
557 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p1, p3, p4), b.getVertices(), TEST_PRECISION);
558 }
559
560 @Test
561 void testConvexPolygonToTriangleFan_sixVertices() {
562
563 final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
564 final Vector3D p1 = Vector3D.ZERO;
565 final Vector3D p2 = Vector3D.of(1, -1, 0);
566 final Vector3D p3 = Vector3D.of(1.5, -1, 0);
567 final Vector3D p4 = Vector3D.of(5, 0, 0);
568 final Vector3D p5 = Vector3D.of(3, 1, 0);
569 final Vector3D p6 = Vector3D.of(0.5, 1, 0);
570
571
572 final List<Triangle3D> tris = Planes.convexPolygonToTriangleFan(plane, Arrays.asList(p1, p2, p3, p4, p5, p6));
573
574
575 Assertions.assertEquals(4, tris.size());
576
577 final Triangle3D a = tris.get(0);
578 Assertions.assertSame(plane, a.getPlane());
579 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p4, p5), a.getVertices(), TEST_PRECISION);
580
581 final Triangle3D b = tris.get(1);
582 Assertions.assertSame(plane, b.getPlane());
583 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p5, p6), b.getVertices(), TEST_PRECISION);
584
585 final Triangle3D c = tris.get(2);
586 Assertions.assertSame(plane, c.getPlane());
587 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p6, p1), c.getVertices(), TEST_PRECISION);
588
589 final Triangle3D d = tris.get(3);
590 Assertions.assertSame(plane, d.getPlane());
591 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p3, p1, p2), d.getVertices(), TEST_PRECISION);
592 }
593
594 @Test
595 void testConvexPolygonToTriangleFan_notEnoughVertices() {
596
597 final String baseMsg = "Cannot create triangle fan: 3 or more vertices are required but found only ";
598 final Plane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
599
600
601 GeometryTestUtils.assertThrowsWithMessage(() -> {
602 Planes.convexPolygonToTriangleFan(plane, Collections.emptyList());
603 }, IllegalArgumentException.class, baseMsg + "0");
604
605 GeometryTestUtils.assertThrowsWithMessage(() -> {
606 Planes.convexPolygonToTriangleFan(plane, Collections.singletonList(Vector3D.ZERO));
607 }, IllegalArgumentException.class, baseMsg + "1");
608
609 GeometryTestUtils.assertThrowsWithMessage(() -> {
610 Planes.convexPolygonToTriangleFan(plane, Arrays.asList(Vector3D.ZERO, Vector3D.of(1, 0, 0)));
611 }, IllegalArgumentException.class, baseMsg + "2");
612 }
613
614 @Test
615 void testExtrudeVertexLoop_convex() {
616
617 final List<Vector2D> vertices = Arrays.asList(
618 Vector2D.of(2, 1),
619 Vector2D.of(3, 1),
620 Vector2D.of(2, 3)
621 );
622
623 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
624 Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_X, TEST_PRECISION);
625 final Vector3D extrusionVector = Vector3D.of(1, 0, 1);
626
627
628 final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
629
630
631 Assertions.assertEquals(5, boundaries.size());
632
633 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
634
635 Assertions.assertEquals(1, tree.getSize(), TEST_EPS);
636 EuclideanTestUtils.assertCoordinatesEqual(
637 Vector3D.of(-5.0 / 3.0, 7.0 / 3.0, 1).add(extrusionVector.multiply(0.5)), tree.getCentroid(), TEST_EPS);
638
639 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
640 Vector3D.of(-1.5, 2.5, 1.25), tree.getCentroid());
641 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
642 Vector3D.of(-2, 2, 1), Vector3D.of(-1, 2, 1), Vector3D.of(-1, 3, 1),
643 Vector3D.of(-1, 2, 2), Vector3D.of(0, 2, 2), Vector3D.of(0, 3, 2));
644
645 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
646 Vector3D.of(-1.5, 2.5, 0.9), Vector3D.of(-1.5, 2.5, 2.1));
647 }
648
649 @Test
650 void testExtrudeVertexLoop_nonConvex() {
651
652 final List<Vector2D> vertices = Arrays.asList(
653 Vector2D.of(1, 2),
654 Vector2D.of(1, -2),
655 Vector2D.of(4, -2),
656 Vector2D.of(4, -1),
657 Vector2D.of(2, -1),
658 Vector2D.of(2, 1),
659 Vector2D.of(4, 1),
660 Vector2D.of(4, 2),
661 Vector2D.of(1, 2)
662 );
663
664 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
665 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
666 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
667
668
669 final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
670
671
672 Assertions.assertEquals(14, boundaries.size());
673
674 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
675
676 Assertions.assertEquals(16, tree.getSize(), TEST_EPS);
677 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2.25, 0, 0), tree.getCentroid(), TEST_EPS);
678
679 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
680 Vector3D.of(1.5, 0, 0), Vector3D.of(3, 1.5, 0), Vector3D.of(3, -1.5, 0));
681 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
682 Vector3D.of(1.5, 0, -1), Vector3D.of(3, 1.5, -1), Vector3D.of(3, -1.5, -1),
683 Vector3D.of(1.5, 0, 1), Vector3D.of(3, 1.5, 1), Vector3D.of(3, -1.5, 1),
684 Vector3D.of(1, 0, 0), Vector3D.of(2.5, -2, 0), Vector3D.of(4, -1.5, 0),
685 Vector3D.of(3, -1, 0), Vector3D.of(2, 0, 0), Vector3D.of(3, 1, 0),
686 Vector3D.of(4, 1.5, 0), Vector3D.of(2.5, 2, 0));
687
688 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
689 tree.getCentroid(), Vector3D.ZERO, Vector3D.of(5, 0, 0));
690 }
691
692 @Test
693 void testExtrudeVertexLoop_noVertices() {
694
695 final List<Vector2D> vertices = new ArrayList<>();
696
697 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
698 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
699 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
700
701
702 final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
703
704
705 Assertions.assertEquals(0, boundaries.size());
706 }
707
708 @Test
709 void testExtrudeVertexLoop_twoVertices_producesInfiniteRegion() {
710
711 final List<Vector2D> vertices = Arrays.asList(Vector2D.ZERO, Vector2D.of(1, 1));
712
713 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
714 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
715 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
716
717
718 final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
719
720
721 Assertions.assertEquals(3, boundaries.size());
722
723 final PlaneConvexSubset bottom = boundaries.get(0);
724 Assertions.assertTrue(bottom.isInfinite());
725 Assertions.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
726 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
727
728 final PlaneConvexSubset top = boundaries.get(1);
729 Assertions.assertTrue(top.isInfinite());
730 Assertions.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
731 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
732
733 final PlaneConvexSubset side = boundaries.get(2);
734 Assertions.assertTrue(side.isInfinite());
735 Assertions.assertTrue(side.getPlane().contains(Vector3D.ZERO));
736 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
737 side.getPlane().getNormal(), TEST_EPS);
738
739 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
740 Assertions.assertFalse(tree.isFull());
741 Assertions.assertTrue(tree.isInfinite());
742
743 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
744 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
745
746 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
747 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
748
749 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
750 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
751 }
752
753 @Test
754 void testExtrudeVertexLoop_invalidVertexList() {
755
756 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
757 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
758 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
759
760
761 Assertions.assertThrows(IllegalStateException.class, () -> Planes.extrudeVertexLoop(Collections.singletonList(Vector2D.ZERO), plane, extrusionVector, TEST_PRECISION));
762 Assertions.assertThrows(IllegalStateException.class, () -> Planes.extrudeVertexLoop(Arrays.asList(Vector2D.ZERO, Vector2D.of(0, 1e-16)), plane,
763 extrusionVector, TEST_PRECISION));
764 }
765
766 @Test
767 void testExtrudeVertexLoop_regionsConsistentBetweenExtrusionPlanes() {
768
769 final List<Vector2D> vertices = Arrays.asList(
770 Vector2D.of(1, 2),
771 Vector2D.of(1, -2),
772 Vector2D.of(4, -2),
773 Vector2D.of(4, -1),
774 Vector2D.of(2, -1),
775 Vector2D.of(2, 1),
776 Vector2D.of(4, 1),
777 Vector2D.of(4, 2),
778 Vector2D.of(1, 2)
779 );
780
781 final RegionBSPTree2D subspaceTree = LinePath.fromVertexLoop(vertices, TEST_PRECISION).toTree();
782
783 final double subspaceSize = subspaceTree.getSize();
784 final Vector2D subspaceCentroid = subspaceTree.getCentroid();
785
786 final double extrusionLength = 2;
787 final double expectedSize = subspaceSize * extrusionLength;
788
789 final Vector3D planePt = Vector3D.of(-1, 2, -3);
790
791 EuclideanTestUtils.permuteSkipZero(-2, 2, 1, (x, y, z) -> {
792 final Vector3D normal = Vector3D.of(x, y, z);
793 final EmbeddingPlane plane = Planes.fromPointAndNormal(planePt, normal, TEST_PRECISION).getEmbedding();
794
795 final Vector3D baseCentroid = plane.toSpace(subspaceCentroid);
796
797 final Vector3D plusExtrusionVector = normal.withNorm(extrusionLength);
798 final Vector3D minusExtrusionVector = plusExtrusionVector.negate();
799
800
801 final RegionBSPTree3D extrudePlus = RegionBSPTree3D.from(
802 Planes.extrudeVertexLoop(vertices, plane, plusExtrusionVector, TEST_PRECISION));
803 final RegionBSPTree3D extrudeMinus = RegionBSPTree3D.from(
804 Planes.extrudeVertexLoop(vertices, plane, minusExtrusionVector, TEST_PRECISION));
805
806
807 Assertions.assertEquals(expectedSize, extrudePlus.getSize(), TEST_EPS);
808 EuclideanTestUtils.assertCoordinatesEqual(baseCentroid.add(plusExtrusionVector.multiply(0.5)),
809 extrudePlus.getCentroid(), TEST_EPS);
810
811 Assertions.assertEquals(expectedSize, extrudeMinus.getSize(), TEST_EPS);
812 EuclideanTestUtils.assertCoordinatesEqual(baseCentroid.add(minusExtrusionVector.multiply(0.5)),
813 extrudeMinus.getCentroid(), TEST_EPS);
814 });
815 }
816
817 @Test
818 void testExtrude_vertexLoop_clockwiseWinding() {
819
820 final List<Vector2D> vertices = Arrays.asList(
821 Vector2D.of(0, 1),
822 Vector2D.of(1, 0),
823 Vector2D.of(0, -1),
824 Vector2D.of(-1, 0));
825
826 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
827 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
828 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
829
830
831 final List<PlaneConvexSubset> boundaries = Planes.extrudeVertexLoop(vertices, plane, extrusionVector, TEST_PRECISION);
832
833
834 final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
835
836 Assertions.assertTrue(resultTree.isInfinite());
837 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
838 Vector3D.of(1, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0));
839 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE, Vector3D.ZERO);
840 }
841
842 @Test
843 void testExtrude_linePath_emptyPath() {
844
845 final LinePath path = LinePath.empty();
846
847 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
848 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
849 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
850
851
852 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
853
854
855 Assertions.assertEquals(0, boundaries.size());
856 }
857
858 @Test
859 void testExtrude_linePath_singleSegment_producesInfiniteRegion_extrudingOnMinus() {
860
861 final LinePath path = LinePath.builder(TEST_PRECISION)
862 .append(Vector2D.ZERO)
863 .append(Vector2D.of(1, 1))
864 .build();
865
866 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
867 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
868 final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
869
870
871 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
872
873
874 Assertions.assertEquals(3, boundaries.size());
875
876 final PlaneConvexSubset top = boundaries.get(0);
877 Assertions.assertTrue(top.isInfinite());
878 Assertions.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
879 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
880
881 final PlaneConvexSubset bottom = boundaries.get(1);
882 Assertions.assertTrue(bottom.isInfinite());
883 Assertions.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
884 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
885
886 final PlaneConvexSubset side = boundaries.get(2);
887 Assertions.assertTrue(side.isInfinite());
888 Assertions.assertTrue(side.getPlane().contains(Vector3D.ZERO));
889 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
890 side.getPlane().getNormal(), TEST_EPS);
891
892 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
893 Assertions.assertFalse(tree.isFull());
894 Assertions.assertTrue(tree.isInfinite());
895
896 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
897 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
898
899 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
900 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
901
902 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
903 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
904 }
905
906 @Test
907 void testExtrude_linePath_singleSegment_producesInfiniteRegion_extrudingOnPlus() {
908
909 final LinePath path = LinePath.builder(TEST_PRECISION)
910 .append(Vector2D.ZERO)
911 .append(Vector2D.of(1, 1))
912 .build();
913
914 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
915 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
916 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
917
918
919 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
920
921
922 Assertions.assertEquals(3, boundaries.size());
923
924 final PlaneConvexSubset bottom = boundaries.get(0);
925 Assertions.assertTrue(bottom.isInfinite());
926 Assertions.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
927 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
928
929 final PlaneConvexSubset top = boundaries.get(1);
930 Assertions.assertTrue(top.isInfinite());
931 Assertions.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
932 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
933
934 final PlaneConvexSubset side = boundaries.get(2);
935 Assertions.assertTrue(side.isInfinite());
936 Assertions.assertTrue(side.getPlane().contains(Vector3D.ZERO));
937 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
938 side.getPlane().getNormal(), TEST_EPS);
939
940 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
941 Assertions.assertFalse(tree.isFull());
942 Assertions.assertTrue(tree.isInfinite());
943
944 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
945 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
946
947 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
948 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
949
950 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
951 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
952 }
953
954 @Test
955 void testExtrude_linePath_singleSpan_producesInfiniteRegion() {
956
957 final LinePath path = LinePath.from(Lines.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).span());
958
959 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
960 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
961 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
962
963
964 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
965
966
967 Assertions.assertEquals(3, boundaries.size());
968
969 final PlaneConvexSubset bottom = boundaries.get(0);
970 Assertions.assertTrue(bottom.isInfinite());
971 Assertions.assertTrue(bottom.getPlane().contains(Vector3D.of(0, 0, -1)));
972 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), bottom.getPlane().getNormal(), TEST_EPS);
973
974 final PlaneConvexSubset top = boundaries.get(1);
975 Assertions.assertTrue(top.isInfinite());
976 Assertions.assertTrue(top.getPlane().contains(Vector3D.of(0, 0, 1)));
977 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), top.getPlane().getNormal(), TEST_EPS);
978
979 final PlaneConvexSubset side = boundaries.get(2);
980 Assertions.assertTrue(side.isInfinite());
981 Assertions.assertTrue(side.getPlane().contains(Vector3D.ZERO));
982 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 0).normalize(),
983 side.getPlane().getNormal(), TEST_EPS);
984
985 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
986 Assertions.assertFalse(tree.isFull());
987 Assertions.assertTrue(tree.isInfinite());
988
989 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
990 Vector3D.of(0, 1, 0), Vector3D.of(-1, 0, 0), Vector3D.of(-2, -1, 0));
991
992 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
993 Vector3D.of(1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(-1, -1, 0));
994
995 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
996 Vector3D.of(2, 1, 0), Vector3D.of(1, 0, 0), Vector3D.of(0, -1, 0));
997 }
998
999 @Test
1000 void testExtrude_linePath_intersectingInfiniteLines_extrudingOnPlus() {
1001
1002 final Vector2D intersectionPt = Vector2D.of(1, 0);
1003
1004 final LinePath path = LinePath.from(
1005 Lines.fromPointAndAngle(intersectionPt, 0, TEST_PRECISION).reverseRayTo(intersectionPt),
1006 Lines.fromPointAndAngle(intersectionPt, Angle.PI_OVER_TWO, TEST_PRECISION)
1007 .rayFrom(intersectionPt));
1008
1009 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
1010 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1011 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
1012
1013
1014 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
1015
1016
1017 Assertions.assertEquals(4, boundaries.size());
1018
1019 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
1020 Assertions.assertFalse(tree.isFull());
1021 Assertions.assertTrue(tree.isInfinite());
1022
1023 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
1024 Vector3D.of(0, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(0, 2, 0), Vector3D.of(-1, 2, 0));
1025
1026 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
1027 Vector3D.of(-1, 0, 0), Vector3D.of(0, 0, 0), Vector3D.of(1, 0, 0),
1028 Vector3D.of(1, 1, 0), Vector3D.of(1, 2, 0), Vector3D.of(-2, 2, 1),
1029 Vector3D.of(-2, 2, -1));
1030
1031 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
1032 Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0), Vector3D.of(3, 1, 0), Vector3D.of(3, -1, 0),
1033 Vector3D.of(-2, -2, -2), Vector3D.of(-2, -2, 2));
1034 }
1035
1036 @Test
1037 void testExtrude_linePath_intersectingInfiniteLines_extrudingOnMinus() {
1038
1039 final Vector2D intersectionPt = Vector2D.of(1, 0);
1040
1041 final LinePath path = LinePath.from(
1042 Lines.fromPointAndAngle(intersectionPt, 0, TEST_PRECISION).reverseRayTo(intersectionPt),
1043 Lines.fromPointAndAngle(intersectionPt, Angle.PI_OVER_TWO, TEST_PRECISION)
1044 .rayFrom(intersectionPt));
1045
1046 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
1047 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1048 final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
1049
1050
1051 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
1052
1053
1054 Assertions.assertEquals(4, boundaries.size());
1055
1056 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
1057 Assertions.assertFalse(tree.isFull());
1058 Assertions.assertTrue(tree.isInfinite());
1059
1060 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
1061 Vector3D.of(0, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(0, 2, 0), Vector3D.of(-1, 2, 0));
1062
1063 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
1064 Vector3D.of(-1, 0, 0), Vector3D.of(0, 0, 0), Vector3D.of(1, 0, 0),
1065 Vector3D.of(1, 1, 0), Vector3D.of(1, 2, 0), Vector3D.of(-2, 2, 1),
1066 Vector3D.of(-2, 2, -1));
1067
1068 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
1069 Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0), Vector3D.of(3, 1, 0), Vector3D.of(3, -1, 0),
1070 Vector3D.of(-2, -2, -2), Vector3D.of(-2, -2, 2));
1071 }
1072
1073 @Test
1074 void testExtrude_linePath_infiniteNonConvex() {
1075
1076 final LinePath path = LinePath.builder(TEST_PRECISION)
1077 .append(Vector2D.of(1, -5))
1078 .append(Vector2D.of(1, 1))
1079 .append(Vector2D.of(0, 0))
1080 .append(Vector2D.of(-1, 1))
1081 .append(Vector2D.of(-1, -5))
1082 .build();
1083
1084 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
1085 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1086 final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
1087
1088
1089 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
1090
1091
1092 Assertions.assertEquals(8, boundaries.size());
1093
1094 final RegionBSPTree3D tree = RegionBSPTree3D.from(boundaries);
1095 Assertions.assertFalse(tree.isFull());
1096 Assertions.assertTrue(tree.isInfinite());
1097
1098 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
1099 Vector3D.of(0, -1, 0), Vector3D.of(0, -100, 0));
1100
1101 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY,
1102 Vector3D.of(-1, 1, 0), Vector3D.of(0, 0, 0), Vector3D.of(1, 1, 0),
1103 Vector3D.of(-1, -100, 0), Vector3D.of(1, -100, 0),
1104 Vector3D.of(0, -100, 1), Vector3D.of(0, -100, -1));
1105
1106 EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
1107 Vector3D.of(-2, 0, 0), Vector3D.of(2, 0, 0), Vector3D.of(0, 0.5, 0),
1108 Vector3D.of(0, -100, -2), Vector3D.of(0, -100, 2));
1109 }
1110
1111 @Test
1112 void testExtrude_linePath_clockwiseWinding() {
1113
1114 final LinePath path = LinePath.builder(TEST_PRECISION)
1115 .append(Vector2D.of(0, 1))
1116 .append(Vector2D.of(1, 0))
1117 .append(Vector2D.of(0, -1))
1118 .append(Vector2D.of(-1, 0))
1119 .close();
1120
1121 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
1122 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1123 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
1124
1125
1126 final List<PlaneConvexSubset> boundaries = Planes.extrude(path, plane, extrusionVector, TEST_PRECISION);
1127
1128
1129 final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
1130
1131 Assertions.assertTrue(resultTree.isInfinite());
1132 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
1133 Vector3D.of(1, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0));
1134 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE, Vector3D.ZERO);
1135 }
1136
1137 @Test
1138 void testExtrude_region_empty() {
1139
1140 final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1141
1142 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
1143 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1144 final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
1145
1146
1147 final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
1148
1149
1150 Assertions.assertEquals(0, boundaries.size());
1151 }
1152
1153 @Test
1154 void testExtrude_region_full() {
1155
1156 final RegionBSPTree2D tree = RegionBSPTree2D.full();
1157
1158 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
1159 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1160 final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
1161
1162
1163 final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
1164
1165
1166 Assertions.assertEquals(2, boundaries.size());
1167
1168 Assertions.assertTrue(boundaries.get(0).isFull());
1169 Assertions.assertTrue(boundaries.get(1).isFull());
1170
1171 final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
1172
1173 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
1174 Vector3D.of(1, 1, 0), Vector3D.of(-1, 1, 0), Vector3D.of(-1, -1, 0), Vector3D.of(1, -1, 0));
1175
1176 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.BOUNDARY,
1177 Vector3D.of(1, 1, 1), Vector3D.of(-1, 1, 1), Vector3D.of(-1, -1, 1), Vector3D.of(1, -1, 1),
1178 Vector3D.of(1, 1, -1), Vector3D.of(-1, 1, -1), Vector3D.of(-1, -1, -1), Vector3D.of(1, -1, -1));
1179
1180 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE,
1181 Vector3D.of(1, 1, 2), Vector3D.of(-1, 1, 2), Vector3D.of(-1, -1, 2), Vector3D.of(1, -1, 2),
1182 Vector3D.of(1, 1, -2), Vector3D.of(-1, 1, -2), Vector3D.of(-1, -1, -2), Vector3D.of(1, -1, -2));
1183 }
1184
1185 @Test
1186 void testExtrude_region_disjointRegions() {
1187
1188 final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1189 tree.insert(Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
1190 tree.insert(Parallelogram.axisAligned(Vector2D.of(2, 2), Vector2D.of(3, 3), TEST_PRECISION));
1191
1192 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
1193 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1194 final Vector3D extrusionVector = Vector3D.of(0, 0, -2);
1195
1196
1197 final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
1198
1199
1200 Assertions.assertEquals(12, boundaries.size());
1201
1202 final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
1203
1204 Assertions.assertEquals(4, resultTree.getSize(), TEST_EPS);
1205 Assertions.assertEquals(20, resultTree.getBoundarySize(), TEST_EPS);
1206 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1.5, 1.5, 0), resultTree.getCentroid(), TEST_EPS);
1207
1208 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.INSIDE,
1209 Vector3D.of(0.5, 0.5, 0), Vector3D.of(2.5, 2.5, 0));
1210
1211 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.BOUNDARY,
1212 Vector3D.ZERO, Vector3D.of(1, 1, 0), Vector3D.of(2, 2, 0), Vector3D.of(3, 3, 0),
1213 Vector3D.of(0.5, 0.5, -1), Vector3D.of(0.5, 0.5, 1), Vector3D.of(2.5, 2.5, -1),
1214 Vector3D.of(2.5, 2.5, 1));
1215
1216 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE,
1217 Vector3D.of(-1, -1, 0), Vector3D.of(1.5, 1.5, 0), Vector3D.of(4, 4, 0),
1218 Vector3D.of(0.5, 0.5, -2), Vector3D.of(0.5, 0.5, 2), Vector3D.of(2.5, 2.5, -2),
1219 Vector3D.of(2.5, 2.5, 2));
1220 }
1221
1222 @Test
1223 void testExtrude_region_starWithCutout() {
1224
1225
1226 final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1227 tree.insert(LinePath.builder(TEST_PRECISION)
1228 .append(Vector2D.of(0, 4))
1229 .append(Vector2D.of(-1.5, 1))
1230 .append(Vector2D.of(-4, 1))
1231 .append(Vector2D.of(-2, -1))
1232 .append(Vector2D.of(-3, -4))
1233 .append(Vector2D.of(0, -2))
1234 .append(Vector2D.of(3, -4))
1235 .append(Vector2D.of(2, -1))
1236 .append(Vector2D.of(4, 1))
1237 .append(Vector2D.of(1.5, 1))
1238 .close());
1239 tree.insert(LinePath.builder(TEST_PRECISION)
1240 .append(Vector2D.of(0, 1))
1241 .append(Vector2D.of(1, 0))
1242 .append(Vector2D.of(0, -1))
1243 .append(Vector2D.of(-1, 0))
1244 .close());
1245
1246 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, -1),
1247 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1248 final Vector3D extrusionVector = Vector3D.of(0, 0, 2);
1249
1250
1251 final List<PlaneConvexSubset> boundaries = Planes.extrude(tree, plane, extrusionVector, TEST_PRECISION);
1252
1253
1254 final RegionBSPTree3D resultTree = RegionBSPTree3D.from(boundaries);
1255
1256 Assertions.assertTrue(resultTree.isFinite());
1257 EuclideanTestUtils.assertRegionLocation(resultTree, RegionLocation.OUTSIDE, resultTree.getCentroid());
1258 }
1259
1260 @Test
1261 void testExtrude_invalidExtrusionVector() {
1262
1263 final List<Vector2D> vertices = new ArrayList<>();
1264 final LinePath path = LinePath.empty();
1265 final RegionBSPTree2D tree = RegionBSPTree2D.empty();
1266
1267 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
1268 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
1269
1270 final Pattern errorPattern = Pattern.compile("^Extrusion vector produces regions of zero size.*");
1271
1272
1273 GeometryTestUtils.assertThrowsWithMessage(() -> {
1274 Planes.extrudeVertexLoop(vertices, plane, Vector3D.of(1e-16, 0, 0), TEST_PRECISION);
1275 }, IllegalArgumentException.class, errorPattern);
1276 GeometryTestUtils.assertThrowsWithMessage(() -> {
1277 Planes.extrudeVertexLoop(vertices, plane, Vector3D.of(4, 1e-16, 0), TEST_PRECISION);
1278 }, IllegalArgumentException.class, errorPattern);
1279 GeometryTestUtils.assertThrowsWithMessage(() -> {
1280 Planes.extrudeVertexLoop(vertices, plane, Vector3D.of(1e-16, 5, 0), TEST_PRECISION);
1281 }, IllegalArgumentException.class, errorPattern);
1282
1283 GeometryTestUtils.assertThrowsWithMessage(() -> {
1284 Planes.extrude(path, plane, Vector3D.of(1e-16, 0, 0), TEST_PRECISION);
1285 }, IllegalArgumentException.class, errorPattern);
1286 GeometryTestUtils.assertThrowsWithMessage(() -> {
1287 Planes.extrude(path, plane, Vector3D.of(4, 1e-16, 0), TEST_PRECISION);
1288 }, IllegalArgumentException.class, errorPattern);
1289 GeometryTestUtils.assertThrowsWithMessage(() -> {
1290 Planes.extrude(path, plane, Vector3D.of(1e-16, 5, 0), TEST_PRECISION);
1291 }, IllegalArgumentException.class, errorPattern);
1292
1293 GeometryTestUtils.assertThrowsWithMessage(() -> {
1294 Planes.extrude(tree, plane, Vector3D.of(1e-16, 0, 0), TEST_PRECISION);
1295 }, IllegalArgumentException.class, errorPattern);
1296 GeometryTestUtils.assertThrowsWithMessage(() -> {
1297 Planes.extrude(tree, plane, Vector3D.of(4, 1e-16, 0), TEST_PRECISION);
1298 }, IllegalArgumentException.class, errorPattern);
1299 GeometryTestUtils.assertThrowsWithMessage(() -> {
1300 Planes.extrude(tree, plane, Vector3D.of(1e-16, 5, 0), TEST_PRECISION);
1301 }, IllegalArgumentException.class, errorPattern);
1302 }
1303
1304 private static void checkPlane(final Plane plane, final Vector3D origin, Vector3D u, Vector3D v) {
1305 u = u.normalize();
1306 v = v.normalize();
1307 final Vector3D w = u.cross(v);
1308
1309 EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getOrigin(), TEST_EPS);
1310 Assertions.assertTrue(plane.contains(origin));
1311
1312 EuclideanTestUtils.assertCoordinatesEqual(w, plane.getNormal(), TEST_EPS);
1313 Assertions.assertEquals(1.0, plane.getNormal().norm(), TEST_EPS);
1314
1315 final double offset = plane.getOriginOffset();
1316 Assertions.assertEquals(Vector3D.ZERO.distance(plane.getOrigin()), Math.abs(offset), TEST_EPS);
1317 EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getNormal().multiply(-offset), TEST_EPS);
1318 }
1319
1320 private static void checkPoints(final PlaneConvexSubset sp, final RegionLocation loc, final Vector3D... pts) {
1321 for (final Vector3D pt : pts) {
1322 Assertions.assertEquals(loc, sp.classify(pt), "Unexpected location for point " + pt);
1323 }
1324 }
1325
1326 private static void assertConvexAreasEqual(final ConvexArea a, final ConvexArea b) {
1327 final List<LineConvexSubset> aBoundaries = new ArrayList<>(a.getBoundaries());
1328 final List<LineConvexSubset> bBoundaries = new ArrayList<>(b.getBoundaries());
1329
1330 Assertions.assertEquals(aBoundaries.size(), bBoundaries.size());
1331
1332 for (final LineConvexSubset aBoundary : aBoundaries) {
1333 if (!hasEquivalentSubLine(aBoundary, bBoundaries)) {
1334 Assertions.fail("Failed to find equivalent subline for " + aBoundary);
1335 }
1336 }
1337 }
1338
1339 private static boolean hasEquivalentSubLine(final LineConvexSubset target, final Collection<? extends LineConvexSubset> subsets) {
1340 final Line line = target.getLine();
1341 final double start = target.getSubspaceStart();
1342 final double end = target.getSubspaceEnd();
1343
1344 for (final LineConvexSubset subset : subsets) {
1345 if (line.eq(subset.getLine(), TEST_PRECISION) &&
1346 TEST_PRECISION.eq(start, subset.getSubspaceStart()) &&
1347 TEST_PRECISION.eq(end, subset.getSubspaceEnd())) {
1348 return true;
1349 }
1350 }
1351
1352 return false;
1353 }
1354 }