Commons Geometry User Guide

Overview
Example Modules
Concepts
Core Interfaces
Euclidean Space
Spherical Space
- Spherical 1D
- Spherical 2D

Overview

Commons Geometry provides types and utilities for geometric processing. The code originated in the org.apache.commons.math3.geometry package of the commons-math 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.

Commons Geometry is divided into a number of submodules.

commons-geometry-core - Provides core interfaces and classes.
commons-geometry-euclidean - Provides classes for Euclidean space in 1D, 2D, and 3D.
commons-geometry-spherical - Provides classes for Spherical space in 1D and 2D.
commons-geometry-io-core - Provides core classes and interfaces for IO functionality.
commons-geometry-io-euclidean - Provides classes for IO operations on Euclidean data formats, such STL and OBJ.

Example Modules

In addition to the modules above, the Commons Geometry source distribution contains example code demonstrating library functionality and/or providing useful development utilities. These modules are not part of the public API of the library and no guarantees are made concerning backwards compatibility. The example module parent page contains a listing of the available modules.

Concepts

Floating Point Math

All floating point numbers in Commons Geometry are represented using doubles.

The concept of a precision context 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 org.apache.commons.numbers.core.Precision.DoubleEquivalence class from the Commons Numbers library. The example below uses an epsilon (tolerance) value to compare numbers for equality.

// create a precision instance with an epsilon (aka, tolerance) value of 1e-3
Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-3);

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

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

equals() vs eq()

Many objects in Commons Geometry provide both a standard Java equals() method as well as an eq() method. The equals() method always tests for strict equality between objects. In general, any floating point values in the two objects must be exactly equal in order for the equals() method to return true (see the documentation on individual classes for details). This strictness is enforced so that equals() can behave as expected by the JDK, fulfilling properties such as transitivity and the relationship to hashCode().

In contrast, the eq() method is used to test for approximate equality between objects, with floating point values being evaluated by a provided Precision.DoubleEquivalence instance. Because of this approximate nature, this method cannot be guaranteed to be transitive or have any meaningful relationship to hashCode. The eq() should be used to test for object equality in cases where floating-point errors in a computation may have introduced small discrepancies in values. The example below demonstrates the differences between equals() and eq().

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

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

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

Transforms

A geometric transform is simply a function that maps points from one set to another. Transforms in Commons Geometry are represented with the Transform 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 of this interface must meet the requirements listed below. Transforms that do not meet these requirements cannot be expected to produce correct results in algorithms that use this interface.

Transforms must represent functions that are one-to-one and onto (i.e. bijections). This means that every point in the space must be mapped to exactly one other point in the space. This also implies that the function is invertible.
Transforms must preserve collinearity. This means that if a set of points lie on a common hyperplane before the transform, then they must also lie on a common hyperplane after the transform. For example, if the Euclidean 2D points a, b, and c lie on line L, then the transformed points a', b', and c' must lie on line L', where L' is the transformed form of the line.
Transforms must preserve the concept of parallelism defined for the space. This means that hyperplanes that are parallel before the transformation must remain parallel afterwards, and hyperplanes that intersect must also intersect afterwards. For example, a transform that causes parallel lines to converge to a single point in Euclidean space (such as the projective transforms used to create perspective viewpoints in 3D graphics) would not meet this requirement. However, a transform that turns a square into a rhombus with no right angles would fulfill the requirement, since the two pairs of parallel lines forming the square remain parallel after the transformation.

Transforms that meet the above requirements in Euclidean space (and other affine spaces) are known as affine transforms and include such common operations as translation, rotation, reflection, scaling, and any combinations thereof.

Hyperplanes

A hyperplane 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:

points on one side of the hyperplane,
points on the opposite side of the hyperplane, and
points lying directly on the hyperplane.

To differentiate between the two sides of a hyperplane, one side is labeled as the plus side and the other as the minus side. The offset 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.

Hyperplanes play a key role in Commons Geometry not only because of their importance geometrically but also because they form the basis for the region classes and algorithms, such as BSP trees. Hyperplanes are represented in code with the Hyperplane interface, with each space and dimension containing its own custom implementation. Users are not intended to implement this interface.

BSP Trees

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).

The main principle in BSP trees is the recursive subdivision of space using hyperplanes. 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.

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 are considered to 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. (In Commons Geometry, this default convention can be changed by passing a RegionCutRule value when inserting into a tree. This gives fine-grain control over the structure of the tree and can be used to create structural splits in the tree, meaning splits that do not encode region information but are only used to help keep the tree balanced.)

