Commons Geometry User Guide

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 5 submodules.

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 DoublePrecisionContext interface. The example below uses an epsilon (tolerance) value to compare numbers for equality.

// create a precision context with an epsilon (aka, tolerance) value of 1e-3
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-3);

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

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


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

DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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.

1. 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.
2. 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.
3. 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 place 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 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.

DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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.

DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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 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

Examples

Interval creation
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

BSP tree from intervals
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

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

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

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


Euclidean 2D

Examples

Line intersection
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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

Examples

Plane intersection
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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,

// 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
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

// create the faces of a pyramid with a square base and its apex pointing along the
// positive z axis
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
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);

// create a BSP tree representing an axis-aligned cube with corners at (0, 0, 0) and (1, 1, 1)
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

Examples

AngularInterval creation
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

BSP tree from intervals
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.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

Examples

GreatCircle intersection
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(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
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 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


Convex Hull

A convex hull of a region or shape in the smallest convex set of points that completely contains the shape. For example, if a set of points in Euclidean 2D space are represented by nails in a flat piece of wood, then the convex hull of that shape would be the path made by a rubber band wrapped around all of the nails. Similarly, in Euclidean 3D space, the convex hull of a shape can be visualized as the result of "shrink-wrapping" the shape with a very tight, non-flexible material.

A number of convex hull algorithms exist, for various spaces and dimensions, and it is the goal of the commons-geometry-hull module to provide implementations of these algorithms.

Convex Hull - Euclidean 2D

Examples

Monotone Chain
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-10);

// create a list of input points for the algorithm
List<Vector2D> pts = Arrays.asList(
Vector2D.ZERO,
Vector2D.of(0.5, 0.5),
Vector2D.of(0, 0.5),
Vector2D.of(0, 1),
Vector2D.of(0.25, 0.1),
Vector2D.of(1, 0),
Vector2D.of(1, 1),
Vector2D.of(0.75, 0.9)
);

// create an instance of the monotone chain convex hull generator
MonotoneChain mc = new MonotoneChain(precision);

// compute the convex hull
ConvexHull2D hull = mc.generate(pts);

// list the vertices from the input that were used in the hull
List<Vector2D> vertices = hull.getVertices(); // [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]

// get the hull as a region
ConvexArea region = hull.getRegion();
boolean containsAll = pts.stream().allMatch(region::contains); // true - region contains all input points


Enclosing

The smallest enclosing ball problem is the mathematical problem of locating the n-sphere with the smallest radius that encloses a given set of points. This module contains implementations of algorithms for solving this problem.

Primary Classes

• Encloser - Interface for classes that solve the smallest enclosing ball problem.
• EnclosingBall - Class containing the result of smallest enclosing ball computation.
• WelzlEncloser - Class implementing a space-independent version of Emo Welzl's algorithm for computing the smallest enclosing ball of a set of points. Specialized classes exist for Euclidean 2D space (WelzlEncloser2D) and Euclidean 3D space (WelzlEncloser3D).

Examples

WelzlEncloser3D
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-10);

List>Vector3D< points = Arrays.asList(
Vector3D.of(0, 0, 1),
Vector3D.of(0.75, 0, 1),
Vector3D.of(2, 0, 1),
Vector3D.of(1, 0, 2)
);

// compute the enclosing ball
WelzlEncloser3D encloser = new WelzlEncloser3D(precision);

EnclosingBall>Vector3D< sphere = encloser.enclose(points);

// check the generated ball
Vector3D center = sphere.getCenter(); // (1, 0, 1)