View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.geometry.euclidean.threed;
18  
19  import java.util.Arrays;
20  import java.util.List;
21  import java.util.regex.Pattern;
22  
23  import org.apache.commons.geometry.core.GeometryTestUtils;
24  import org.apache.commons.geometry.core.RegionLocation;
25  import org.apache.commons.geometry.core.partitioning.Split;
26  import org.apache.commons.geometry.core.partitioning.SplitLocation;
27  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
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.geometry.euclidean.twod.path.LinePath;
33  import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
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 EmbeddedAreaPlaneConvexSubsetTest {
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 EmbeddingPlane XY_PLANE_Z1 = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
47              Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
48  
49      @Test
50      void testSpaceConversion() {
51          // arrange
52          final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(1, 0, 0),
53                  Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_Z, TEST_PRECISION);
54  
55          final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(plane, ConvexArea.full());
56  
57          // act/assert
58          EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 2), ps.toSubspace(Vector3D.of(-5, 1, 2)), TEST_EPS);
59          EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -2, 4), ps.toSpace(Vector2D.of(-2, 4)), TEST_EPS);
60      }
61  
62      @Test
63      void testProperties_infinite() {
64          // arrange
65          final ConvexArea area = ConvexArea.full();
66  
67          // act
68          final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1, area);
69  
70          // assert
71          Assertions.assertTrue(ps.isFull());
72          Assertions.assertFalse(ps.isEmpty());
73          Assertions.assertFalse(ps.isFinite());
74          Assertions.assertTrue(ps.isInfinite());
75  
76          GeometryTestUtils.assertPositiveInfinity(ps.getSize());
77  
78          Assertions.assertSame(XY_PLANE_Z1, ps.getPlane());
79          Assertions.assertSame(area, ps.getSubspaceRegion());
80  
81          Assertions.assertEquals(0, ps.getVertices().size());
82      }
83  
84      @Test
85      void testProperties_finite() {
86          // arrange
87          final ConvexArea area = ConvexArea.convexPolygonFromPath(LinePath.builder(TEST_PRECISION)
88                  .appendVertices(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1))
89                  .build(true));
90  
91          // act
92          final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1, area);
93  
94          // assert
95          Assertions.assertFalse(ps.isFull());
96          Assertions.assertFalse(ps.isEmpty());
97          Assertions.assertTrue(ps.isFinite());
98          Assertions.assertFalse(ps.isInfinite());
99  
100         Assertions.assertEquals(0.5, ps.getSize(), TEST_EPS);
101 
102         Assertions.assertSame(XY_PLANE_Z1, ps.getPlane());
103         Assertions.assertSame(area, ps.getSubspaceRegion());
104 
105         EuclideanTestUtils.assertVertexLoopSequence(
106                 Arrays.asList(Vector3D.of(0, 0, 1), Vector3D.of(1, 0, 1), Vector3D.of(0, 1, 1)),
107                 ps.getVertices(), TEST_PRECISION);
108     }
109 
110     @Test
111     void testGetVertices_twoParallelLines() {
112         // arrange
113         final EmbeddingPlane plane = Planes.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION).getEmbedding();
114         final PlaneConvexSubset sp = new EmbeddedAreaPlaneConvexSubset(plane, ConvexArea.fromBounds(
115                     Lines.fromPointAndAngle(Vector2D.of(0, 1), Math.PI, TEST_PRECISION),
116                     Lines.fromPointAndAngle(Vector2D.of(0, -1), 0.0, TEST_PRECISION)
117                 ));
118 
119         // act
120         final List<Vector3D> vertices = sp.getVertices();
121 
122         // assert
123         Assertions.assertEquals(0, vertices.size());
124     }
125 
126     @Test
127     void testGetVertices_infiniteWithVertices() {
128         // arrange
129         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
130         final PlaneConvexSubset sp = new EmbeddedAreaPlaneConvexSubset(plane, ConvexArea.fromBounds(
131                     Lines.fromPointAndAngle(Vector2D.of(0, 1), Math.PI, TEST_PRECISION),
132                     Lines.fromPointAndAngle(Vector2D.of(0, -1), 0.0, TEST_PRECISION),
133                     Lines.fromPointAndAngle(Vector2D.of(1, 0), Angle.PI_OVER_TWO, TEST_PRECISION)
134                 ));
135 
136         // act
137         final List<Vector3D> vertices = sp.getVertices();
138 
139         // assert
140         Assertions.assertEquals(2, vertices.size());
141 
142         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, -1, 1), vertices.get(0), TEST_EPS);
143         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 1), vertices.get(1), TEST_EPS);
144     }
145     @Test
146     void testToTriangles_infinite() {
147         // arrange
148         final Pattern pattern = Pattern.compile("^Cannot convert infinite plane subset to triangles: .*");
149 
150         // act/assert
151         GeometryTestUtils.assertThrowsWithMessage(() -> {
152             new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1, ConvexArea.full()).toTriangles();
153         }, IllegalStateException.class, pattern);
154 
155         GeometryTestUtils.assertThrowsWithMessage(() -> {
156             final ConvexArea area = ConvexArea.fromBounds(Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION));
157             final EmbeddedAreaPlaneConvexSubset halfSpace = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1, area);
158 
159             halfSpace.toTriangles();
160         }, IllegalStateException.class, pattern);
161 
162         GeometryTestUtils.assertThrowsWithMessage(() -> {
163             final ConvexArea area = ConvexArea.fromBounds(
164                     Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION),
165                     Lines.fromPointAndAngle(Vector2D.ZERO, 0.5 * Math.PI, TEST_PRECISION));
166 
167             final EmbeddedAreaPlaneConvexSubset halfSpaceWithVertices = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1, area);
168 
169             halfSpaceWithVertices.toTriangles();
170         }, IllegalStateException.class, pattern);
171     }
172 
173     @Test
174     void testToTriangles_finite() {
175         // arrange
176         final Vector3D p1 = Vector3D.of(0, 0, 1);
177         final Vector3D p2 = Vector3D.of(1, 0, 1);
178         final Vector3D p3 = Vector3D.of(2, 1, 1);
179         final Vector3D p4 = Vector3D.of(1.5, 1, 1);
180 
181         final List<Vector2D> subPts = XY_PLANE_Z1.toSubspace(Arrays.asList(p1, p2, p3, p4));
182 
183         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
184                 ConvexArea.convexPolygonFromVertices(subPts, TEST_PRECISION));
185 
186         // act
187         final List<Triangle3D> tris = ps.toTriangles();
188 
189         // assert
190         Assertions.assertEquals(2, tris.size());
191 
192         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p1, p2),
193                 tris.get(0).getVertices(), TEST_PRECISION);
194         EuclideanTestUtils.assertVertexLoopSequence(Arrays.asList(p4, p2, p3),
195                 tris.get(1).getVertices(), TEST_PRECISION);
196     }
197 
198     @Test
199     void testClassify() {
200         // arrange
201         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
202                 Parallelogram.builder(TEST_PRECISION)
203                     .setPosition(Vector2D.of(2, 3))
204                     .setScale(2, 2)
205                     .build());
206 
207         // act/assert
208         checkPoints(ps, RegionLocation.INSIDE, Vector3D.of(2, 3, 1));
209         checkPoints(ps, RegionLocation.BOUNDARY,
210                 Vector3D.of(1, 3, 1), Vector3D.of(3, 3, 1),
211                 Vector3D.of(2, 2, 1), Vector3D.of(2, 4, 1));
212         checkPoints(ps, RegionLocation.OUTSIDE,
213                 Vector3D.of(2, 3, 0), Vector3D.of(2, 3, 2),
214                 Vector3D.of(0, 3, 1), Vector3D.of(4, 3, 1),
215                 Vector3D.of(2, 1, 1), Vector3D.of(2, 5, 1));
216     }
217 
218     @Test
219     void testClosest() {
220         // arrange
221         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
222                 Parallelogram.builder(TEST_PRECISION)
223                     .setPosition(Vector2D.of(2, 3))
224                     .setScale(2, 2)
225                     .build());
226 
227         // act/assert
228         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 3, 1), ps.closest(Vector3D.of(2, 3, 1)), TEST_EPS);
229         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(2, 3, 1), ps.closest(Vector3D.of(2, 3, 100)), TEST_EPS);
230         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 1),
231                 ps.closest(Vector3D.of(-100, -100, -100)), TEST_EPS);
232         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 3.5, 1),
233                 ps.closest(Vector3D.of(100, 3.5, 100)), TEST_EPS);
234     }
235 
236     @Test
237     void testGetBounds_noBounds() {
238         // arrange
239         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
240                 Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_X, TEST_PRECISION);
241 
242         final EmbeddedAreaPlaneConvexSubset full = new EmbeddedAreaPlaneConvexSubset(plane, ConvexArea.full());
243         final EmbeddedAreaPlaneConvexSubset halfPlane = new EmbeddedAreaPlaneConvexSubset(plane,
244                 ConvexArea.fromBounds(Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION)));
245 
246         // act/assert
247         Assertions.assertNull(full.getBounds());
248         Assertions.assertNull(halfPlane.getBounds());
249     }
250 
251     @Test
252     void testGetBounds_hasBounds() {
253         // arrange
254         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1),
255                 Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_X, TEST_PRECISION);
256 
257         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(plane,
258                 ConvexArea.convexPolygonFromVertices(Arrays.asList(
259                     Vector2D.of(1, 1), Vector2D.of(2, 1), Vector2D.of(1, 2)
260                 ), TEST_PRECISION));
261 
262         // act
263         final Bounds3D bounds = ps.getBounds();
264 
265         // assert
266         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-2, 1, 1), bounds.getMin(), TEST_EPS);
267         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 2, 1), bounds.getMax(), TEST_EPS);
268     }
269 
270     @Test
271     void testTransform() {
272         // arrange
273         final AffineTransformMatrix3D t = AffineTransformMatrix3D.identity()
274                 .rotate(QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Y, -Angle.PI_OVER_TWO))
275                 .scale(1, 1, 2)
276                 .translate(Vector3D.of(1, 0, 0));
277 
278         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
279                 Parallelogram.builder(TEST_PRECISION)
280                     .setPosition(Vector2D.of(2, 3))
281                     .setScale(2, 2)
282                     .build());
283 
284         // act
285         final EmbeddedAreaPlaneConvexSubset result = ps.transform(t);
286 
287         // assert
288         Assertions.assertFalse(result.isFull());
289         Assertions.assertFalse(result.isEmpty());
290         Assertions.assertTrue(result.isFinite());
291         Assertions.assertFalse(result.isInfinite());
292 
293         Assertions.assertEquals(8, result.getSize(), TEST_EPS);
294 
295         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X, result.getPlane().getNormal(), TEST_EPS);
296         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_Z, result.getPlane().getU(), TEST_EPS);
297 
298         EuclideanTestUtils.assertVertexLoopSequence(
299                 Arrays.asList(Vector3D.of(0, 2, 2), Vector3D.of(0, 2, 6), Vector3D.of(0, 4, 6), Vector3D.of(0, 4, 2)),
300                 result.getVertices(), TEST_PRECISION);
301     }
302 
303     @Test
304     void testReverse() {
305         // arrange
306         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
307                 Parallelogram.builder(TEST_PRECISION)
308                     .setPosition(Vector2D.of(2, 3))
309                     .setScale(2, 2)
310                     .build());
311 
312         // act
313         final EmbeddedAreaPlaneConvexSubset result = ps.reverse();
314 
315         // assert
316         Assertions.assertFalse(result.isFull());
317         Assertions.assertFalse(result.isEmpty());
318         Assertions.assertTrue(result.isFinite());
319         Assertions.assertFalse(result.isInfinite());
320 
321         Assertions.assertEquals(4, result.getSize(), TEST_EPS);
322 
323         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_Z, result.getPlane().getNormal(), TEST_EPS);
324         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_Y, result.getPlane().getU(), TEST_EPS);
325 
326         EuclideanTestUtils.assertVertexLoopSequence(
327                 Arrays.asList(Vector3D.of(1, 4, 1), Vector3D.of(3, 4, 1), Vector3D.of(3, 2, 1), Vector3D.of(1, 2, 1)),
328                 result.getVertices(), TEST_PRECISION);
329     }
330 
331     @Test
332     void testSplit_plus() {
333         // arrange
334         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
335                 ConvexArea.convexPolygonFromVertices(Arrays.asList(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1)),
336                         TEST_PRECISION));
337 
338         final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION);
339 
340         // act
341         final Split<PlaneConvexSubset> split = ps.split(splitter);
342 
343         // assert
344         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
345 
346         Assertions.assertNull(split.getMinus());
347         Assertions.assertSame(ps, split.getPlus());
348     }
349 
350     @Test
351     void testSplit_minus() {
352         // arrange
353         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
354                 ConvexArea.convexPolygonFromVertices(Arrays.asList(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1)),
355                         TEST_PRECISION));
356 
357         final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.Unit.MINUS_Z, TEST_PRECISION);
358 
359         // act
360         final Split<PlaneConvexSubset> split = ps.split(splitter);
361 
362         // assert
363         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
364 
365         Assertions.assertSame(ps, split.getMinus());
366         Assertions.assertNull(split.getPlus());
367     }
368 
369     @Test
370     void testSplit_both() {
371         // arrange
372         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
373                 ConvexArea.convexPolygonFromVertices(Arrays.asList(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1)),
374                         TEST_PRECISION));
375 
376         final Plane splitter = Planes.fromPointAndNormal(Vector3D.ZERO, Vector3D.of(-1, 1, 0), TEST_PRECISION);
377 
378         // act
379         final Split<PlaneConvexSubset> split = ps.split(splitter);
380 
381         // assert
382         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
383 
384         final PlaneConvexSubset minus = split.getMinus();
385         EuclideanTestUtils.assertVertexLoopSequence(
386                 Arrays.asList(Vector3D.of(0, 0, 1), Vector3D.of(1, 0, 1), Vector3D.of(0.5, 0.5, 1)),
387                 minus.getVertices(), TEST_PRECISION);
388 
389         final PlaneConvexSubset plus = split.getPlus();
390         EuclideanTestUtils.assertVertexLoopSequence(
391                 Arrays.asList(Vector3D.of(0, 0, 1), Vector3D.of(0.5, 0.5, 1), Vector3D.of(0, 1, 1)),
392                 plus.getVertices(), TEST_PRECISION);
393     }
394 
395     @Test
396     void testSplit_neither() {
397         // arrange
398         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
399                 ConvexArea.convexPolygonFromVertices(Arrays.asList(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1)),
400                         TEST_PRECISION));
401 
402         final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0, 0, 1), Vector3D.of(0, 1e-15, -1), TEST_PRECISION);
403 
404         // act
405         final Split<PlaneConvexSubset> split = ps.split(splitter);
406 
407         // assert
408         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
409 
410         Assertions.assertNull(split.getMinus());
411         Assertions.assertNull(split.getPlus());
412     }
413 
414     @Test
415     void testSplit_usesVertexBasedSubsetsWhenPossible() {
416         // arrange
417         // create an infinite subset
418         final EmbeddingPlane plane = Planes.fromPointAndPlaneVectors(Vector3D.ZERO,
419                 Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
420         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(plane, ConvexArea.fromBounds(
421                     Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION),
422                     Lines.fromPointAndAngle(Vector2D.of(1, 0), Angle.PI_OVER_TWO, TEST_PRECISION),
423                     Lines.fromPointAndAngle(Vector2D.of(0, 1), -Angle.PI_OVER_TWO, TEST_PRECISION)
424                 ));
425 
426         final Plane splitter = Planes.fromPointAndNormal(Vector3D.of(0.5, 0.5, 0), Vector3D.of(-1, 1, 0), TEST_PRECISION);
427 
428         // act
429         final Split<PlaneConvexSubset> split = ps.split(splitter);
430 
431         // assert
432         Assertions.assertTrue(ps.isInfinite());
433 
434         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
435 
436         final PlaneConvexSubset plus = split.getPlus();
437         Assertions.assertNotNull(plus);
438         Assertions.assertTrue(plus.isInfinite());
439         Assertions.assertTrue(plus instanceof EmbeddedAreaPlaneConvexSubset);
440 
441         final PlaneConvexSubset minus = split.getMinus();
442         Assertions.assertNotNull(minus);
443         Assertions.assertFalse(minus.isInfinite());
444         Assertions.assertTrue(minus instanceof SimpleTriangle3D);
445     }
446 
447     @Test
448     void testToString() {
449         // arrange
450         final EmbeddedAreaPlaneConvexSubset ps = new EmbeddedAreaPlaneConvexSubset(XY_PLANE_Z1,
451                 ConvexArea.convexPolygonFromVertices(Arrays.asList(Vector2D.ZERO, Vector2D.of(1, 0), Vector2D.of(0, 1)),
452                         TEST_PRECISION));
453 
454         // act
455         final String str = ps.toString();
456 
457         // assert
458         GeometryTestUtils.assertContains("EmbeddedAreaPlaneConvexSubset[plane= EmbeddingPlane[", str);
459         GeometryTestUtils.assertContains("subspaceRegion= ConvexArea[", str);
460     }
461 
462     private static void checkPoints(final EmbeddedAreaPlaneConvexSubset ps, final RegionLocation loc, final Vector3D... pts) {
463         for (final Vector3D pt : pts) {
464             Assertions.assertEquals(loc, ps.classify(pt), "Unexpected location for point " + pt);
465         }
466     }
467 }