One of the main sources for the development of the BSP tree code in this project and the original commons-math project was Bruce Naylor, John Amanatides and William Thibault's paper Merging BSP Trees Yields Polyhedral Set Operations Proc. Siggraph '90, Computer Graphics 24(4), August 1990, pp 115-124, published by the Association for Computing Machinery (ACM).

BSP tree data structures in Commons Geometry are represented with the BSPTree interface. Implementations of this interface representing regions/polytopes exist for each supported space and dimension.

Examples

Manual BSP Tree Region Creation

The example below creates a BSP tree representing the unit square by directly inserting hyperplane cuts into nodes. A diagonal "structural" cut is used at the root node in order to keep the tree balanced.

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

RegionBSPTree2D.RegionNode2D currentNode;

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

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

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

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

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

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

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

Standard BSP Tree Region Creation

The example below uses the standard approach to building BSP tree regions by inserting hyperplane subsets into the tree. The shape is the same as the example above.

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

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

Core Interfaces

Commons Geometry 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. Additionally, each space and dimension has a primary factory class containing static factory methods for producing hyperplanes and common hyperplane subsets. See the summary below for details.

Each supported space and dimension contains...

One implementation of...
- Point - Represents locations in the space and serves to define the space in the API.
- Hyperplane - Geometric primitive; serves to partition the space.
One implementation (if applicable) of...
- Vector - General vector interface.
One or more implementations of...
- HyperplaneSubset - Represents an arbitrary subset of points in a hyperplane, such as a set of 1D intervals on a line or a polygonal area on a 3D plane. This is a base interface of HyperplaneConvexSubset, but does not require that the represented subset be convex. Thus, non-convex and disjoint regions can be represented. Instances may have finite or infinite size.
- HyperplaneConvexSubset - Represents convex subsets of points in hyperplanes. This interface is frequently used to define the boundaries of regions, such as line segments in Euclidean 2D space and polyhedron facets in Euclidean 3D space. Instances of this type may be finite (such as line segments) or infinite (such as rays).
- Region - Represents a region in the space. Regions partition their surrounding space into sets of points lying on the inside, outside, and boundary of the region. Examples include circles, spheres, polygons, and polyhedrons. Each dimension and space has at least one region type implemented using BSP trees. Instances may have finite or infinite size.
- Transform - Represents an inversible mapping between points that preserves parallelism. Instances are used to transform points and other geometric primitives.

Euclidean Space

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 Euclidean norm.

Points and Vectors

Mathematically, points and vectors are separate, distinct entities. Points represent specific locations in space while vectors represent displacements between points. 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 "VectorXD" classes that implement both interfaces using Cartesian coordinates: Vector1D, Vector2D, and Vector3D. It is up to users to determine when instances of these classes are representing points and when they are representing vectors.

Euclidean 1D

Primary Classes

Point/Vector - Vector1D
Hyperplane - OrientedPoint
Hyperplane Factory Class - OrientedPoints
Region
- RegionBSPTree1D - Represents arbitrary 1D regions using BSP trees.
- Interval - Represents a single (possibly infinite), convex interval.
Transform
- AffineTransformMatrix1D - Represents affine transforms using a 2x2 matrix.

Examples

