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:33 UTC
[commons-geometry] 06/06: Merge branch 'GEOMETRY-45__Matt'
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 6a14ededd61426ba527bebfb6beb204eb768621b
Merge: db148ff ffef8c0
Author: Gilles Sadowski <gi...@harfang.homelinux.org>
AuthorDate: Mon Dec 23 01:19:47 2019 +0100
Merge branch 'GEOMETRY-45__Matt'
Closes #46.
.../euclidean/threed}/SphereGenerator.java | 4 +-
.../euclidean/threed}/package-info.java | 2 +-
.../euclidean/twod}/DiskGenerator.java | 2 +-
.../euclidean/twod}/package-info.java | 2 +-
.../geometry/enclosing/WelzlEncloser2DTest.java | 2 +-
.../geometry/enclosing/WelzlEncloser3DTest.java | 2 +-
.../euclidean/threed}/SphereGeneratorTest.java | 2 +-
.../euclidean/twod}/DiskGeneratorTest.java | 2 +-
.../twod}/AbstractConvexHullGenerator2D.java | 2 +-
.../euclidean/twod}/AklToussaintHeuristic.java | 2 +-
.../hull => hull/euclidean/twod}/ConvexHull2D.java | 2 +-
.../euclidean/twod}/ConvexHullGenerator2D.java | 2 +-
.../euclidean/twod}/MonotoneChain.java | 2 +-
.../hull => hull/euclidean/twod}/package-info.java | 2 +-
.../euclidean/twod}/AklToussaintHeuristicTest.java | 2 +-
.../twod}/ConvexHullGenerator2DAbstractTest.java | 2 +-
.../euclidean/twod}/MonotoneChainTest.java | 2 +-
src/site/xdoc/userguide/index.xml | 66 +---------------------
18 files changed, 19 insertions(+), 83 deletions(-)
diff --cc src/site/xdoc/userguide/index.xml
index f7956ec,57d2143..2ff63bd
--- a/src/site/xdoc/userguide/index.xml
+++ b/src/site/xdoc/userguide/index.xml
@@@ -24,948 -24,15 +24,884 @@@
</properties>
<body>
- <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>
+ <section name="Table of Contents" href="toc">
- <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>