Package org.locationtech.jts.algorithm

Contains classes and interfaces implementing fundamental computational geometry algorithms.

See: Description

Interface Summary

Interface	Description
BoundaryNodeRule	An interface for rules which determine whether node points which are in boundaries of Lineal geometry components are in the boundary of the parent geometry collection.

Class Summary

Class	Description
Angle	Utility functions for working with angles.
Area	Functions for computing area.
BoundaryNodeRule.EndPointBoundaryNodeRule	A BoundaryNodeRule which specifies that any points which are endpoints of lineal components are in the boundary of the parent geometry.
BoundaryNodeRule.Mod2BoundaryNodeRule	A BoundaryNodeRule specifies that points are in the boundary of a lineal geometry iff the point lies on the boundary of an odd number of components.
BoundaryNodeRule.MonoValentEndPointBoundaryNodeRule	A BoundaryNodeRule which determines that only endpoints with valency of exactly 1 are on the boundary.
BoundaryNodeRule.MultiValentEndPointBoundaryNodeRule	A BoundaryNodeRule which determines that only endpoints with valency greater than 1 are on the boundary.
Centroid	Computes the centroid of a Geometry of any dimension.
CGAlgorithms	Deprecated See Length, Area, Distance, Orientation, PointLocation
CGAlgorithms3D	Basic computational geometry algorithms for geometry and coordinates defined in 3-dimensional Cartesian space.
CGAlgorithmsDD	Implements basic computational geometry algorithms using DD arithmetic.
ConvexHull	Computes the convex hull of a Geometry.
Distance	Functions to compute distance between basic geometric structures.
HCoordinate	Represents a homogeneous coordinate in a 2-D coordinate space.
InteriorPoint	Computes an interior point of a Geometry.
InteriorPointArea	Computes a point in the interior of an areal geometry.
InteriorPointLine	Computes a point in the interior of an linear geometry.
InteriorPointPoint	Computes a point in the interior of an point geometry.
Intersection	Functions to compute intersection points between lines and line segments.
Length	Functions for computing length.
LineIntersector	A LineIntersector is an algorithm that can both test whether two line segments intersect and compute the intersection point(s) if they do.
MinimumAreaRectangle	Computes the minimum-area rectangle enclosing a Geometry.
MinimumBoundingCircle	Computes the Minimum Bounding Circle (MBC) for the points in a Geometry.
MinimumDiameter	Computes the minimum diameter of a Geometry.
Orientation	Functions to compute the orientation of basic geometric structures including point triplets (triangles) and rings.
PointLocation	Functions for locating points within basic geometric structures such as line segments, lines and rings.
PointLocator	Computes the topological (Location) of a single point to a Geometry.
PolygonNodeTopology	Functions to compute topological information about nodes (ring intersections) in polygonal geometry.
RayCrossingCounter	Counts the number of segments crossed by a horizontal ray extending to the right from a given point, in an incremental fashion.
RectangleLineIntersector	Computes whether a rectangle intersects line segments.
RobustDeterminant	Implements an algorithm to compute the sign of a 2x2 determinant for double precision values robustly.
RobustLineIntersector	A robust version of LineIntersector.

Exception Summary

Exception	Description
NotRepresentableException	Indicates that a HCoordinate has been computed which is not representable on the Cartesian plane.

Package org.locationtech.jts.algorithm Description

Contains classes and interfaces implementing fundamental computational geometry algorithms.

Robustness

Geometrical algorithms involve a combination of combinatorial and numerical computation. As with all numerical computation using finite-precision numbers, the algorithms chosen are susceptible to problems of robustness. A robustness problem occurs when a numerical calculation produces an incorrect answer for some inputs due to round-off errors. Robustness problems are especially serious in geometric computation, since they can result in errors during topology building.

There are many approaches to dealing with the problem of robustness in geometrical computation. Not surprisingly, most robust algorithms are substantially more complex and less performant than the non-robust versions. Fortunately, JTS is sensitive to robustness problems in only a few key functions (such as line intersection and the point-in-polygon test). There are efficient robust algorithms available for these functions, and these algorithms are implemented in JTS.

Computational Performance

Runtime performance is an important consideration for a production-quality implementation of geometric algorithms. The most computationally intensive algorithm used in JTS is intersection detection. JTS methods need to determine both all intersection between the line segments in a single Geometry (self-intersection) and all intersections between the line segments of two different Geometries.

The obvious naive algorithm for intersection detection (comparing every segment with every other) has unacceptably slow performance. There is a large literature of faster algorithms for intersection detection. Unfortunately, many of them involve substantial code complexity. JTS tries to balance code simplicity with performance gains. It uses some simple techniques to produce substantial performance gains for common types of input data.

Package Specification

• Java Topology Suite Technical Specifications
• OpenGIS Simple Features Specification for SQL