Interval creation

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(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

BSP tree from intervals

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(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

Euclidean 2D

Primary Classes

Point/Vector - Vector2D
Hyperplane - Line
HyperplaneSubset - LineSubset
HyperplaneConvexSubset - LineConvexSubset (subclasses include Segment, Ray, and ReverseRay)
Hyperplane / HyperplaneSubset Factory Class - Lines
Region
- RegionBSPTree2D - Represents arbitrary areas using BSP trees.
- ConvexArea - Represents a single (possibly infinite), convex area.
- Circle - Represents a circle.
Transform
- AffineTransformMatrix2D - Represents affine transforms using a 3x3 matrix.
Additional
- LinePath - Represents a connected sequence of line subsets.

Examples

Line intersection

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

// create some lines
Line a = Lines.fromPoints(Vector2D.ZERO, Vector2D.of(2, 2), precision);
Line b = Lines.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

Line segment intersection

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

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

BSP tree union

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

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

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

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

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

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

Linecast

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

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

Euclidean 3D

Primary Classes

Point/Vector - Vector3D
Hyperplane - Plane (the subclass EmbeddingPlane contains additional in-plane vectors to define embedded 2D subspaces)
HyperplaneSubset - PlaneSubset
HyperplaneConvexSubset - PlaneConvexSubset (subinterfaces include ConvexPolygon3D and Triangle3D)
Hyperplane / HyperplaneSubset Factory Class - Planes
Region
- RegionBSPTree3D - Represents arbitrary volumes using BSP trees.
- ConvexVolume - Represents a single (possibly infinite), convex volume.
- Sphere - Represents a sphere.
Transform
- AffineTransformMatrix3D - Represents affine transforms using a 4x4 matrix.
- QuaternionRotation - Represents 3D rotations using quaternions. Instances can be converted back and forth between AxisAngleSequences, which are used to represent rotations as Euler and/or Tait-Bryan angles.
Additional
- Line3D - Represents a line in 3D space.
- LineConvexSubset3D - Represents a finite or infinite line convex subset. Subclasses include Segment3D, Ray3D, and ReverseRay3D.
- Lines3D - Factory class for 3D lines and line subsets.

Examples

Plane intersection

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

// create two planes
Plane a = Planes.fromPointAndNormal(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z, precision);
Plane b = Planes.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)

Transforms

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,
        Angle.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)]

BSP tree from boundaries

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

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

// split the region through its centroid along a diagonal of the base
Plane cutter = Planes.fromPointAndNormal(tree.getCentroid(), 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 hyperplane subsets
// (ie, boundary facets)
RegionBSPTree3D minus = split.getMinus();

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

Linecast

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

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

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

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

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

Spherical Space

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.

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 Point1S.getNormalizedAzimuth() ). In 2D, the normalized form is a 3D Euclidean vector indicating the point's location on the unit sphere (see Point2S.getVector() ).

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 shortest 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 AngularInterval.Convex ), which implies the same for GreatArc instances in 2D.

Spherical 1D

Primary Classes

Point - Point1S
Hyperplane - CutAngle
Hyperplane Factory Class - CutAngles
Region
- RegionBSPTree1S - Represents arbitrary 1D regions using BSP trees.
- AngularInterval - Represents a single interval, possibly non-convex.
- AngularInterval.Convex - Represents a single, convex interval.
Transform
- Transform1S - Transform supporting rotation and reflection.

Examples

AngularInterval creation

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

// create angular intervals of different sizes, one of size pi/2 and one of size 3pi/2
AngularInterval a = AngularInterval.of(0, Angle.PI_OVER_TWO, precision);
AngularInterval b = AngularInterval.of(Point1S.PI, Point1S.of(Angle.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

BSP tree from intervals

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(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

Spherical 2D

Primary Classes

Point - Point2S
Hyperplane - GreatCircle
HyperplaneSubset - GreatCircleSubset
HyperplaneConvexSubset - GreatArc
Hyperplane / HyperplaneSubset Factory Class - GreatCircles
Region
- RegionBSPTree2S - Represents arbitrary areas using BSP trees.
- ConvexArea2S - Represents a single, convex area.
Transform
- Transform2S - Transform supporting rotation and reflection.
Additional
- GreatArcPath - Represents a connected sequences of great arcs; useful for defining the boundaries of regions.

Examples

GreatCircle intersection

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-6);

// create two great circles
GreatCircle a = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_K, precision);
GreatCircle b = GreatCircles.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)

BSP tree from boundaries

Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(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 centroid
GreatCircle splitter = GreatCircles.fromPoints(tree.getCentroid(), 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

Commons Geometry User Guide

Contents

Overview

Example Modules

Concepts

Floating Point Math

equals() vs eq()

Transforms

Hyperplanes

BSP Trees

Examples

Manual BSP Tree Region Creation

Standard BSP Tree Region Creation

Core Interfaces

Each supported space and dimension contains...

Euclidean Space

Points and Vectors

Euclidean 1D

Primary Classes

Examples

Interval creation

BSP tree from intervals

Euclidean 2D

Primary Classes

Examples

Line intersection

Line segment intersection

BSP tree union

Linecast

Euclidean 3D

Primary Classes

Examples

Plane intersection

Transforms

BSP tree from boundaries

Linecast

Spherical Space

Spherical 1D

Primary Classes

Examples

AngularInterval creation

BSP tree from intervals

Spherical 2D

Primary Classes

Examples

GreatCircle intersection

BSP tree from boundaries