You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2019/12/23 00:30:28 UTC
[commons-geometry] 01/06: GEOMETRY-73: adding user guide
This is an automated email from the ASF dual-hosted git repository.
erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit d58d10378dc59ff09e68b4b238200c7d47adfc92
Author: Matt Juntunen <ma...@hotmail.com>
AuthorDate: Sat Dec 21 23:55:40 2019 -0500
GEOMETRY-73: adding user guide
---
.../apache/commons/geometry/core/Transform.java | 9 +-
.../geometry/core/internal/package-info.java | 2 +-
.../apache/commons/geometry/core/package-info.java | 5 +-
.../geometry/core/partitioning/Hyperplane.java | 19 +-
.../geometry/core/partitioning/Splittable.java | 2 +-
.../geometry/core/partitioning/SubHyperplane.java | 15 +-
.../geometry/core/partitioning/package-info.java | 12 +
.../commons/geometry/euclidean/package-info.java | 2 +-
.../euclidean/DocumentationExamplesTest.java | 384 ++++++++
.../spherical/DocumentationExamplesTest.java | 133 +++
src/site/apt/userguide/geometry.apt | 24 -
src/site/site.xml | 33 +-
src/site/xdoc/index.xml | 37 +-
src/site/xdoc/userguide/index.xml | 973 ++++++++++++++++++++-
14 files changed, 1584 insertions(+), 66 deletions(-)
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/Transform.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/Transform.java
index 7047fab..0dc1d12 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/Transform.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/Transform.java
@@ -27,10 +27,11 @@ import java.util.function.UnaryOperator;
* requirements outlined above. These are:
* <ol>
* <li>The transform must be <a href="https://en.wikipedia.org/wiki/Affine_transformation">affine</a>.
- * This means that points and parallel lines must be preserved by the transformation. For example,
- * a translation or rotation in Euclidean 3D space meets this requirement because a mapping exists for
- * all points and lines that are parallel before the transform remain parallel afterwards.
- * However, a projective transform that causes parallel lines to meet at a point in infinity does not.
+ * In basic terms, this means that the transform must retain the "straightness" and "parallelness" of
+ * lines and planes (or whatever is an equivalent concept for the space). For example, a translation or
+ * rotation in Euclidean 3D space meets this requirement because all lines that are parallel before the
+ * transform remain parallel afterwards. However, a projective transform that causes previously parallel
+ * lines to meet at a single point does not.
* </li>
* <li>The transform must be <em>inversible</em>. An inverse transform must exist that will return
* the original point if given the transformed point. In other words, for a transform {@code t}, there
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/package-info.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/package-info.java
index 1e4be0a..3f190f7 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/package-info.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/internal/package-info.java
@@ -17,7 +17,7 @@
/**
*
* <p>
- * This package contains geometry utilities intended for internal use only.
+ * This package contains utilities intended for internal use only.
* No guarantees are made for the stability of the contained APIs.
* </p>
*/
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/package-info.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/package-info.java
index a45caa8..8c476bf 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/package-info.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/package-info.java
@@ -17,8 +17,9 @@
/**
*
* <p>
- * This package is the top level package for geometry. It provides only a few interfaces
- * related to vectorial/affine spaces that are implemented in sub-packages.
+ * This package contains the core interfaces and classes for <em>commons-geometry</em>.
+ * The majority of the interfaces here are intended for internal implementation
+ * only.
* </p>
*
*/
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Hyperplane.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Hyperplane.java
index d7bd09f..6ae7ff1 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Hyperplane.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Hyperplane.java
@@ -19,9 +19,24 @@ package org.apache.commons.geometry.core.partitioning;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.Transform;
-/** Interface representing a hyperplane, which is a subspace of degree
- * one less than the space it is embedded in.
+/** Interface representing a hyperplane, which is a subspace of dimension
+ * one less than its surrounding space. (A hyperplane in Euclidean 3D space,
+ * for example, is a 2 dimensional plane.)
+ *
+ * <p>
+ * Hyperplanes partition their surrounding space into 3 distinct sets: (1) points
+ * lying on one side of the hyperplane, (2) points lying on the opposite side, and
+ * (3) points lying on the hyperplane itself. One side of the hyperplane is labeled
+ * as the <em>plus</em> side and the other as the <em>minus</em> side. The
+ * {@link #offset(Point) offset} of a point in relation to a hyperplane is the distance
+ * from the point to the hyperplane combined with the sign of the side that the point
+ * lies on: points lying on the plus side of the hyperplane have a positive offsets,
+ * those on the minus side have a negative offset, and those lying directly on the
+ * hyperplane have an offset of zero.
+ *
* @param <P> Point implementation type
+ * @see HyperplaneLocation
+ * @see SubHyperplane
*/
public interface Hyperplane<P extends Point<P>> {
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Splittable.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Splittable.java
index 60cef06..a2670a6 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Splittable.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/Splittable.java
@@ -18,7 +18,7 @@ package org.apache.commons.geometry.core.partitioning;
import org.apache.commons.geometry.core.Point;
-/** Interface representing objects that can be split by hyperplanes.
+/** Interface representing objects that can be split by {@link Hyperplane}s.
* @param <P> Point implementation type
* @param <S> Split type
*/
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/SubHyperplane.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/SubHyperplane.java
index 887f2a8..74a4169 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/SubHyperplane.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/SubHyperplane.java
@@ -22,10 +22,19 @@ import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
-/** Interface representing subhyperplanes, which are regions
- * embedded in a hyperplane.
-
+/** Interface representing subhyperplanes.
+ *
+ * <p>
+ * A subhyperplane is a portion of a hyperplane. For example, the triangular
+ * facet of a polyhedron in Euclidean 3D space is a subhyperplane because
+ * its interior represents a subset of the plane defined by the three points.
+ * While hyperplanes always extend through the entire space that surrounds
+ * them, subhyperplanes have no such restriction: they can represent a single,
+ * small portion of the hyperplane (as in the example above); multiple, disjoint
+ * regions; or the entire hyperplane.
+ *
* @param <P> Point implementation type
+ * @see Hyperplane
*/
public interface SubHyperplane<P extends Point<P>> extends Splittable<P, SubHyperplane<P>> {
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/package-info.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/package-info.java
index b0e4967..1f75da4 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/package-info.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/package-info.java
@@ -19,5 +19,17 @@
* <p>
* This package contains code related to partitioning of spaces by hyperplanes.
* </p>
+ *
+ * <p>
+ * A hyperplane is a subspace of dimension one less than its surrounding space.
+ * In Euclidean 3D space, the hyperplanes are 2-dimensional planes, while in
+ * Euclidean 2D space, the hyperplanes are 1-dimensional lines. Hyperplanes have
+ * the property that they partition the entire surrounding space into 3 distinct sets
+ * of points: (1) points lying on one side of the hyperplane, (2) points lying on the
+ * opposite side, and (3) points lying directly on the hyperplane itself. In order
+ * to differentiate between the two sides of the hyperplane, one side is labeled
+ * as the <em>plus</em> side and the other as the <em>minus</em> side. The plus side
+ * of a Euclidean plane, for example, lies in the direction of the plane normal.
+ * </p>
*/
package org.apache.commons.geometry.core.partitioning;
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/package-info.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/package-info.java
index 948b851..85798a9 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/package-info.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/package-info.java
@@ -26,7 +26,7 @@
* space is an <a href="https://en.wikipedia.org/wiki/Affine_space">affine
* space</a>, meaning that it consists of points and displacement vectors
* representing translations between points. Distances between points are given
- * by the formula <code>√(A - B)<sup>2</sup></code>, which is also known
+ * by the formula \( \sqrt{(A - B)^2} \), which is also known
* as the <em>Euclidean norm</em>.
* </p>
*
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
new file mode 100644
index 0000000..f77ba4d
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
@@ -0,0 +1,384 @@
+/*
+ * 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.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.ConvexSubPlane;
+import org.apache.commons.geometry.euclidean.threed.Line3D;
+import org.apache.commons.geometry.euclidean.threed.Plane;
+import org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D;
+import org.apache.commons.geometry.euclidean.threed.Transform3D;
+import org.apache.commons.geometry.euclidean.threed.Vector3D;
+import org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation;
+import org.apache.commons.geometry.euclidean.twod.FunctionTransform2D;
+import org.apache.commons.geometry.euclidean.twod.Line;
+import org.apache.commons.geometry.euclidean.twod.Polyline;
+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.numbers.angle.PlaneAngleRadians;
+import org.junit.Assert;
+import org.junit.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 testIndexPageExample() {
+ // construct a precision context to handle floating-point comparisons
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create a binary space partitioning tree representing the unit cube
+ // centered on the origin
+ RegionBSPTree3D region = RegionBSPTree3D.builder(precision)
+ .addRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5))
+ .build();
+
+ // create a rotated copy of the region
+ Transform3D rotation = QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Z, 0.25 * Math.PI);
+
+ RegionBSPTree3D copy = region.copy();
+ copy.transform(rotation);
+
+ // compute the intersection of the regions, storing the result back into the caller
+ // (the result could also have been placed into a third region)
+ region.intersection(copy);
+
+ // compute some properties of the intersection region
+ double size = region.getSize(); // 0.8284271247461903
+ Vector3D center = region.getBarycenter(); // (0, 0, 0)
+
+ // -----------
+ Assert.assertEquals(0.8284271247461903, size, TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.ZERO, center, TEST_EPS);
+ }
+
+ @Test
+ public void testPrecisionContextExample() {
+ // create a precision context with an epsilon (aka, tolerance) value of 1e-3
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-3);
+
+ // test for equality
+ 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
+
+ // ------------------
+ Assert.assertTrue(precision.eq(1.0009, 1.0));
+ Assert.assertFalse(precision.eq(1.002, 1.0));
+
+ Assert.assertEquals(0, precision.compare(1.0009, 1.0));
+ Assert.assertEquals(1, precision.compare(1.002, 1.0));
+ }
+
+ @Test
+ public void testManualBSPTreeExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create a tree representing an empty space (nothing "inside")
+ RegionBSPTree2D tree = RegionBSPTree2D.empty();
+
+ // get the root node
+ RegionBSPTree2D.RegionNode2D currentNode = tree.getRoot();
+
+ // cut each minus node with the next hyperplane in the shape
+ currentNode.insertCut(Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision));
+ currentNode = currentNode.getMinus();
+
+ currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_X, Vector2D.of(-1, 1), precision));
+ currentNode = currentNode.getMinus();
+
+ currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_Y, Vector2D.Unit.MINUS_Y, precision));
+ currentNode = currentNode.getMinus();
+
+ currentNode.isInside(); // true (node is inside)
+ currentNode.getParent().getPlus().isInside(); // false (sibling node is outside)
+ tree.getSize(); // size of the region = 0.5
+ tree.count(); // number of nodes in the tree = 7
+
+ // ---------
+ Assert.assertTrue(currentNode.isInside());
+ Assert.assertFalse(currentNode.getParent().getPlus().isInside());
+ Assert.assertEquals(0.5, tree.getSize(), TEST_EPS);
+ Assert.assertEquals(7, tree.count());
+ }
+
+ @Test
+ public void testSubHyperplaneBSPTreeExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create a tree representing an empty space (nothing "inside")
+ RegionBSPTree2D tree = RegionBSPTree2D.empty();
+
+ // insert the subhyperplanes
+ tree.insert(Arrays.asList(
+ Segment.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision),
+ Segment.fromPoints(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y, precision),
+ Segment.fromPoints(Vector2D.Unit.PLUS_Y, Vector2D.ZERO, precision)
+ ));
+
+ tree.getSize(); // size of the region = 0.5
+ tree.count(); // number of nodes in the tree = 7
+
+ // ---------
+ Assert.assertEquals(0.5, tree.getSize(), TEST_EPS);
+ Assert.assertEquals(7, tree.count());
+ }
+
+ @Test
+ public void testIntervalExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create a closed interval and a half-open interval with a min but no max
+ Interval closed = Interval.of(1, 2, precision);
+ Interval halfOpen = Interval.min(1, precision);
+
+ // classify some points against the intervals
+ closed.contains(0.0); // false
+ halfOpen.contains(Vector1D.ZERO); // false
+
+ RegionLocation closedOneLoc = closed.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY
+ RegionLocation halfOpenOneLoc = halfOpen.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY
+
+ RegionLocation closedThreeLoc = closed.classify(3.0); // RegionLocation.OUTSIDE
+ RegionLocation halfOpenThreeLoc = halfOpen.classify(3.0); // RegionLocation.INSIDE
+
+ // --------------------
+ Assert.assertFalse(closed.contains(0));
+ Assert.assertFalse(halfOpen.contains(0));
+
+ Assert.assertEquals(RegionLocation.BOUNDARY, closedOneLoc);
+ Assert.assertEquals(RegionLocation.BOUNDARY, halfOpenOneLoc);
+
+ Assert.assertEquals(RegionLocation.OUTSIDE, closedThreeLoc);
+ Assert.assertEquals(RegionLocation.INSIDE, halfOpenThreeLoc);
+ }
+
+ @Test
+ public void testRegionBSPTree1DExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // build a bsp tree from the union of several intervals
+ 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;
+ double size = tree.getSize(); // 3
+
+ // convert back to intervals
+ List<Interval> intervals = tree.toIntervals(); // size = 2
+
+ // ----------------------
+ Assert.assertEquals(3, size, TEST_EPS);
+ Assert.assertEquals(2, intervals.size());
+ }
+
+ @Test
+ public void testLineIntersectionExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create some lines
+ Line a = Line.fromPoints(Vector2D.ZERO, Vector2D.of(2, 2), precision);
+ Line b = Line.fromPointAndDirection(Vector2D.of(1, -1), Vector2D.Unit.PLUS_Y, precision);
+
+ // compute the intersection and angles
+ Vector2D intersection = a.intersection(b); // (1, 1)
+ double angleAtoB = a.angle(b); // pi/4
+ double angleBtoA = b.angle(a); // -pi/4
+
+ // ----------------------------
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), intersection, TEST_EPS);
+ Assert.assertEquals(0.25 * Math.PI, angleAtoB, TEST_EPS);
+ Assert.assertEquals(-0.25 * Math.PI, angleBtoA, TEST_EPS);
+ }
+
+ @Test
+ public void testLineSegmentIntersectionExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create some line segments
+ Segment closedPosX = Segment.fromPoints(Vector2D.of(3, -1), Vector2D.of(3, 1), precision);
+ Segment closedNegX = Segment.fromPoints(Vector2D.of(-3, -1), Vector2D.of(-3, 1), precision);
+ Segment halfOpen = Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision)
+ .segmentFrom(Vector2D.of(2, 0));
+
+ // compute some intersections
+ Vector2D posXIntersection = closedPosX.intersection(halfOpen); // (3, 0)
+ Vector2D negXIntersection = closedNegX.intersection(halfOpen); // null - no intersection
+
+ // ----------------------------
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 0), posXIntersection, TEST_EPS);
+ Assert.assertNull(negXIntersection);
+ }
+
+ @Test
+ public void testRegionBSPTree2DExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create a connected sequence of line segments forming the unit square
+ Polyline path = Polyline.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
+ RegionBSPTree2D tree = path.toTree();
+
+ // copy the tree
+ RegionBSPTree2D copy = tree.copy();
+
+ // translate the copy
+ Vector2D translation = Vector2D.of(0.5, 0.5);
+ copy.transform(FunctionTransform2D.from(v -> v.add(translation)));
+
+ // compute the union of the regions, storing the result back into the
+ // first tree
+ tree.union(copy);
+
+ // compute some properties
+ double size = tree.getSize(); // 1.75
+ Vector2D center = tree.getBarycenter(); // (0.75, 0.75)
+
+ // get a polyline representing the boundary; a list is returned since trees
+ // can represent disjoint regions
+ List<Polyline> boundaries = tree.getBoundaryPaths(); // size = 1
+
+ // ----------------
+ Assert.assertEquals(1.75, size, TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.75, 0.75), center, TEST_EPS);
+ Assert.assertEquals(1, boundaries.size());
+ }
+
+ @Test
+ public void testPlaneIntersectionExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create two planes
+ Plane a = Plane.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z, precision);
+ Plane b = Plane.fromPointAndPlaneVectors(Vector3D.of(1, 1, 1),
+ Vector3D.Unit.PLUS_Z, Vector3D.Unit.MINUS_Y, precision);
+
+ // compute the intersection
+ Line3D line = a.intersection(b);
+
+ Vector3D dir = line.getDirection(); // (0, 1, 0)
+
+ // ----------------------
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_Y, dir, TEST_EPS);
+ }
+
+ @Test
+ public void testTransform3DExample() {
+ 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
+ AffineTransformMatrix3D mat = AffineTransformMatrix3D.createScale(2)
+ .translate(Vector3D.of(1, 2, 3));
+
+ QuaternionRotation rot = QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Z,
+ PlaneAngleRadians.PI_OVER_TWO);
+
+ // transform the input points
+ List<Vector3D> matOutput = inputPts.stream()
+ .map(mat)
+ .collect(Collectors.toList()); // [(1, 2, 3), (3, 2, 3), (1, 4, 3), (1, 2, 5)]
+
+ 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() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create the faces of a pyrmaid with a square base and its apex pointing along the
+ // positive z axis
+ Vector3D a1 = Vector3D.Unit.PLUS_Z;
+ Vector3D b1 = Vector3D.of(0.5, 0.5, 0.0);
+ Vector3D b2 = Vector3D.of(0.5, -0.5, 0.0);
+ Vector3D b3 = Vector3D.of(-0.5, -0.5, 0.0);
+ Vector3D b4 = Vector3D.of(-0.5, 0.5, 0.0);
+
+ Vector3D[][] faces = {
+ {b1, a1, b2},
+ {b2, a1, b3},
+ {b3, a1, b4},
+ {b4, a1, b1},
+ {b1, b2, b3, b4}
+ };
+
+ // convert the faces to convex sub planes and insert into a bsp tree
+ RegionBSPTree3D tree = RegionBSPTree3D.empty();
+ Arrays.stream(faces)
+ .map(vertices -> ConvexSubPlane.fromVertexLoop(Arrays.asList(vertices), precision))
+ .forEach(tree::insert);
+
+ // split the region through its barycenter along a diagonal of the base
+ Plane cutter = Plane.fromPointAndNormal(tree.getBarycenter(), Vector3D.Unit.from(1, 1, 0), precision);
+ Split<RegionBSPTree3D> split = tree.split(cutter);
+
+ // compute some properties for the minus side of the split and convert back to subhyperplanes
+ // (ie, facets)
+ RegionBSPTree3D minus = split.getMinus();
+
+ double minusSize = minus.getSize(); // 1/6
+ List<ConvexSubPlane> minusFacets = minus.getBoundaries(); // size = 4
+
+ // ---------------------
+ Assert.assertEquals(1.0 / 6.0, minusSize, TEST_EPS);
+ Assert.assertEquals(4, minusFacets.size());
+ }
+}
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/DocumentationExamplesTest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/DocumentationExamplesTest.java
new file mode 100644
index 0000000..70a165d
--- /dev/null
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/DocumentationExamplesTest.java
@@ -0,0 +1,133 @@
+/*
+ * 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.spherical;
+
+import java.util.List;
+
+import org.apache.commons.geometry.core.RegionLocation;
+import org.apache.commons.geometry.core.partitioning.Split;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.apache.commons.geometry.euclidean.threed.Vector3D;
+import org.apache.commons.geometry.spherical.oned.AngularInterval;
+import org.apache.commons.geometry.spherical.oned.Point1S;
+import org.apache.commons.geometry.spherical.oned.RegionBSPTree1S;
+import org.apache.commons.geometry.spherical.twod.GreatArcPath;
+import org.apache.commons.geometry.spherical.twod.GreatCircle;
+import org.apache.commons.geometry.spherical.twod.Point2S;
+import org.apache.commons.geometry.spherical.twod.RegionBSPTree2S;
+import org.apache.commons.numbers.angle.PlaneAngleRadians;
+import org.junit.Assert;
+import org.junit.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 testAngularIntervalExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create angular intervals of different sizes, one of size pi/2 and one of size 3pi/2
+ AngularInterval a = AngularInterval.of(0, PlaneAngleRadians.PI_OVER_TWO, precision);
+ AngularInterval b = AngularInterval.of(Point1S.PI, Point1S.of(PlaneAngleRadians.PI_OVER_TWO), precision);
+
+ // test some points
+ a.contains(Point1S.of(0.25 * Math.PI)); // true
+ b.contains(Point1S.of(0.25 * Math.PI)); // true
+
+ RegionLocation aLocZero = a.classify(Point1S.ZERO); // RegionLocation.BOUNDARY
+ RegionLocation bLocZero = b.classify(Point1S.ZERO); // RegionLocation.INSIDE
+
+ // -------------------
+ Assert.assertTrue(a.contains(Point1S.of(0.25 * Math.PI)));
+ Assert.assertTrue(b.contains(Point1S.of(0.25 * Math.PI)));
+
+ Assert.assertEquals(RegionLocation.BOUNDARY, aLocZero);
+ Assert.assertEquals(RegionLocation.INSIDE, bLocZero);
+ }
+
+ @Test
+ public void testRegionBSPTree1SExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create a region from the union of multiple angular intervals
+ RegionBSPTree1S tree = RegionBSPTree1S.empty();
+ tree.add(AngularInterval.of(0, 0.25 * Math.PI, precision));
+ tree.add(AngularInterval.of(0.5 * Math.PI, Math.PI, precision));
+ tree.add(AngularInterval.of(0.75 * Math.PI, 1.5 * Math.PI, precision));
+
+ // compute the region size in radians
+ double size = tree.getSize(); // 1.25pi
+
+ // convert back to intervals
+ List<AngularInterval> intervals = tree.toIntervals(); //size = 2
+
+ // ---------------
+ Assert.assertEquals(size, 1.25 * Math.PI, TEST_EPS);
+ Assert.assertEquals(2, intervals.size());
+ }
+
+ @Test
+ public void testGreatCircleIntersectionExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create two non-parallel great arcs
+ GreatCircle a = GreatCircle.fromPoints(Point2S.PLUS_I, Point2S.PLUS_K, precision);
+ GreatCircle b = GreatCircle.fromPole(Vector3D.Unit.PLUS_Z, precision);
+
+ // find the two intersection points of the great circles
+ Point2S ptA = a.intersection(b); //(pi, pi/2)
+ Point2S ptB = ptA.antipodal(); // (0, pi/2)
+
+ // ----------------------
+ SphericalTestUtils.assertPointsEq(Point2S.MINUS_I, ptA, TEST_EPS);
+ SphericalTestUtils.assertPointsEq(Point2S.PLUS_I, ptB, TEST_EPS);
+ }
+
+ @Test
+ public void testRegionBSPTree2SExample() {
+ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+ // create a path outlining a quadrant triangle
+ GreatArcPath path = GreatArcPath.builder(precision)
+ .append(Point2S.PLUS_I)
+ .append(Point2S.PLUS_J)
+ .append(Point2S.PLUS_K)
+ .build(true); // close the path with the starting path
+
+ // convert to a region
+ RegionBSPTree2S tree = path.toTree();
+
+ // split in two through the barycenter
+ GreatCircle splitter = GreatCircle.fromPoints(tree.getBarycenter(), Point2S.PLUS_K, precision);
+ Split<RegionBSPTree2S> split = tree.split(splitter);
+
+ // compute some properties for the minus side
+ RegionBSPTree2S minus = split.getMinus();
+
+ double minusSize = minus.getSize(); // pi/4
+ List<GreatArcPath> minusPaths = minus.getBoundaryPaths(); // size = 1
+
+ // ---------------------
+ Assert.assertEquals(Math.PI / 4, minusSize, TEST_EPS);
+ Assert.assertEquals(1, minusPaths.size());
+ }
+}
diff --git a/src/site/apt/userguide/geometry.apt b/src/site/apt/userguide/geometry.apt
deleted file mode 100644
index 9bc40a8..0000000
--- a/src/site/apt/userguide/geometry.apt
+++ /dev/null
@@ -1,24 +0,0 @@
-~~
-~~ 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.
-~~
-
- -----------------------------
- The Apache Commons Geometry User Guide
- -----------------------------
-
-1. Purpose
-
- <<<Commons Geometry>>> provides ... <TO DO>
diff --git a/src/site/site.xml b/src/site/site.xml
index 17fd332..a404f18 100644
--- a/src/site/site.xml
+++ b/src/site/site.xml
@@ -31,9 +31,29 @@
<body>
<!-- Custom <head> tag with injected XHTML is supported. -->
<head>
- <![CDATA[<script type="text/javascript" id="MathJax-script" async
- src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
- </script>]]>
+ <![CDATA[
+ <script type="text/javascript" id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
+ </script>
+ ]]>
+
+ <!--
+ Workaround to get styles for inline code elements. The current version
+ of the site plugin strips "code" tags out of the content. The following
+ style rules are a copy of the Bootstrap rules for "code" elements but
+ applied to span elements with the class "code".
+ -->
+ <![CDATA[
+ <style type="text/css">
+ .code {
+ font-family: Menlo, Monaco, "Courier New", monospace;
+ color: #d14;
+ padding: 3px 4px;
+ background-color: #f7f7f9;
+ border: 1px solid #e1e1e8;
+ border-radius: 3px;
+ }
+ </style>
+ ]]>
</head>
<menu name="Geometry">
@@ -50,6 +70,11 @@
<menu name="User Guide">
<item name="Contents" href="/userguide/index.html"/>
+ <item name="Overview" href="/userguide/index.html#overview"/>
+ <item name="Concepts" href="/userguide/index.html#concepts"/>
+ <item name="Core Interfaces" href="/userguide/index.html#interfaces"/>
+ <item name="Euclidean Space" href="/userguide/index.html#euclidean"/>
+ <item name="Spherical Space" href="/userguide/index.html#spherical"/>
</menu>
</body>
@@ -72,7 +97,7 @@
<div class="source"><pre> to <div class="source"><pre
class="prettyprint">
-->
- <prettyPrintSourcePreTags>false</prettyPrintSourcePreTags>
+ <prettyPrintSourcePreTags>true</prettyPrintSourcePreTags>
<!-- Add the "linenums" class to the prettyprint enabled source
tags -->
diff --git a/src/site/xdoc/index.xml b/src/site/xdoc/index.xml
index 3702553..fd30b24 100644
--- a/src/site/xdoc/index.xml
+++ b/src/site/xdoc/index.xml
@@ -27,8 +27,43 @@
<section name="Apache Commons Geometry" href="summary">
<p>
- Utilities for geometry.
+ Commons Geometry provides types and utilities for geometric processing. Key features include
</p>
+ <ul>
+ <li>Support for Euclidean space in 1, 2, and 3 dimensions</li>
+ <li>Support for spherical space in 1 and 2 dimensions</li>
+ <li>Support for geometric elements of infinite size</li>
+ <li>Support for boolean operations on regions (union, intersection, difference, xor)</li>
+ <li>Single external dependency (<a href="https://commons.apache.org/proper/commons-numbers/"
+ >commons-numbers</a>)</li>
+ </ul>
+
+ <p>The code below gives a small sample of the API by computing the intersection of cube with a rotated
+ version of itself. See the <a href="userguide/index.html">user guide</a> for more details.
+ </p>
+<source class="prettyprint">// construct a precision context to handle floating-point comparisons
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create a binary space partitioning tree representing the unit cube
+// centered on the origin
+RegionBSPTree3D region = RegionBSPTree3D.builder(precision)
+ .addRect(Vector3D.of(-0.5, -0.5, -0.5), Vector3D.of(0.5, 0.5, 0.5))
+ .build();
+
+// create a rotated copy of the region
+Transform3D rotation = QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Z, 0.25 * Math.PI);
+
+RegionBSPTree3D copy = region.copy();
+copy.transform(rotation);
+
+// compute the intersection of the regions, storing the result back into the caller
+// (the result could also have been placed into a third region)
+region.intersection(copy);
+
+// compute some properties of the intersection region
+double size = region.getSize(); // 0.8284271247461903
+Vector3D center = region.getBarycenter(); // (0, 0, 0)
+</source>
</section>
<section name="Download Apache Commons Geometry">
diff --git a/src/site/xdoc/userguide/index.xml b/src/site/xdoc/userguide/index.xml
index 8bcc3ff..f07d42a 100644
--- a/src/site/xdoc/userguide/index.xml
+++ b/src/site/xdoc/userguide/index.xml
@@ -1,41 +1,968 @@
<?xml version="1.0"?>
-<!--
- 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.
- -->
-
+<!-- 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. -->
+
<?xml-stylesheet type="text/xsl" href="./xdoc.xsl"?>
<document url="index.html">
<properties>
- <title>The Commons Geometry User Guide - Table of Contents</title>
+ <title>User Guide</title>
</properties>
<body>
- <section name="Table of Contents" href="toc">
-
+ <h1>Commons Geometry User Guide</h1>
+
+ <section name="Contents" href="toc">
+ <ul>
+ <li>
+ <a href="#overview">Overview</a>
+ </li>
+ <li>
+ <a href="#concepts">Concepts</a>
+ <ul>
+ <li>
+ <a href="#floating_point">Floating Point Math</a>
+ </li>
+ <li>
+ <a href="#transforms">Transforms</a>
+ </li>
+ <li>
+ <a href="#hyperplanes">Hyperplanes</a>
+ </li>
+ <li>
+ <a href="#bsp_trees">BSP Trees</a>
+ </li>
+ </ul>
+ </li>
+ <li>
+ <a href="#interfaces">Core Interfaces</a>
+ </li>
+ <li>
+ <a href="#euclidean">Euclidean Space</a>
+ <ul>
+ <li>
+ <a href="#euclidean_1d">Euclidean 1D</a>
+ </li>
+ <li>
+ <a href="#euclidean_2d">Euclidean 2D</a>
+ </li>
+ <li>
+ <a href="#euclidean_3d">Euclidean 3D</a>
+ </li>
+ </ul>
+ </li>
+ <li>
+ <a href="#euclidean">Spherical Space</a>
+ <ul>
+ <li>
+ <a href="#spherical_1d">Spherical 1D</a>
+ </li>
+ <li>
+ <a href="#spherical_2d">Spherical 2D</a>
+ </li>
+ </ul>
+ </li>
+ </ul>
+ </section>
+
+ <section name="Overview" id="overview">
+ <p>
+ <em>Commons Geometry</em> provides types and utilities for geometric processing. The code originated in the
+ <span class="code">org.apache.commons.math3.geometry</span> package of the
+ <a class="code" href="https://commons.apache.org/proper/commons-math/">commons-math</a> project
+ but was pulled out into a separate project for better maintainability. It has since undergone numerous
+ improvements, including a major refactor of the core interfaces and classes.
+ </p>
+
+ <p>
+ <em>Commons Geometry</em> is divided into 5 submodules.
+ </p>
<ul>
+ <li>
+ <a class="code" href="../commons-geometry-core/index.html">commons-geometry-core</a> - Provides core interfaces
+ and classes.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/index.html">commons-geometry-euclidean</a> - Provides
+ classes for Euclidean space in 1D, 2D, and 3D.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/index.html">commons-geometry-spherical</a> - Provides
+ classes for Spherical space in 1D and 2D.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-hull/index.html">commons-geometry-hull</a> - Provides implementations
+ of convex hull algorithms.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-enclosing/index.html">commons-geometry-enclosing</a> - Provides implementations
+ of enclosing ball algorithms.
+ </li>
+ </ul>
+ </section>
+
+ <section name="Concepts" id="concepts">
+ <subsection name="Floating Point Math" id="floating_point">
+ <p>
+ All floating point numbers in <em>Commons Geometry</em> are represented using
+ <span class="code">double</span>s.
+ </p>
+ <p>
+ The concept of a <em>precision context</em> is used in order to avoid issues with floating point errors
+ in computations. A precision context is an object that encapsulates floating point comparisons,
+ allowing numbers that may not be exactly equal to be considered equal for the
+ purposes of a computation. This idea is represented in code with the
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/precision/DoublePrecisionContext.html"
+ >DoublePrecisionContext</a> interface. The example below uses an epsilon (tolerance) value to compare
+ numbers for equality.
+ </p>
+ <source>
+// create a precision context with an epsilon (aka, tolerance) value of 1e-3
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-3);
+// test for equality
+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
+ </source>
+ </subsection>
+
+ <subsection name="Transforms" id="transforms">
+ <p>
+ A geometric transform is simply a function that maps points from one set to another. Transforms
+ in <em>Commons Geometry</em> are represented with the
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/Transform.html">Transform</a>
+ interface. Useful implementations of this interface exist for each supported space
+ and dimension, so users should not need to implement their own. However, it is important to know that
+ all implementations (and instances) of this interface <em>must</em> meet the following requirements:
+ </p>
+ <ol>
+ <li>
+ The transform must be <strong><a href="https://en.wikipedia.org/wiki/Affine_transformation">affine</a></strong>.
+ In basic terms, this means that the transform must retain the "straightness" and "parallelness" of
+ lines and planes (or whatever is an equivalent concept for the space). For example, a translation or
+ rotation in Euclidean 3D space meets this requirement because all lines that are parallel before the
+ transform remain parallel afterwards. However, a projective transform that causes previously parallel
+ lines to meet at a single point does not.
+ </li>
+ <li>
+ The transform must be <strong>inversible</strong>. An inverse transform must exist that will return
+ the original point if given the transformed point. In other words, for a transform <var>t</var>, there
+ must exist an inverse <var>inv</var> such that <var>inv.apply(t.apply(pt))</var> returns a point equal to
+ the input point <var>pt</var>.
+ </li>
+ </ol>
+ <p>
+ Transforms that do not meet these requirements cannot be expected to produce correct results in
+ algorithms that use this interface.
+ </p>
+ </subsection>
+
+ <subsection name="Hyperplanes" id="hyperplanes">
+ <p>
+ A <em>hyperplane</em> is a subspace of dimension one less than its surrounding space. For example,
+ the hyperplanes in Euclidean 3D space are 2 dimensional planes. Similarly, the hyperplanes in Euclidean
+ 2D space are 1 dimensional lines. Hyperplanes have the property that they partition their surrounding
+ space into 3 distinct sets:
+ </p>
+ <ul>
+ <li>points on one side of the hyperplane,</li>
+ <li>points on the opposite side of the hyperplane, and</li>
+ <li>points lying directly on the hyperplane.</li>
+ </ul>
+ <p>
+ To differentiate between the two sides of a hyperplane, one side is labeled as the <em>plus</em> side
+ and the other as the <em>minus</em> side. The <em>offset</em> of a point relative to a hyperplane is the
+ distance from the point to the closest point on the hyperplane, with the sign of the distance being positive
+ if the point lies on the plus side of the hyperplane and minus otherwise. Points lying directly on the
+ hyperplane have an offset of zero.
+ </p>
+ <p>
+ A subset of the points in a hyperplane is called a <em>subhyperplane</em>.
+ A triangular facet of a polyhedron in Euclidean 3D space, for example, is a subhyperplane because its
+ interior represents a subset of the plane defined by the three points. Any subset of the points in a
+ hyperplane is a subhyperplane; the region does not need to be contiguous or even finite. In fact, a
+ subhyperplane can contain the entire hyperplane itself.
+ </p>
+ <p>
+ Hyperplanes place a key role in <em>Commons Geometry</em> not only because of their importance geometrically but also
+ because they form the basis for the region classes and algorithms, such as <a href="#bsp_trees">BSP trees</a>.
+ Hyperplanes are represented in code with the
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/partitioning/Hyperplane.html">Hyperplane</a>
+ interface, with each space and dimension contains its own custom implementation. Users are not intended to
+ implement this interface.
+ </p>
+ </subsection>
+
+ <subsection name="BSP Trees" id="bsp_trees">
+ <p>
+ Binary Space Partitioning (BSP) trees are an efficient way to represent spatial partitionings. They provide a very
+ flexible and powerful geometric data structure that can represent everything from an entire, infinite space
+ to simple, convex regions. Numerous algorithms also exist to perform operations on BSP trees, such as
+ classifying points, computing the size of a represented region, and performing boolean operations on
+ polytopes (union, intersection, difference, xor, complement).
+ </p>
+ <p>
+ The main principle in BSP trees is the recursive subdivision of space using
+ <a href="#hyperplanes">hyperplanes</a>. The easiest way to understand the data structure is to follow
+ the steps for creating a tree. When initially created, BSP trees contain a single node: the root node.
+ This node is a leaf node and represents the entire space. If one "inserts" a
+ hyperplane into the tree at that node, then the hyperplane partitions the node's space into a plus side
+ and a minus side. The root node is now "cut", and two new leaf nodes are created for it as children: a plus
+ node and a minus node. The plus node represents the half-space on the plus side of the cutting hyperplane
+ and the minus side represents the half-space on the minus side of the cutting hyperplane. These new child
+ nodes can themselves be cut by other hyperplanes, generating new child leaf nodes, and so on. In this way,
+ BSP trees can be created to represent any hyperplane-based spatial partitioning.
+ </p>
+ <p>
+ In their most basic form, BSP trees do not represents polytopes. In order to represent polytopes,
+ additional information must be stored with each leaf node, namely whether or not that leaf node lies on the
+ inside or outside of the shape. By convention, when a BSP tree node is cut, the child node that lies on the
+ minus side of the cutting hyperplane is considered to be inside of the shape, while the child node on the plus
+ side is considered to be on the outside. For example, in Euclidean 3D space, plane normals point toward the plus
+ side of the plane. Thus, when splitting a BSP tree node with a plane, the plane normal points outward from
+ the shape, as one might expect.
+ </p>
+ <p>
+ One of the main sources for the development of the BSP tree code in this project and the original
+ <span class="code">commons-math</span> project was Bruce
+ Naylor, John Amanatides and William Thibault's paper <a href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
+ BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
+ Computer Graphics 24(4), August 1990, pp 115-124, published by the
+ Association for Computing Machinery (ACM).
+ </p>
+ <p>
+ BSP tree data structures in <em>Commons Geometry</em> are represented with the
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/partitioning/bsp/BSPTree.html">BSPTree</a>
+ interface. Implementations of this interface representing regions/polytopes exist for each supported space and dimension.
+ </p>
+
+ <h4>Examples</h4>
+
+ <h5>Manual BSP Tree Region Creation</h5>
+ <p>
+ The example below manually creates a BSP tree representing a right triangle at the origin. This is not the
+ recommended way to construct such a tree, but is included here to demonstrate the BSP tree API.
+ </p>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create a tree representing an empty space (nothing "inside")
+RegionBSPTree2D tree = RegionBSPTree2D.empty();
+
+// get the root node
+RegionBSPTree2D.RegionNode2D currentNode = tree.getRoot();
+
+// cut each minus node with the next hyperplane in the shape
+currentNode.insertCut(Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision));
+currentNode = currentNode.getMinus();
+
+currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_X, Vector2D.of(-1, 1), precision));
+currentNode = currentNode.getMinus();
+
+currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_Y, Vector2D.Unit.MINUS_Y, precision));
+currentNode = currentNode.getMinus();
+
+currentNode.isInside(); // true (node is inside)
+currentNode.getParent().getPlus().isInside(); // false (sibling node is outside)
+tree.getSize(); // size of the region = 0.5
+tree.count(); // number of nodes in the tree = 7
+ </source>
+
+ <h5>Standard BSP Tree Region Creation</h5>
+ <p>
+ The example below uses the recommended approach to building BSP tree regions by inserting subhyperplanes
+ into the tree. The shape is the same as the example above.
+ </p>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create a tree representing an empty space (nothing "inside")
+RegionBSPTree2D tree = RegionBSPTree2D.empty();
+
+// insert the subhyperplanes
+tree.insert(Arrays.asList(
+ Segment.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision),
+ Segment.fromPoints(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y, precision),
+ Segment.fromPoints(Vector2D.Unit.PLUS_Y, Vector2D.ZERO, precision)
+ ));
+
+tree.getSize(); // size of the region = 0.5
+tree.count(); // number of nodes in the tree = 7
+ </source>
+
+ </subsection>
+
+ </section>
+ <section name="Core Interfaces" id="interfaces">
+
+ <p>
+ <em>Commons Geometry</em> contains a number of core interfaces that appear throughout the library, generally
+ following the same implementation patterns. For each space and dimension, there are interfaces that are always
+ implemented with a single class, some that may have more than one implementation, and some that are optional.
+ See the summary below for details.
+ </p>
+
+ <h5>Each supported space and dimension contains...</h5>
+ <ul>
+ <li>
+ <strong>A <em>single</em> implementation of...</strong>
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/Point.html">Point</a> -
+ Represents locations in the space and serves to define the space in the API.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/partitioning/Hyperplane.html">Hyperplane</a> -
+ Geometric primitive; serves to partition the space.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/partitioning/ConvexSubHyperplane.html">ConvexSubHyperplane</a> -
+ Represents convex regions embedded in hyperplanes. This interface is frequently used to define the boundaries
+ of regions, such as the facets of polyhedrons in Euclidean 3D space.
+ </li>
+ </ul>
+ </li>
<li>
- <a href="geometry.html#a1._Purpose">
- 1. Purpose of the library</a>
+ <strong><em>At most one</em> implementation of...</strong>
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/Vector.html">Vector</a> -
+ General vector interface.
+ </li>
+ </ul>
+ </li>
+ <li>
+ <strong><em>One or more</em> implementations of...</strong>
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/partitioning/SubHyperplane.html">SubHyperplane</a> -
+ Represents an arbitrary region embedded in a hyperplane, such as a 2D polygon on a 3D plane in Euclidean space.
+ This is a base interface of
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/partitioning/ConvexSubHyperplane.html">ConvexSubHyperplane</a>,
+ but does not require that the represented subhyperplane be convex. Thus, non-convex and disjoint regions
+ can be represented.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/Region.html">Region</a> -
+ Represents a region in the space. For example, in Euclidean space, this will be a length in 1D, an
+ area in 2D, and a volume in 3D. Many regions are implemented using <a href="#bsp_trees">BSP trees</a>.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/Transform.html">Transform</a> -
+ Represents a mapping between points. Instances are used to transform points and other geometric primitives.
+ </li>
+ </ul>
</li>
</ul>
+ </section>
+
+ <section name="Euclidean Space" id="euclidean">
+ <p>
+ Euclidean space is the space commonly thought of when people think of geometry. It corresponds with the
+ common notion of "flat" space or the space that we usually experience in the physical world.
+ Distances between points in this space are given by the formula \( \sqrt{(A - B)^2} \),
+ which is also known as the <em>Euclidean norm</em>.
+ </p>
+
+ <h4>Points and Vectors</h4>
+ <p>
+ Mathematically, points and vectors are separate, distinct entities. Points represent specific
+ locations in space while vectors represent displacements between vectors. However, since the use of these
+ types is so closely related and the data structures are so similar, they have been merged into a single set
+ of Euclidean <em>"VectorXD"</em> classes that implement both interfaces using Cartesian coordinates:
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/Vector1D.html">Vector1D</a>,
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/Vector2D.html">Vector2D</a>, and
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/Vector3D.html">Vector3D</a>.
+ It is up to users to determine when instances of these classes are representing points and when they are
+ representing vectors.
+ </p>
+
+ <subsection name="Euclidean 1D" id="euclidean_1d">
+ <h4>Primary Classes</h4>
+ <ul>
+ <li>
+ Point/Vector -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/Vector1D.html">Vector1D</a>
+ </li>
+ <li>
+ Hyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/OrientedPoint.html">OrientedPoint</a>
+ </li>
+ <li>
+ ConvexSubHyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/OrientedPoint.SubOrientedPoint.html">SubOrientedPoint</a>
+ (Stub implementation since no subspace exists.)
+ </li>
+ <li>
+ Region
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/RegionBSPTree1D.html">RegionBSPTree1D</a> -
+ Represents arbitrary 1D regions using BSP trees.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/Interval.html">Interval</a> -
+ Represents a single (possibly infinite), convex interval.
+ </li>
+ </ul>
+ </li>
+ <li>
+ Transform
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/AffineTransformMatrix1D.html">AffineTransformMatrix1D</a> -
+ Represents transforms using a 2x2 matrix.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/oned/FunctionTransform1D.html">FunctionTransform1D</a> -
+ Adapter class that allows simple JDK <span class="code">Function</span>'s to be used as transforms.
+ Callers are responsible for ensuring that given functions meet the <a href="#transforms">requirements for transforms</a>.
+ </li>
+ </ul>
+ </li>
+ </ul>
+
+ <h4>Examples</h4>
+
+ <h5>Interval creation</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create a closed interval and a half-open interval with a min but no max
+Interval closed = Interval.of(1, 2, precision);
+Interval halfOpen = Interval.min(1, precision);
+
+// classify some points against the intervals
+closed.contains(0.0); // false
+halfOpen.contains(Vector1D.ZERO); // false
+
+RegionLocation closedOneLoc = closed.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY
+RegionLocation halfOpenOneLoc = halfOpen.classify(Vector1D.of(1)); // RegionLocation.BOUNDARY
+
+RegionLocation closedThreeLoc = closed.classify(3.0); // RegionLocation.OUTSIDE
+RegionLocation halfOpenThreeLoc = halfOpen.classify(3.0); // RegionLocation.INSIDE
+ </source>
+
+ <h5>BSP tree from intervals</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// build a bsp tree from the union of several intervals
+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;
+tree.getSize(); // 3
+
+// convert back to intervals
+List<Interval> intervals = tree.toIntervals(); // size = 2
+ </source>
+ </subsection>
+
+ <subsection name="Euclidean 2D" id="euclidean_2d">
+ <h4>Primary Classes</h4>
+ <ul>
+ <li>
+ Point/Vector -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/Vector2D.html">Vector2D</a>
+ </li>
+ <li>
+ Hyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/Line.html">Line</a>
+ </li>
+ <li>
+ SubHyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/SubLine.html">SubLine</a>
+ </li>
+ <li>
+ ConvexSubHyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/Segment.html">Segment</a>
+ </li>
+ <li>
+ Region
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.html">RegionBSPTree2D</a> -
+ Represents arbitrary areas using BSP trees.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/ConvexArea.html">ConvexArea</a> -
+ Represents a single (possibly infinite), convex area.
+ </li>
+ </ul>
+
+ </li>
+ <li>
+ Transform
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/AffineTransformMatrix2D.html">AffineTransformMatrix2D</a> -
+ Represents transforms using a 3x3 matrix.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/FunctionTransform2D.html">FunctionTransform2D</a> -
+ Adapter class that allows simple JDK <span class="code">Function</span>'s to be used as transforms.
+ Callers are responsible for ensuring that given functions meet the <a href="#transforms">requirements for transforms</a> .
+ </li>
+ </ul>
+ </li>
+ <li>
+ Additional
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/twod/Polyline.html">Polyline</a> -
+ Represents a connected sequence of line segments.
+ </li>
+ </ul>
+ </li>
+ </ul>
+
+ <h4>Examples</h4>
+
+ <h5>Line intersection</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create some lines
+Line a = Line.fromPoints(Vector2D.ZERO, Vector2D.of(2, 2), precision);
+Line b = Line.fromPointAndDirection(Vector2D.of(1, -1), Vector2D.Unit.PLUS_Y, precision);
+
+// compute the intersection and angles
+Vector2D intersection = a.intersection(b); // (1, 1)
+double angleAtoB = a.angle(b); // pi/4
+double angleBtoA = b.angle(a); // -pi/4
+ </source>
+
+ <h5>Line segment intersection</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create some line segments
+Segment closedPosX = Segment.fromPoints(Vector2D.of(3, -1), Vector2D.of(3, 1) , precision);
+Segment closedNegX = Segment.fromPoints(Vector2D.of(-3, -1), Vector2D.of(-3, 1), precision);
+Segment halfOpen = Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision)
+ .segmentFrom(Vector2D.of(2, 0));
+
+// compute some intersections
+Vector2D posXIntersection = closedPosX.intersection(halfOpen); // (3, 0)
+Vector2D negXIntersection = closedNegX.intersection(halfOpen); // null - no intersection
+ </source>
+
+ <h5>BSP tree union</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create a connected sequence of line segments forming the unit square
+Polyline path = Polyline.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
+RegionBSPTree2D tree = path.toTree();
+
+// copy the tree
+RegionBSPTree2D copy = tree.copy();
+
+// translate the copy
+Vector2D translation = Vector2D.of(0.5, 0.5);
+copy.transform(FunctionTransform2D.from(v -> v.add(translation)));
+
+// compute the union of the regions, storing the result back into the
+// first tree
+tree.union(copy);
+
+// compute some properties
+double size = tree.getSize(); // 1.75
+Vector2D center = tree.getBarycenter(); // (0.75, 0.75)
+
+// get a polyline representing the boundary; a list is returned since trees
+// can represent disjoint regions
+List<Polyline> boundaries = tree.getBoundaryPaths(); // size = 1
+ </source>
+ </subsection>
+
+ <subsection name="Euclidean 3D" id="euclidean_3d">
+ <h4>Primary Classes</h4>
+ <ul>
+ <li>
+ Point/Vector -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/Vector3D.html">Vector3D</a>
+ </li>
+ <li>
+ Hyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/Plane.html">Plane</a>
+ </li>
+ <li>
+ SubHyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/SubPlane.html">SubPlane</a>
+ </li>
+ <li>
+ ConvexSubHyperplane -
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/ConvexSubPlane.html">ConvexSubPlane</a>
+ </li>
+ <li>
+ Region
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.html">RegionBSPTree3D</a> -
+ Represents arbitrary volumes using BSP trees.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/ConvexVolume.html">ConvexVolume</a> -
+ Represents a single (possibly infinite), convex volume.
+ </li>
+ </ul>
+
+ </li>
+ <li>
+ Transform
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/AffineTransformMatrix3D.html">AffineTransformMatrix3D</a> -
+ Represents transforms using a 4x4 matrix.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/FunctionTransform3D.html">FunctionTransform3D</a> -
+ Adapter class that allows simple JDK <span class="code">Function</span>'s to be used as transforms.
+ Callers are responsible for ensuring that given functions meet the <a href="#transforms">requirements for transforms</a>.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/rotation/QuaternionRotation.html">QuaternionRotation</a> -
+ Represents 3D rotations using quaternions. Instances can be converted back and forth between
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/rotation/AxisAngleSequence.html">AxisAngleSequence</a>s,
+ which are used to represent rotations as Euler and/or Tait-Bryan angles.
+ </li>
+ </ul>
+ </li>
+ <li>
+ Additional
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/Line3D.html">Line3D</a> -
+ Represents a line in 3D space.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-euclidean/apidocs/org/apache/commons/geometry/euclidean/threed/Segment3D.html">Segment3D</a> -
+ Represents a line segment in 3D space. Since the segment can extend to infinity in either direction, this
+ class can also be used to represent rays.
+ </li>
+ </ul>
+ </li>
+ </ul>
+
+ <h4>Examples</h4>
+
+ <h5>Plane intersection</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create two planes
+Plane a = Plane.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z, precision);
+Plane b = Plane.fromPointAndPlaneVectors(Vector3D.of(1, 1, 1),
+ Vector3D.Unit.PLUS_Z, Vector3D.Unit.MINUS_Y, precision);
+
+// compute the intersection
+Line3D line = a.intersection(b);
+
+Vector3D dir = line.getDirection(); // (0, 1, 0)
+ </source>
+
+ <h5>Transforms</h5>
+ <source>
+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
+AffineTransformMatrix3D mat = AffineTransformMatrix3D.createScale(2)
+ .translate(Vector3D.of(1, 2, 3));
+
+QuaternionRotation rot = QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Z,
+ PlaneAngleRadians.PI_OVER_TWO);
+
+// transform the input points
+List<Vector3D> matOutput = inputPts.stream()
+ .map(mat)
+ .collect(Collectors.toList()); // [(1, 2, 3), (3, 2, 3), (1, 4, 3), (1, 2, 5)]
+
+List<Vector3D> rotOutput = inputPts.stream()
+ .map(rot)
+ .collect(Collectors.toList()); // [(0, 0, 0), (0, 1, 0), (-1, 0, 0), (0, 0, 1)]
+ </source>
+
+ <h5>BSP tree from boundaries</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create the faces of a pyrmaid with a square base and its apex pointing along the
+// positive z axis
+Vector3D a1 = Vector3D.Unit.PLUS_Z;
+Vector3D b1 = Vector3D.of(0.5, 0.5, 0.0);
+Vector3D b2 = Vector3D.of(0.5, -0.5, 0.0);
+Vector3D b3 = Vector3D.of(-0.5, -0.5, 0.0);
+Vector3D b4 = Vector3D.of(-0.5, 0.5, 0.0);
+
+Vector3D[][] faces = {
+ {b1, a1, b2},
+ {b2, a1, b3},
+ {b3, a1, b4},
+ {b4, a1, b1},
+ {b1, b2, b3, b4}
+};
+
+// convert the faces to convex sub planes and insert into a bsp tree
+RegionBSPTree3D tree = RegionBSPTree3D.empty();
+Arrays.stream(faces)
+ .map(vertices -> ConvexSubPlane.fromVertexLoop(Arrays.asList(vertices), precision))
+ .forEach(tree::insert);
+
+// split the region through its barycenter along a diagonal of the base
+Plane cutter = Plane.fromPointAndNormal(tree.getBarycenter(), Vector3D.Unit.from(1, 1, 0), precision);
+Split<RegionBSPTree3D> split = tree.split(cutter);
+
+// compute some properties for the minus side of the split and convert back to subhyperplanes
+// (ie, facets)
+RegionBSPTree3D minus = split.getMinus();
+
+double minusSize = minus.getSize(); // 1/6
+List<ConvexSubPlane> minusFacets = minus.getBoundaries(); // size = 4
+ </source>
+ </subsection>
+
+ </section>
+
+ <section name="Spherical Space" id="spherical">
+
+ <p>
+ Spherical space is the space present on the surface of a circle (1D) or sphere (2D). This space is an example
+ of a non-Euclidean geometry.
+ </p>
+ <p>
+ One of the key features of spherical space is that it wraps around on itself: if a line is drawn from
+ a point and continues in a single direction, it will eventually return to its starting point. This feature has
+ several consequences, one of which is that points are not unique in terms of their coordinates. For example,
+ in 1D space, the point \(0\) is equivalent to the point \(2\pi\) and any other point of the form
+ \(2n\pi\). The point classes in this space address this issue by providing two representations of the location
+ of points: one representation containing the coordinates given by the user and another, "normalized" representation
+ that uniquely identifies the location of the point. In 1D, the normalized form is the azimuth angle in the
+ range \([0, 2\pi)\) (see
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/Point1S.html#getNormalizedAzimuth--">Point1S.getNormalizedAzimuth()</a>
+ ). In 2D, the normalized form is a 3D Euclidean vector indicating the point's location on the unit sphere (see
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/Point2S.html#getVector--">Point2S.getVector()</a>
+ ).
+ </p>
+ <p>
+ Another consequence of the wrap-around feature of spherical space is that the concept of "convexity" must be
+ defined more carefully than in Euclidean space. In Euclidean space, when a region is convex, it simply means
+ that a line drawn between any two points in the region also lies in the region. In spherical space, we must be
+ more careful because there are always at least two lines that can be drawn between any two points: one going "the
+ short way" around the space and the other going "the long way". We therefore define a convex region to be one
+ where the <em>shortest</em> path between any two points lies entirely within the region. (In cases where
+ the distances are equal, we also define the region to be convex.) In the 1D case, this means that convex intervals
+ must either be completely full or have a size less than or equal to \(\pi\) (see
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/AngularInterval.Convex.html">AngularInterval.Convex</a>
+ ), which implies the same for
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/GreatArc.html">GreatArc</a>
+ instances in 2D.
+ </p>
+
+ <subsection name="Spherical 1D" id="spherical_1d">
+ <h4>Primary Classes</h4>
+ <ul>
+ <li>
+ Point -
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/Point1S.html">Point1S</a>
+ </li>
+ <li>
+ Hyperplane -
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/CutAngle.html">CutAngle</a>
+ </li>
+ <li>
+ ConvexSubHyperplane -
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/CutAngle.SubCutAngle.html">SubCutAngle</a> -
+ (Stub implementation since no subspace exists.)
+ </li>
+ <li>
+ Region
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/RegionBSPTree1S.html">RegionBSPTree1S</a> -
+ Represents arbitrary 1D regions using BSP trees.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/AngularInterval.html">AngularInterval</a> -
+ Represents a single interval, possibly non-convex.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/AngularInterval.Convex.html">AngularInterval.Convex</a> -
+ Represents a single, convex interval.
+ </li>
+ </ul>
+
+ </li>
+ <li>
+ Transform
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/oned/Transform1S.html">Transform1S</a> -
+ Transform supporting rotation and reflection.
+ </li>
+ </ul>
+ </li>
+ </ul>
+
+ <h4>Examples</h4>
+
+ <h5>AngularInterval creation</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create angular intervals of different sizes, one of size pi/2 and one of size 3pi/2
+AngularInterval a = AngularInterval.of(0, PlaneAngleRadians.PI_OVER_TWO, precision);
+AngularInterval b = AngularInterval.of(Point1S.PI, Point1S.of(PlaneAngleRadians.PI_OVER_TWO), precision);
+
+// test some points
+a.contains(Point1S.of(0.25 * Math.PI)); // true
+b.contains(Point1S.of(0.25 * Math.PI)); // true
+
+RegionLocation aLocZero = a.classify(Point1S.ZERO); // RegionLocation.BOUNDARY
+RegionLocation bLocZero = b.classify(Point1S.ZERO); // RegionLocation.INSIDE
+ </source>
+
+ <h5>BSP tree from intervals</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create a region from the union of multiple angular intervals
+RegionBSPTree1S tree = RegionBSPTree1S.empty();
+tree.add(AngularInterval.of(0, 0.25 * Math.PI, precision));
+tree.add(AngularInterval.of(0.5 * Math.PI, Math.PI, precision));
+tree.add(AngularInterval.of(0.75 * Math.PI, 1.5 * Math.PI, precision));
+
+// compute the region size in radians
+double size = tree.getSize(); // 1.25pi
+
+// convert back to intervals
+List<AngularInterval> intervals = tree.toIntervals(); //size = 2
+ </source>
+ </subsection>
+
+ <subsection name="Spherical 2D" id="spherical_2d">
+ <h4>Primary Classes</h4>
+ <ul>
+ <li>
+ Point -
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/Point2S.html">Point2S</a>
+ </li>
+ <li>
+ Hyperplane -
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/GreatCircle.html">GreatCircle</a>
+ </li>
+ <li>
+ SubHyperplane -
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/SubGreatCircle.html">SubGreatCircle</a>
+ </li>
+ <li>
+ ConvexSubHyperplane -
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/GreatArc.html">GreatArc</a>
+ </li>
+ <li>
+ Region
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/RegionBSPTree2S.html">RegionBSPTree2S</a> -
+ Represents arbitrary areas using BSP trees.
+ </li>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/ConvexArea2S.html">ConvexArea2S</a> -
+ Represents a single, convex area.
+ </li>
+ </ul>
+
+ </li>
+ <li>
+ Transform
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/Transform2S.html">Transform2S</a> -
+ Transform supporting rotation and reflection.
+ </li>
+ </ul>
+ </li>
+ <li>
+ Additional
+ <ul>
+ <li>
+ <a class="code" href="../commons-geometry-spherical/apidocs/org/apache/commons/geometry/spherical/twod/GreatArcPath.html">GreatArcPath</a> -
+ Represents a connected sequences of great arcs; useful for defining the boundaries of regions.
+ </li>
+ </ul>
+ </li>
+ </ul>
+
+ <h4>Examples</h4>
+
+ <h5>GreatCircle intersection</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+// create two non-parallel great arcs
+GreatCircle a = GreatCircle.fromPoints(Point2S.PLUS_I, Point2S.PLUS_K, precision);
+GreatCircle b = GreatCircle.fromPole(Vector3D.Unit.PLUS_Z, precision);
+
+// find the two intersection points of the great circles
+Point2S ptA = a.intersection(b); //(pi, pi/2)
+Point2S ptB = ptA.antipodal(); // (0, pi/2)
+ </source>
+
+ <h5>BSP tree from boundaries</h5>
+ <source>
+DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
+
+// create a path outlining a quadrant triangle
+GreatArcPath path = GreatArcPath.builder(precision)
+ .append(Point2S.PLUS_I)
+ .append(Point2S.PLUS_J)
+ .append(Point2S.PLUS_K)
+ .build(true); // close the path with the starting path
+
+// convert to a region
+RegionBSPTree2S tree = path.toTree();
+
+// split in two through the barycenter
+GreatCircle splitter = GreatCircle.fromPoints(tree.getBarycenter(), Point2S.PLUS_K, precision);
+Split<RegionBSPTree2S> split = tree.split(splitter);
+
+// compute some properties for the minus side
+RegionBSPTree2S minus = split.getMinus();
+
+double minusSize = minus.getSize(); // pi/4
+List<GreatArcPath> minusPaths = minus.getBoundaryPaths(); // size = 1
+ </source>
+ </subsection>
+
</section>
</body>
-
+
</document>