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.Arrays;
20 import java.util.List;
21
22 import org.apache.commons.geometry.core.RegionLocation;
23 import org.apache.commons.geometry.core.Transform;
24 import org.apache.commons.geometry.core.partitioning.Split;
25 import org.apache.commons.geometry.core.partitioning.SplitLocation;
26 import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
27 import org.apache.commons.geometry.euclidean.threed.line.Lines3D;
28 import org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation;
29 import org.apache.commons.geometry.euclidean.twod.ConvexArea;
30 import org.apache.commons.geometry.euclidean.twod.Lines;
31 import org.apache.commons.geometry.euclidean.twod.Vector2D;
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 PlaneConvexSubsetTest {
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 @Test
45 void testToConvex() {
46
47 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(
48 Arrays.asList(Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_Z), TEST_PRECISION);
49
50
51 final List<PlaneConvexSubset> convex = sp.toConvex();
52
53
54 Assertions.assertEquals(1, convex.size());
55 Assertions.assertSame(sp, convex.get(0));
56 }
57
58 @Test
59 void testReverse() {
60
61 final Vector3D p1 = Vector3D.of(1, 0, 1);
62 final Vector3D p2 = Vector3D.of(2, 0, 1);
63 final Vector3D p3 = Vector3D.of(1, 1, 1);
64
65 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(p1, p2, p3), TEST_PRECISION);
66
67
68 final PlaneConvexSubset reversed = sp.reverse();
69
70
71 Assertions.assertEquals(sp.getPlane().reverse(), reversed.getPlane());
72 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_Z, reversed.getPlane().getNormal(), TEST_EPS);
73
74 Assertions.assertEquals(0.5, reversed.getSize(), TEST_EPS);
75
76 checkVertices(reversed, p1, p3, p2);
77
78 checkPoints(reversed, RegionLocation.INSIDE, Vector3D.of(1.25, 0.25, 1));
79
80 checkPoints(reversed, RegionLocation.BOUNDARY, p1, p2, p3);
81 }
82
83 @Test
84 void testTransform_full() {
85
86 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.Unit.PLUS_Z, Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
87 final PlaneConvexSubset sp = Planes.subsetFromConvexArea(plane, ConvexArea.full());
88
89 final AffineTransformMatrix3D transform = AffineTransformMatrix3D.identity()
90 .rotate(QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_X, Angle.PI_OVER_TWO))
91 .translate(Vector3D.Unit.PLUS_Y);
92
93
94 final PlaneConvexSubset transformed = sp.transform(transform);
95
96
97 Assertions.assertTrue(transformed.isFull());
98 Assertions.assertFalse(transformed.isEmpty());
99
100 checkPlane(transformed.getPlane(), Vector3D.ZERO, Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Z);
101 }
102
103 @Test
104 void testTransform_halfSpace() {
105
106 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.Unit.PLUS_Z, Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
107 final PlaneConvexSubset sp = Planes.subsetFromConvexArea(plane,
108 ConvexArea.fromBounds(Lines.fromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), TEST_PRECISION)));
109
110 final AffineTransformMatrix3D transform = AffineTransformMatrix3D.createRotation(Vector3D.Unit.PLUS_Z,
111 QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Y, Angle.PI_OVER_TWO));
112
113
114 final PlaneConvexSubset transformed = sp.transform(transform);
115
116
117 Assertions.assertFalse(transformed.isFull());
118 Assertions.assertFalse(transformed.isEmpty());
119
120 checkPlane(transformed.getPlane(), Vector3D.ZERO, Vector3D.Unit.MINUS_Z, Vector3D.Unit.PLUS_Y);
121 }
122
123 @Test
124 void testTransform_finite() {
125
126 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(
127 Arrays.asList(Vector3D.of(1, 0, 0), Vector3D.of(0, 1, 0), Vector3D.of(0, 0, 1)), TEST_PRECISION);
128
129 final Transform<Vector3D> transform = AffineTransformMatrix3D.createScale(2)
130 .rotate(QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Y, Angle.PI_OVER_TWO));
131
132
133 final PlaneConvexSubset transformed = sp.transform(transform);
134
135
136 final Vector3D midpt = Vector3D.of(2, 2, -2).multiply(1 / 3.0);
137 final Vector3D normal = midpt.normalize();
138 final Vector3D u = Vector3D.of(0, 2, 2).normalize();
139
140 checkPlane(transformed.getPlane(), midpt, u, normal.cross(u));
141
142 checkVertices(transformed, Vector3D.of(0, 0, -2), Vector3D.of(0, 2, 0), Vector3D.of(2, 0, 0));
143
144 checkPoints(transformed, RegionLocation.INSIDE, midpt);
145 }
146
147 @Test
148 void testTransform_reflection() {
149
150 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(
151 Arrays.asList(Vector3D.of(1, 0, 0), Vector3D.of(0, 1, 0), Vector3D.of(0, 0, 1)), TEST_PRECISION);
152
153 final Transform<Vector3D> transform = AffineTransformMatrix3D.createScale(-1, 1, 1);
154
155
156 final PlaneConvexSubset transformed = sp.transform(transform);
157
158
159 final Vector3D midpt = Vector3D.of(-1, 1, 1).multiply(1 / 3.0);
160 final Vector3D normal = midpt.negate().normalize();
161 final Vector3D u = Vector3D.of(1, 1, 0).normalize();
162
163 checkPlane(transformed.getPlane(), midpt, u, normal.cross(u));
164
165 checkVertices(transformed, Vector3D.of(-1, 0, 0), Vector3D.of(0, 1, 0), Vector3D.of(0, 0, 1));
166
167 checkPoints(transformed, RegionLocation.INSIDE, Vector3D.of(-1, 1, 1).multiply(1 / 3.0));
168 }
169
170 @Test
171 void testSplit_full() {
172
173 final EmbeddingPlane plane = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_Z, TEST_PRECISION)
174 .getEmbedding();
175 final PlaneConvexSubset sp = Planes.subsetFromConvexArea(plane, ConvexArea.full());
176
177 final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION);
178
179
180 final Split<PlaneConvexSubset> split = sp.split(splitter);
181
182
183 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
184
185 final PlaneConvexSubset minus = split.getMinus();
186 Assertions.assertEquals(1, minus.getEmbedded().getSubspaceRegion().getBoundaries().size());
187 checkPoints(minus, RegionLocation.BOUNDARY, Vector3D.ZERO, Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_Y);
188 checkPoints(minus, RegionLocation.INSIDE, Vector3D.Unit.MINUS_X);
189 checkPoints(minus, RegionLocation.OUTSIDE, Vector3D.Unit.PLUS_X);
190
191 final PlaneConvexSubset plus = split.getPlus();
192 Assertions.assertEquals(1, plus.getEmbedded().getSubspaceRegion().getBoundaries().size());
193 checkPoints(plus, RegionLocation.BOUNDARY, Vector3D.ZERO, Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_Y);
194 checkPoints(plus, RegionLocation.INSIDE, Vector3D.Unit.PLUS_X);
195 checkPoints(plus, RegionLocation.OUTSIDE, Vector3D.Unit.MINUS_X);
196 }
197
198 @Test
199 void testSplit_both() {
200
201 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
202 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
203 ), TEST_PRECISION);
204
205 final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_Z, TEST_PRECISION);
206
207
208 final Split<PlaneConvexSubset> split = sp.split(splitter);
209
210
211 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
212
213 final PlaneConvexSubset minus = split.getMinus();
214 checkVertices(minus, Vector3D.of(1, 1, 0), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0));
215
216 final PlaneConvexSubset plus = split.getPlus();
217 checkVertices(plus, Vector3D.of(1, 1, 1), Vector3D.of(1, 1, 0), Vector3D.of(0, 2, 0));
218 }
219
220 @Test
221 void testSplit_plusOnly() {
222
223 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
224 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
225 ), TEST_PRECISION);
226
227 final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, -3.1), Vector3D.Unit.PLUS_Z, TEST_PRECISION);
228
229
230 final Split<PlaneConvexSubset> split = sp.split(splitter);
231
232
233 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
234
235 Assertions.assertNull(split.getMinus());
236
237 final PlaneConvexSubset plus = split.getPlus();
238 checkVertices(plus, Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0));
239 }
240
241 @Test
242 void testSplit_minusOnly() {
243
244 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
245 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
246 ), TEST_PRECISION);
247
248 final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, 1.1), Vector3D.Unit.PLUS_Z, TEST_PRECISION);
249
250
251 final Split<PlaneConvexSubset> split = sp.split(splitter);
252
253
254 Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
255
256 final PlaneConvexSubset minus = split.getMinus();
257 checkVertices(minus, Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0));
258
259 Assertions.assertNull(split.getPlus());
260 }
261
262 @Test
263 void testSplit_parallelSplitter_on() {
264
265 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
266 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
267 ), TEST_PRECISION);
268
269 final Plane splitter = sp.getPlane();
270
271
272 final Split<PlaneConvexSubset> split = sp.split(splitter);
273
274
275 Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
276
277 Assertions.assertNull(split.getMinus());
278 Assertions.assertNull(split.getPlus());
279 }
280
281 @Test
282 void testSplit_parallelSplitter_minus() {
283
284 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
285 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
286 ), TEST_PRECISION);
287
288 final Plane plane = sp.getPlane();
289 final Plane splitter = plane.translate(plane.getNormal());
290
291
292 final Split<PlaneConvexSubset> split = sp.split(splitter);
293
294
295 Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
296
297 Assertions.assertSame(sp, split.getMinus());
298 Assertions.assertNull(split.getPlus());
299 }
300
301 @Test
302 void testSplit_parallelSplitter_plus() {
303
304 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
305 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
306 ), TEST_PRECISION);
307
308 final Plane plane = sp.getPlane();
309 final Plane splitter = plane.translate(plane.getNormal().negate());
310
311
312 final Split<PlaneConvexSubset> split = sp.split(splitter);
313
314
315 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
316
317 Assertions.assertNull(split.getMinus());
318 Assertions.assertSame(sp, split.getPlus());
319 }
320
321 @Test
322 void testSplit_antiParallelSplitter_on() {
323
324 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
325 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
326 ), TEST_PRECISION);
327
328 final Plane splitter = sp.getPlane().reverse();
329
330
331 final Split<PlaneConvexSubset> split = sp.split(splitter);
332
333
334 Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
335
336 Assertions.assertNull(split.getMinus());
337 Assertions.assertNull(split.getPlus());
338 }
339
340 @Test
341 void testSplit_antiParallelSplitter_minus() {
342
343 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
344 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
345 ), TEST_PRECISION);
346
347 final Plane plane = sp.getPlane().reverse();
348 final Plane splitter = plane.translate(plane.getNormal());
349
350
351 final Split<PlaneConvexSubset> split = sp.split(splitter);
352
353
354 Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
355
356 Assertions.assertSame(sp, split.getMinus());
357 Assertions.assertNull(split.getPlus());
358 }
359
360 @Test
361 void testSplit_antiParallelSplitter_plus() {
362
363 final PlaneConvexSubset ps = Planes.convexPolygonFromVertices(Arrays.asList(
364 Vector3D.of(1, 1, 1), Vector3D.of(1, 1, -3), Vector3D.of(0, 2, 0)
365 ), TEST_PRECISION);
366
367 final Plane plane = ps.getPlane().reverse();
368 final Plane splitter = plane.translate(plane.getNormal().negate());
369
370
371 final Split<PlaneConvexSubset> split = ps.split(splitter);
372
373
374 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
375
376 Assertions.assertNull(split.getMinus());
377 Assertions.assertSame(ps, split.getPlus());
378 }
379
380 @Test
381 void testSplit_usesVertexBasedTypesWhenPossible() {
382
383
384 final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.ZERO,
385 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
386 final PlaneConvexSubset ps = Planes.subsetFromConvexArea(plane, ConvexArea.fromBounds(
387 Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION),
388 Lines.fromPointAndAngle(Vector2D.of(1, 0), Angle.PI_OVER_TWO, TEST_PRECISION),
389 Lines.fromPointAndAngle(Vector2D.of(0, 1), -Angle.PI_OVER_TWO, TEST_PRECISION)
390 ));
391
392 final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 1, 0), Vector3D.Unit.PLUS_Y, TEST_PRECISION);
393
394
395 final Split<PlaneConvexSubset> split = ps.split(splitter);
396
397
398 Assertions.assertTrue(ps.isInfinite());
399
400 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
401
402 final PlaneConvexSubset plus = split.getPlus();
403 Assertions.assertNotNull(plus);
404 Assertions.assertTrue(plus.isInfinite());
405 Assertions.assertFalse(plus instanceof ConvexPolygon3D);
406
407 final PlaneConvexSubset minus = split.getMinus();
408 Assertions.assertNotNull(minus);
409 Assertions.assertFalse(minus.isInfinite());
410 Assertions.assertTrue(minus instanceof ConvexPolygon3D);
411 }
412
413 @Test
414 void testIntersection_line() {
415
416 final PlaneConvexSubset ps = Planes.convexPolygonFromVertices(Arrays.asList(
417 Vector3D.of(0, 0, 2), Vector3D.of(1, 0, 2), Vector3D.of(1, 1, 2), Vector3D.of(0, 1, 2)),
418 TEST_PRECISION);
419
420
421 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 2),
422 ps.intersection(Lines3D.fromPoints(Vector3D.of(0.5, 0.5, 2), Vector3D.ZERO, TEST_PRECISION)), TEST_EPS);
423
424 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 2),
425 ps.intersection(Lines3D.fromPoints(Vector3D.of(1, 1, 2), Vector3D.of(1, 1, 0), TEST_PRECISION)), TEST_EPS);
426
427 Assertions.assertNull(ps.intersection(Lines3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION)));
428 Assertions.assertNull(ps.intersection(Lines3D.fromPoints(Vector3D.of(0, 0, 2), Vector3D.of(1, 1, 2), TEST_PRECISION)));
429
430 Assertions.assertNull(ps.intersection(Lines3D.fromPoints(Vector3D.of(4, 4, 2), Vector3D.of(4, 4, 0), TEST_PRECISION)));
431 }
432
433 @Test
434 void testIntersection_segment() {
435
436 final PlaneConvexSubset sp = Planes.convexPolygonFromVertices(Arrays.asList(
437 Vector3D.of(0, 0, 2), Vector3D.of(1, 0, 2), Vector3D.of(1, 1, 2), Vector3D.of(0, 1, 2)),
438 TEST_PRECISION);
439
440
441 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 2),
442 sp.intersection(Lines3D.segmentFromPoints(Vector3D.of(0.5, 0.5, 2), Vector3D.ZERO, TEST_PRECISION)), TEST_EPS);
443
444 EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 2),
445 sp.intersection(Lines3D.segmentFromPoints(Vector3D.of(1, 1, 2), Vector3D.of(1, 1, 0), TEST_PRECISION)), TEST_EPS);
446
447 Assertions.assertNull(sp.intersection(Lines3D.segmentFromPoints(Vector3D.of(0.5, 0.5, 4), Vector3D.of(0.5, 0.5, 3), TEST_PRECISION)));
448
449 Assertions.assertNull(sp.intersection(Lines3D.segmentFromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION)));
450 Assertions.assertNull(sp.intersection(Lines3D.segmentFromPoints(Vector3D.of(0, 0, 2), Vector3D.of(1, 1, 2), TEST_PRECISION)));
451
452 Assertions.assertNull(sp.intersection(Lines3D.segmentFromPoints(Vector3D.of(4, 4, 2), Vector3D.of(4, 4, 0), TEST_PRECISION)));
453 }
454
455 private static void checkPlane(final Plane plane, final Vector3D origin, Vector3D u, Vector3D v) {
456 u = u.normalize();
457 v = v.normalize();
458 final Vector3D w = u.cross(v);
459
460 EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getOrigin(), TEST_EPS);
461 Assertions.assertTrue(plane.contains(origin));
462
463 EuclideanTestUtils.assertCoordinatesEqual(w, plane.getNormal(), TEST_EPS);
464 Assertions.assertEquals(1.0, plane.getNormal().norm(), TEST_EPS);
465
466 final double offset = plane.getOriginOffset();
467 Assertions.assertEquals(Vector3D.ZERO.distance(plane.getOrigin()), Math.abs(offset), TEST_EPS);
468 EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getNormal().multiply(-offset), TEST_EPS);
469 }
470
471 private static void checkPoints(final PlaneConvexSubset sp, final RegionLocation loc, final Vector3D... pts) {
472 for (final Vector3D pt : pts) {
473 Assertions.assertEquals(loc, sp.classify(pt), "Unexpected location for point " + pt);
474 }
475 }
476
477 private static void checkVertices(final PlaneConvexSubset ps, final Vector3D... pts) {
478 EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(pts), ps.getVertices(), TEST_PRECISION);
479 }
480 }