DocumentationExamplesTest.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.geometry.euclidean;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.euclidean.oned.Interval;
import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D;
import org.apache.commons.geometry.euclidean.oned.Vector1D;
import org.apache.commons.geometry.euclidean.threed.AffineTransformMatrix3D;
import org.apache.commons.geometry.euclidean.threed.ConvexPolygon3D;
import org.apache.commons.geometry.euclidean.threed.Plane;
import org.apache.commons.geometry.euclidean.threed.PlaneConvexSubset;
import org.apache.commons.geometry.euclidean.threed.Planes;
import org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
import org.apache.commons.geometry.euclidean.threed.line.Line3D;
import org.apache.commons.geometry.euclidean.threed.line.LinecastPoint3D;
import org.apache.commons.geometry.euclidean.threed.line.Lines3D;
import org.apache.commons.geometry.euclidean.threed.line.Ray3D;
import org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation;
import org.apache.commons.geometry.euclidean.threed.shape.Parallelepiped;
import org.apache.commons.geometry.euclidean.twod.AffineTransformMatrix2D;
import org.apache.commons.geometry.euclidean.twod.Line;
import org.apache.commons.geometry.euclidean.twod.LinecastPoint2D;
import org.apache.commons.geometry.euclidean.twod.Lines;
import org.apache.commons.geometry.euclidean.twod.Ray;
import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
import org.apache.commons.geometry.euclidean.twod.Segment;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.geometry.euclidean.twod.path.LinePath;
import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
import org.apache.commons.numbers.angle.PlaneAngleRadians;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/** This class contains code listed as examples in the user guide and other documentation.
 * If any portion of this code changes, the corresponding examples in the documentation <em>must</em> be updated.
 */
public class DocumentationExamplesTest {

    private static final double TEST_EPS = 1e-12;

    @Test
    public void testPrecisionContextExample() {
        // create a precision context with an epsilon (aka, tolerance) value of 1e-3
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-3);

        // test for equality using the eq() method
        precision.eq(1.0009, 1.0); // true; difference is less than epsilon
        precision.eq(1.002, 1.0); // false; difference is greater than epsilon

        // compare
        precision.compare(1.0009, 1.0); // 0
        precision.compare(1.002, 1.0); // 1

        // ------------------
        Assertions.assertTrue(precision.eq(1.0009, 1.0));
        Assertions.assertFalse(precision.eq(1.002, 1.0));

