Commons Geometry User GuideContentsOverviewCommons 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.
Example ModulesIn 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. ConceptsFloating Point MathAll 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 TransformsA 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 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. HyperplanesA 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:
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 TreesBinary 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. ExamplesManual BSP Tree Region CreationThe 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 CreationThe 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 InterfacesCommons 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...
Euclidean SpaceEuclidean 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 VectorsMathematically, 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 1DPrimary Classes
ExamplesInterval creationPrecision.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 intervalsPrecision.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 2DPrimary Classes
ExamplesLine intersectionPrecision.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 intersectionPrecision.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 unionPrecision.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 LinecastPrecision.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 3DPrimary Classes
ExamplesPlane intersectionPrecision.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) TransformsList<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 boundariesPrecision.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 LinecastPrecision.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 SpaceSpherical 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 1DPrimary Classes
ExamplesAngularInterval creationPrecision.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 intervalsPrecision.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 2DPrimary Classes
ExamplesGreatCircle intersectionPrecision.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 boundariesPrecision.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 |