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;
18  
19  import java.util.Arrays;
20  import java.util.List;
21  import java.util.stream.Collectors;
22  
23  import org.apache.commons.geometry.core.RegionLocation;
24  import org.apache.commons.geometry.core.partitioning.Split;
25  import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
26  import org.apache.commons.geometry.euclidean.oned.Interval;
27  import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D;
28  import org.apache.commons.geometry.euclidean.oned.Vector1D;
29  import org.apache.commons.geometry.euclidean.threed.AffineTransformMatrix3D;
30  import org.apache.commons.geometry.euclidean.threed.ConvexPolygon3D;
31  import org.apache.commons.geometry.euclidean.threed.Plane;
32  import org.apache.commons.geometry.euclidean.threed.PlaneConvexSubset;
33  import org.apache.commons.geometry.euclidean.threed.Planes;
34  import org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D;
35  import org.apache.commons.geometry.euclidean.threed.Vector3D;
36  import org.apache.commons.geometry.euclidean.threed.line.Line3D;
37  import org.apache.commons.geometry.euclidean.threed.line.LinecastPoint3D;
38  import org.apache.commons.geometry.euclidean.threed.line.Lines3D;
39  import org.apache.commons.geometry.euclidean.threed.line.Ray3D;
40  import org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation;
41  import org.apache.commons.geometry.euclidean.threed.shape.Parallelepiped;
42  import org.apache.commons.geometry.euclidean.twod.AffineTransformMatrix2D;
43  import org.apache.commons.geometry.euclidean.twod.Line;
44  import org.apache.commons.geometry.euclidean.twod.LinecastPoint2D;
45  import org.apache.commons.geometry.euclidean.twod.Lines;
46  import org.apache.commons.geometry.euclidean.twod.Ray;
47  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
48  import org.apache.commons.geometry.euclidean.twod.Segment;
49  import org.apache.commons.geometry.euclidean.twod.Vector2D;
50  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
51  import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
52  import org.apache.commons.numbers.angle.Angle;
53  import org.apache.commons.numbers.core.Precision;
54  import org.junit.jupiter.api.Assertions;
55  import org.junit.jupiter.api.Test;
56  
57  /** This class contains code listed as examples in the user guide and other documentation.
58   * If any portion of this code changes, the corresponding examples in the documentation <em>must</em> be updated.
59   */
60  class DocumentationExamplesTest {
61  
62      private static final double TEST_EPS = 1e-12;
63  
64      @Test
65      void testPrecisionContextExample() {
66          // create a precision instance with an epsilon (aka, tolerance) value of 1e-3
67          final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-3);
68  
69          // test for equality using the eq() method
70          precision.eq(1.0009, 1.0); // true; difference is less than epsilon
71          precision.eq(1.002, 1.0); // false; difference is greater than epsilon
72  
73          // compare
74          precision.compare(1.0009, 1.0); // 0
75          precision.compare(1.002, 1.0); // 1
76  
77          // ------------------
78          Assertions.assertTrue(precision.eq(1.0009, 1.0));
79          Assertions.assertFalse(precision.eq(1.002, 1.0));
80  
81          Assertions.assertEquals(0, precision.compare(1.0009, 1.0));
82          Assertions.assertEquals(1, precision.compare(1.002, 1.0));
83      }
84  
85      @Test
86      void testEqualsVsEqExample() {
87          final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
88  
89          final Vector2D v1 = Vector2D.of(1, 1); // (1.0, 1.0)
90          final Vector2D v2 = Vector2D.parse("(1, 1)"); // (1.0, 1.0)
91  
92          final Vector2D v3 = Vector2D.of(Math.sqrt(2), 0).transform(
93                  AffineTransformMatrix2D.createRotation(0.25 * Math.PI)); // (1.0000000000000002, 1.0)
94  
95          v1.equals(v2); // true - exactly equal
96          v1.equals(v3); // false - not exactly equal
97  
98          v1.eq(v3, precision); // true - approximately equal according to the given precision context
99  
100         // ---------------------
101         Assertions.assertEquals(v1, v2);
102         Assertions.assertNotEquals(v1, v3);
103         Assertions.assertTrue(v1.eq(v3, precision));
104     }
105 
106     @Test
107     void testManualBSPTreeExample() {
108         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
109 
110         // create a tree representing an empty space (nothing "inside")
111         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
112 
113         // insert a "structural" cut, meaning a cut whose children have the same inside/outside
114         // status as the parent; this will help keep our tree balanced and limit its overall height
115         tree.getRoot().insertCut(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.of(1, 1), precision),
116                 RegionCutRule.INHERIT);
117 
118         RegionBSPTree2D.RegionNode2D currentNode;
119 
120         // insert on the plus side of the structural diagonal cut
121         currentNode = tree.getRoot().getPlus();
122 
123         currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision));
124         currentNode = currentNode.getMinus();
125 
126         currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.of(1, 0), Vector2D.Unit.PLUS_Y, precision));
127 
128         // insert on the plus side of the structural diagonal cut
129         currentNode = tree.getRoot().getMinus();
130 
131         currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X, precision));
132         currentNode = currentNode.getMinus();
133 
134         currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.of(0, 1), Vector2D.Unit.MINUS_Y, precision));
135 
136         // compute some tree properties
137         final int count = tree.count(); // number of nodes in the tree = 11
138         final int height = tree.height(); // height of the tree = 3
139         final double size = tree.getSize(); // size of the region = 1
140         final Vector2D centroid = tree.getCentroid(); // region centroid = (0.5, 0.5)
141 
142         // ---------
143         Assertions.assertEquals(1, size, TEST_EPS);
144         Assertions.assertEquals(11, count);
145         Assertions.assertEquals(3, height);
146         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), centroid, TEST_EPS);
147     }
148 
149     @Test
150     void testHyperplaneSubsetBSPTreeExample() {
151         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
152 
153         // create a tree representing an empty space (nothing "inside")
154         final RegionBSPTree2D tree = RegionBSPTree2D.empty();
155 
156         // insert the hyperplane subsets
157         tree.insert(Arrays.asList(
158                     Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 0), precision),
159                     Lines.segmentFromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), precision),
160                     Lines.segmentFromPoints(Vector2D.of(1, 1), Vector2D.of(0, 1), precision),
161                     Lines.segmentFromPoints(Vector2D.of(0, 1), Vector2D.ZERO, precision)
162                 ));
163 
164         // compute some tree properties
165         final int count = tree.count(); // number of nodes in the tree = 9
166         final int height = tree.height(); // height of the tree = 4
167         final double size = tree.getSize(); // size of the region = 1
168         final Vector2D centroid = tree.getCentroid(); // region centroid = (0.5, 0.5)
169 
170         // ---------
171         Assertions.assertEquals(1, size, TEST_EPS);
172         Assertions.assertEquals(9, count);
173         Assertions.assertEquals(4, height);
174         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), centroid, TEST_EPS);
175     }
176 
177     @Test
178     void testIntervalExample() {
179         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
180 
181         // create a closed interval and a half-open interval with a min but no max
182         final Interval closed = Interval.of(1, 2, precision);
183         final Interval halfOpen = Interval.min(1, precision);
184 
185         // classify some points against the intervals
186         closed.contains(0.0); // false
187         halfOpen.contains(Vector1D.ZERO); // false
188 
189         final RegionLocation closedOneLoc = closed.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY
190         final RegionLocation halfOpenOneLoc = halfOpen.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY
191 
192         final RegionLocation closedThreeLoc = closed.classify(3.0); // RegionLocation.OUTSIDE
193         final RegionLocation halfOpenThreeLoc = halfOpen.classify(3.0); // RegionLocation.INSIDE
194 
195         // --------------------
196         Assertions.assertFalse(closed.contains(0));
197         Assertions.assertFalse(halfOpen.contains(0));
198 
199         Assertions.assertEquals(RegionLocation.BOUNDARY, closedOneLoc);
200         Assertions.assertEquals(RegionLocation.BOUNDARY, halfOpenOneLoc);
201 
202         Assertions.assertEquals(RegionLocation.OUTSIDE, closedThreeLoc);
203         Assertions.assertEquals(RegionLocation.INSIDE, halfOpenThreeLoc);
204     }
205 
206     @Test
207     void testRegionBSPTree1DExample() {
208         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
209 
210         // build a bsp tree from the union of several intervals
211         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
212 
213         tree.add(Interval.of(1, 2, precision));
214         tree.add(Interval.of(1.5, 3, precision));
215         tree.add(Interval.of(-1, -2, precision));
216 
217         // compute the size;
218         final double size = tree.getSize(); // 3
219 
220         // convert back to intervals
221         final List<Interval> intervals = tree.toIntervals(); // size = 2
222 
223         // ----------------------
224         Assertions.assertEquals(3, size, TEST_EPS);
225         Assertions.assertEquals(2, intervals.size());
226     }
227 
228     @Test
229     void testLineIntersectionExample() {
230         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
231 
232         // create some lines
233         final Line a = Lines.fromPoints(Vector2D.ZERO, Vector2D.of(2, 2), precision);
234         final Line b = Lines.fromPointAndDirection(Vector2D.of(1, -1), Vector2D.Unit.PLUS_Y, precision);
235 
236         // compute the intersection and angles
237         final Vector2D intersection = a.intersection(b); // (1, 1)
238         final double angleAtoB = a.angle(b); // pi/4
239         final double angleBtoA = b.angle(a); // -pi/4
240 
241         // ----------------------------
242         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), intersection, TEST_EPS);
243         Assertions.assertEquals(0.25 * Math.PI, angleAtoB, TEST_EPS);
244         Assertions.assertEquals(-0.25 * Math.PI, angleBtoA, TEST_EPS);
245     }
246 
247     @Test
248     void testLineSegmentIntersectionExample() {
249         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
250 
251         // create some line segments
252         final Segment segmentA = Lines.segmentFromPoints(Vector2D.of(3, -1), Vector2D.of(3, 1), precision);
253         final Segment segmentB = Lines.segmentFromPoints(Vector2D.of(-3, -1), Vector2D.of(-3, 1), precision);
254 
255         // create a ray to intersect against the segments
256         final Ray ray = Lines.rayFromPointAndDirection(Vector2D.of(2, 0), Vector2D.Unit.PLUS_X, precision);
257 
258         // compute some intersections
259         final Vector2D aIntersection = segmentA.intersection(ray); // (3, 0)
260         final Vector2D bIntersection = segmentB.intersection(ray); // null - no intersection
261 
262         // ----------------------------
263         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 0), aIntersection, TEST_EPS);
264         Assertions.assertNull(bIntersection);
265     }
266 
267     @Test
268     void testRegionBSPTree2DExample() {
269         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
270 
271         // create a connected sequence of line segments forming the unit square
272         final LinePath path = LinePath.builder(precision)
273                 .append(Vector2D.ZERO)
274                 .append(Vector2D.Unit.PLUS_X)
275                 .append(Vector2D.of(1, 1))
276                 .append(Vector2D.Unit.PLUS_Y)
277                 .build(true); // build the path, ending it with the starting point
278 
279         // convert to a tree
280         final RegionBSPTree2D tree = path.toTree();
281 
282         // copy the tree
283         final RegionBSPTree2D copy = tree.copy();
284 
285         // translate the copy
286         copy.transform(AffineTransformMatrix2D.createTranslation(Vector2D.of(0.5, 0.5)));
287 
288         // compute the union of the regions, storing the result back into the
289         // first tree
290         tree.union(copy);
291 
292         // compute some properties
293         final double size = tree.getSize(); // 1.75
294         final Vector2D centroid = tree.getCentroid(); // (0.75, 0.75)
295 
296         // get a line path representing the boundary; a list is returned since trees
297         // can represent disjoint regions
298         final List<LinePath> boundaries = tree.getBoundaryPaths(); // size = 1
299 
300         // ----------------
301         Assertions.assertEquals(1.75, size, TEST_EPS);
302         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.75, 0.75), centroid, TEST_EPS);
303         Assertions.assertEquals(1, boundaries.size());
304     }
305 
306     @Test
307     void testLinecast2DExample() {
308         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
309 
310         final Parallelogram box = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), precision);
311 
312         final LinecastPoint2D pt = box.linecastFirst(
313                 Lines.segmentFromPoints(Vector2D.of(1, 0.5), Vector2D.of(4, 0.5), precision));
314 
315         final Vector2D intersection = pt.getPoint(); // (2.0, 0.5)
316         final Vector2D normal = pt.getNormal(); // (1.0, 0.0)
317 
318         // ----------------
319         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 0.5), intersection, TEST_EPS);
320         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), normal, TEST_EPS);
321     }
322 
323     @Test
324     void testPlaneIntersectionExample() {
325         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
326 
327         // create two planes
328         final Plane a = Planes.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z, precision);
329         final Plane b = Planes.fromPointAndPlaneVectors(Vector3D.of(1, 1, 1),
330                 Vector3D.Unit.PLUS_Z, Vector3D.Unit.MINUS_Y, precision);
331 
332         // compute the intersection
333         final Line3D line = a.intersection(b);
334 
335         final Vector3D dir = line.getDirection(); // (0, 1, 0)
336 
337         // ----------------------
338         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_Y, dir, TEST_EPS);
339     }
340 
341     @Test
342     void testTransform3DExample() {
343         final List<Vector3D> inputPts = Arrays.asList(
344                 Vector3D.ZERO,
345                 Vector3D.Unit.PLUS_X,
346                 Vector3D.Unit.PLUS_Y,
347                 Vector3D.Unit.PLUS_Z);
348 
349         // create a 4x4 transform matrix and quaternion rotation
350         final AffineTransformMatrix3D mat = AffineTransformMatrix3D.createScale(2)
351                 .translate(Vector3D.of(1, 2, 3));
352 
353         final QuaternionRotation rot = QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Z,
354                 Angle.PI_OVER_TWO);
355 
356         // transform the input points
357         final List<Vector3D> matOutput = inputPts.stream()
358                 .map(mat)
359                 .collect(Collectors.toList()); // [(1, 2, 3), (3, 2, 3), (1, 4, 3), (1, 2, 5)]
360 
361         final List<Vector3D> rotOutput = inputPts.stream()
362                 .map(rot)
363                 .collect(Collectors.toList()); // [(0, 0, 0), (0, 1, 0), (-1, 0, 0), (0, 0, 1)]
364 
365         // ----------------
366         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 3), matOutput.get(0), TEST_EPS);
367         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 2, 3), matOutput.get(1), TEST_EPS);
368         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 4, 3), matOutput.get(2), TEST_EPS);
369         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 5), matOutput.get(3), TEST_EPS);
370 
371         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 0), rotOutput.get(0), TEST_EPS);
372         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0), rotOutput.get(1), TEST_EPS);
373         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0), rotOutput.get(2), TEST_EPS);
374         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), rotOutput.get(3), TEST_EPS);
375     }
376 
377     @Test
378     void testRegionBSPTree3DExample() {
379         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
380 
381         // create the faces of a pyramid with a square base and its apex pointing along the
382         // positive z axis
383         final Vector3D[] vertices = {
384             Vector3D.Unit.PLUS_Z,
385             Vector3D.of(0.5, 0.5, 0.0),
386             Vector3D.of(0.5, -0.5, 0.0),
387             Vector3D.of(-0.5, -0.5, 0.0),
388             Vector3D.of(-0.5, 0.5, 0.0)
389         };
390 
391         final int[][] faceIndices = {
392             {1, 0, 2},
393             {2, 0, 3},
394             {3, 0, 4},
395             {4, 0, 1},
396             {1, 2, 3, 4}
397         };
398 
399         // convert the vertices and faces to convex polygons and use to construct a BSP tree
400         final List<ConvexPolygon3D> faces = Planes.indexedConvexPolygons(vertices, faceIndices, precision);
401         final RegionBSPTree3D tree = RegionBSPTree3D.from(faces);
402 
403         // split the region through its centroid along a diagonal of the base
404         final Plane cutter = Planes.fromPointAndNormal(tree.getCentroid(), Vector3D.Unit.from(1, 1, 0), precision);
405         final Split<RegionBSPTree3D> split = tree.split(cutter);
406 
407         // compute some properties for the minus side of the split and convert back to hyperplane subsets
408         // (ie, boundary facets)
409         final RegionBSPTree3D minus = split.getMinus();
410 
411         final double minusSize = minus.getSize(); // 1/6
412         final List<PlaneConvexSubset> minusBoundaries = minus.getBoundaries(); // size = 4
413 
414         // ---------------------
415         Assertions.assertEquals(1.0 / 6.0, minusSize, TEST_EPS);
416         Assertions.assertEquals(4, minusBoundaries.size());
417     }
418 
419     @Test
420     void testLinecast3DExample() {
421         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);
422 
423         // create a BSP tree representing an axis-aligned cube with corners at (0, 0, 0) and (1, 1, 1)
424         final RegionBSPTree3D tree = Parallelepiped.axisAligned(Vector3D.ZERO, Vector3D.of(1, 1, 1), precision)
425                 .toTree();
426 
427         // create a ray starting on one side of the cube and pointing through its center
428         final Ray3D ray = Lines3D.rayFromPointAndDirection(Vector3D.of(0.5, 0.5, -1), Vector3D.Unit.PLUS_Z, precision);
429 
430         // perform the linecast
431         final List<LinecastPoint3D> pts = tree.linecast(ray);
432 
433         // check the results
434         final int intersectionCount = pts.size(); // intersectionCount = 2
435         final Vector3D intersection = pts.get(0).getPoint(); // (0.5, 0.5, 0.0)
436         final Vector3D normal = pts.get(0).getNormal(); // (0.0, 0.0, -1.0)
437 
438         // ----------------
439         Assertions.assertEquals(2, intersectionCount);
440 
441         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0), intersection, TEST_EPS);
442         EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), normal, TEST_EPS);
443     }
444 }