        Assertions.assertEquals(0, precision.compare(1.0009, 1.0));
        Assertions.assertEquals(1, precision.compare(1.002, 1.0));
    }

    @Test
    public void testEqualsVsEqExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        final Vector2D v1 = Vector2D.of(1, 1); // (1.0, 1.0)
        final Vector2D v2 = Vector2D.parse("(1, 1)"); // (1.0, 1.0)

        final Vector2D v3 = Vector2D.of(Math.sqrt(2), 0).transform(
                AffineTransformMatrix2D.createRotation(0.25 * Math.PI)); // (1.0000000000000002, 1.0)

        v1.equals(v2); // true - exactly equal
        v1.equals(v3); // false - not exactly equal

        v1.eq(v3, precision); // true - approximately equal according to the given precision context

        // ---------------------
        Assertions.assertEquals(v1, v2);
        Assertions.assertNotEquals(v1, v3);
        Assertions.assertTrue(v1.eq(v3, precision));
    }

    @Test
    public void testManualBSPTreeExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create a tree representing an empty space (nothing "inside")
        final RegionBSPTree2D tree = RegionBSPTree2D.empty();

        // insert a "structural" cut, meaning a cut whose children have the same inside/outside
        // status as the parent; this will help keep our tree balanced and limit its overall height
        tree.getRoot().insertCut(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.of(1, 1), precision),
                RegionCutRule.INHERIT);

        RegionBSPTree2D.RegionNode2D currentNode;

        // insert on the plus side of the structural diagonal cut
        currentNode = tree.getRoot().getPlus();

        currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision));
        currentNode = currentNode.getMinus();

        currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.of(1, 0), Vector2D.Unit.PLUS_Y, precision));

        // insert on the plus side of the structural diagonal cut
        currentNode = tree.getRoot().getMinus();

        currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X, precision));
        currentNode = currentNode.getMinus();

        currentNode.insertCut(Lines.fromPointAndDirection(Vector2D.of(0, 1), Vector2D.Unit.MINUS_Y, precision));

        // compute some tree properties
        final int count = tree.count(); // number of nodes in the tree = 11
        final int height = tree.height(); // height of the tree = 3
        final double size = tree.getSize(); // size of the region = 1
        final Vector2D centroid = tree.getCentroid(); // region centroid = (0.5, 0.5)

        // ---------
        Assertions.assertEquals(1, size, TEST_EPS);
        Assertions.assertEquals(11, count);
        Assertions.assertEquals(3, height);
        EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), centroid, TEST_EPS);
    }

    @Test
    public void testHyperplaneSubsetBSPTreeExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create a tree representing an empty space (nothing "inside")
        final RegionBSPTree2D tree = RegionBSPTree2D.empty();

        // insert the hyperplane subsets
        tree.insert(Arrays.asList(
                    Lines.segmentFromPoints(Vector2D.ZERO, Vector2D.of(1, 0), precision),
                    Lines.segmentFromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), precision),
                    Lines.segmentFromPoints(Vector2D.of(1, 1), Vector2D.of(0, 1), precision),
                    Lines.segmentFromPoints(Vector2D.of(0, 1), Vector2D.ZERO, precision)
                ));

        // compute some tree properties
        final int count = tree.count(); // number of nodes in the tree = 9
        final int height = tree.height(); // height of the tree = 4
        final double size = tree.getSize(); // size of the region = 1
        final Vector2D centroid = tree.getCentroid(); // region centroid = (0.5, 0.5)

        // ---------
        Assertions.assertEquals(1, size, TEST_EPS);
        Assertions.assertEquals(9, count);
        Assertions.assertEquals(4, height);
        EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), centroid, TEST_EPS);
    }

    @Test
    public void testIntervalExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create a closed interval and a half-open interval with a min but no max
        final Interval closed = Interval.of(1, 2, precision);
        final Interval halfOpen = Interval.min(1, precision);

        // classify some points against the intervals
        closed.contains(0.0); // false
        halfOpen.contains(Vector1D.ZERO); // false

        final RegionLocation closedOneLoc = closed.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY
        final RegionLocation halfOpenOneLoc = halfOpen.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY

        final RegionLocation closedThreeLoc = closed.classify(3.0); // RegionLocation.OUTSIDE
        final RegionLocation halfOpenThreeLoc = halfOpen.classify(3.0); // RegionLocation.INSIDE

        // --------------------
        Assertions.assertFalse(closed.contains(0));
        Assertions.assertFalse(halfOpen.contains(0));

        Assertions.assertEquals(RegionLocation.BOUNDARY, closedOneLoc);
        Assertions.assertEquals(RegionLocation.BOUNDARY, halfOpenOneLoc);

        Assertions.assertEquals(RegionLocation.OUTSIDE, closedThreeLoc);
        Assertions.assertEquals(RegionLocation.INSIDE, halfOpenThreeLoc);
    }

    @Test
    public void testRegionBSPTree1DExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // build a bsp tree from the union of several intervals
        final RegionBSPTree1D tree = RegionBSPTree1D.empty();

        tree.add(Interval.of(1, 2, precision));
        tree.add(Interval.of(1.5, 3, precision));
        tree.add(Interval.of(-1, -2, precision));

        // compute the size;
        final double size = tree.getSize(); // 3

        // convert back to intervals
        final List<Interval> intervals = tree.toIntervals(); // size = 2

        // ----------------------
        Assertions.assertEquals(3, size, TEST_EPS);
        Assertions.assertEquals(2, intervals.size());
    }

    @Test
    public void testLineIntersectionExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create some lines
        final Line a = Lines.fromPoints(Vector2D.ZERO, Vector2D.of(2, 2), precision);
        final Line b = Lines.fromPointAndDirection(Vector2D.of(1, -1), Vector2D.Unit.PLUS_Y, precision);

        // compute the intersection and angles
        final Vector2D intersection = a.intersection(b); // (1, 1)
        final double angleAtoB = a.angle(b); // pi/4
        final double angleBtoA = b.angle(a); // -pi/4

        // ----------------------------
        EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), intersection, TEST_EPS);
        Assertions.assertEquals(0.25 * Math.PI, angleAtoB, TEST_EPS);
        Assertions.assertEquals(-0.25 * Math.PI, angleBtoA, TEST_EPS);
    }

    @Test
    public void testLineSegmentIntersectionExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create some line segments
        final Segment segmentA = Lines.segmentFromPoints(Vector2D.of(3, -1), Vector2D.of(3, 1), precision);
        final Segment segmentB = Lines.segmentFromPoints(Vector2D.of(-3, -1), Vector2D.of(-3, 1), precision);

        // create a ray to intersect against the segments
        final Ray ray = Lines.rayFromPointAndDirection(Vector2D.of(2, 0), Vector2D.Unit.PLUS_X, precision);

        // compute some intersections
        final Vector2D aIntersection = segmentA.intersection(ray); // (3, 0)
        final Vector2D bIntersection = segmentB.intersection(ray); // null - no intersection

        // ----------------------------
        EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 0), aIntersection, TEST_EPS);
        Assertions.assertNull(bIntersection);
    }

    @Test
    public void testRegionBSPTree2DExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create a connected sequence of line segments forming the unit square
        final LinePath path = LinePath.builder(precision)
                .append(Vector2D.ZERO)
                .append(Vector2D.Unit.PLUS_X)
                .append(Vector2D.of(1, 1))
                .append(Vector2D.Unit.PLUS_Y)
                .build(true); // build the path, ending it with the starting point

        // convert to a tree
        final RegionBSPTree2D tree = path.toTree();

        // copy the tree
        final RegionBSPTree2D copy = tree.copy();

        // translate the copy
        copy.transform(AffineTransformMatrix2D.createTranslation(Vector2D.of(0.5, 0.5)));

        // compute the union of the regions, storing the result back into the
        // first tree
        tree.union(copy);

        // compute some properties
        final double size = tree.getSize(); // 1.75
        final Vector2D centroid = tree.getCentroid(); // (0.75, 0.75)

        // get a line path representing the boundary; a list is returned since trees
        // can represent disjoint regions
        final List<LinePath> boundaries = tree.getBoundaryPaths(); // size = 1

        // ----------------
        Assertions.assertEquals(1.75, size, TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.75, 0.75), centroid, TEST_EPS);
        Assertions.assertEquals(1, boundaries.size());
    }

    @Test
    public void testLinecast2DExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        final Parallelogram box = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(2, 1), precision);

        final LinecastPoint2D pt = box.linecastFirst(
                Lines.segmentFromPoints(Vector2D.of(1, 0.5), Vector2D.of(4, 0.5), precision));

        final Vector2D intersection = pt.getPoint(); // (2.0, 0.5)
        final Vector2D normal = pt.getNormal(); // (1.0, 0.0)

        // ----------------
        EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(2, 0.5), intersection, TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), normal, TEST_EPS);
    }

    @Test
    public void testPlaneIntersectionExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create two planes
        final Plane a = Planes.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z, precision);
        final Plane b = Planes.fromPointAndPlaneVectors(Vector3D.of(1, 1, 1),
                Vector3D.Unit.PLUS_Z, Vector3D.Unit.MINUS_Y, precision);

        // compute the intersection
        final Line3D line = a.intersection(b);

        final Vector3D dir = line.getDirection(); // (0, 1, 0)

        // ----------------------
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_Y, dir, TEST_EPS);
    }

    @Test
    public void testTransform3DExample() {
        final List<Vector3D> inputPts = Arrays.asList(
                Vector3D.ZERO,
                Vector3D.Unit.PLUS_X,
                Vector3D.Unit.PLUS_Y,
                Vector3D.Unit.PLUS_Z);

        // create a 4x4 transform matrix and quaternion rotation
        final AffineTransformMatrix3D mat = AffineTransformMatrix3D.createScale(2)
                .translate(Vector3D.of(1, 2, 3));

        final QuaternionRotation rot = QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Z,
                PlaneAngleRadians.PI_OVER_TWO);

        // transform the input points
        final List<Vector3D> matOutput = inputPts.stream()
                .map(mat)
                .collect(Collectors.toList()); // [(1, 2, 3), (3, 2, 3), (1, 4, 3), (1, 2, 5)]

        final List<Vector3D> rotOutput = inputPts.stream()
                .map(rot)
                .collect(Collectors.toList()); // [(0, 0, 0), (0, 1, 0), (-1, 0, 0), (0, 0, 1)]

        // ----------------
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 3), matOutput.get(0), TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(3, 2, 3), matOutput.get(1), TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 4, 3), matOutput.get(2), TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 2, 5), matOutput.get(3), TEST_EPS);

        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 0), rotOutput.get(0), TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0), rotOutput.get(1), TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0), rotOutput.get(2), TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1), rotOutput.get(3), TEST_EPS);
    }

    @Test
    public void testRegionBSPTree3DExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create the faces of a pyramid with a square base and its apex pointing along the
        // positive z axis
        final Vector3D[] vertices = {
            Vector3D.Unit.PLUS_Z,
            Vector3D.of(0.5, 0.5, 0.0),
            Vector3D.of(0.5, -0.5, 0.0),
            Vector3D.of(-0.5, -0.5, 0.0),
            Vector3D.of(-0.5, 0.5, 0.0)
        };

        final int[][] faceIndices = {
            {1, 0, 2},
            {2, 0, 3},
            {3, 0, 4},
            {4, 0, 1},
            {1, 2, 3, 4}
        };

        // convert the vertices and faces to convex polygons and use to construct a BSP tree
        final List<ConvexPolygon3D> faces = Planes.indexedConvexPolygons(vertices, faceIndices, precision);
        final RegionBSPTree3D tree = RegionBSPTree3D.from(faces);

        // split the region through its centroid along a diagonal of the base
        final Plane cutter = Planes.fromPointAndNormal(tree.getCentroid(), Vector3D.Unit.from(1, 1, 0), precision);
        final Split<RegionBSPTree3D> split = tree.split(cutter);

        // compute some properties for the minus side of the split and convert back to hyperplane subsets
        // (ie, boundary facets)
        final RegionBSPTree3D minus = split.getMinus();

        final double minusSize = minus.getSize(); // 1/6
        final List<PlaneConvexSubset> minusBoundaries = minus.getBoundaries(); // size = 4

        // ---------------------
        Assertions.assertEquals(1.0 / 6.0, minusSize, TEST_EPS);
        Assertions.assertEquals(4, minusBoundaries.size());
    }

    @Test
    public void testLinecast3DExample() {
        final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

        // create a BSP tree representing an axis-aligned cube with corners at (0, 0, 0) and (1, 1, 1)
        final RegionBSPTree3D tree = Parallelepiped.axisAligned(Vector3D.ZERO, Vector3D.of(1, 1, 1), precision)
                .toTree();

        // create a ray starting on one side of the cube and pointing through its center
        final Ray3D ray = Lines3D.rayFromPointAndDirection(Vector3D.of(0.5, 0.5, -1), Vector3D.Unit.PLUS_Z, precision);

        // perform the linecast
        final List<LinecastPoint3D> pts = tree.linecast(ray);

        // check the results
        final int intersectionCount = pts.size(); // intersectionCount = 2
        final Vector3D intersection = pts.get(0).getPoint(); // (0.5, 0.5, 0.0)
        final Vector3D normal = pts.get(0).getNormal(); // (0.0, 0.0, -1.0)

        // ----------------
        Assertions.assertEquals(2, intersectionCount);

        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0), intersection, TEST_EPS);
        EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1), normal, TEST_EPS);
    }
}