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 }