# Commons Geometry User Guide ## Contents Overview Concepts Floating Point Math Transforms Hyperplanes BSP Trees Core Interfaces Euclidean Space Euclidean 1D Euclidean 2D Euclidean 3D Spherical Space Spherical 1D Spherical 2D Convex Hull Euclidean 2D Enclosing ## 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. 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-hull - Provides implementations of convex hull algorithms. commons-geometry-enclosing - Provides implementations of enclosing ball algorithms. ## 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. 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 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 #### 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
    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();

    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
    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 #### 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
    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,
            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)]
##### 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 #### 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
    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, 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
    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 #### Primary Classes ConvexHullGenerator2D - Interface for classes that implement convex hull algorithms in Euclidean 2D space. ConvexHull2D - Class representing output from convex hull operations. MonotoneChain - Class implementing Andrew's monotone chain algorithm for computing convex hulls. #### 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)
    double radius = sphere.getRadius(); // 1.0
    boolean containsCenter = sphere.contains(center); // true
    boolean containsOrigin = sphere.contains(Vector3D.ZERO); // false