Package com.vividsolutions.jts.algorithm

Contains classes and interfaces implementing fundamental computational geometry algorithms.

See:
Description

Interface Summary

PointInRing

An interface for classes which test whether a Coordinate lies inside a ring.

Class Summary

CentroidArea	Computes the centroid of an area geometry.
CentroidLine	Computes the centroid of a linear geometry.
CentroidPoint	Computes the centroid of a point geometry.
CGAlgorithms	Specifies and implements various fundamental Computational Geometric algorithms.
ConvexHull	Computes the convex hull of a Geometry.
HCoordinate	Represents a homogeneous coordinate in a 2-D coordinate space.
InteriorPointArea	Computes a point in the interior of an area geometry.
InteriorPointLine	Computes a point in the interior of an linear geometry.
InteriorPointPoint	Computes a point in the interior of an point geometry.
LineIntersector	A LineIntersector is an algorithm that can both test whether two line segments intersect and compute the intersection point if they do.
MCPointInRing	Implements PointInRing using MonotoneChains and a BinTree index to increase performance.
MinimumDiameter	Computes the minimum diameter of a Geometry.
NonRobustCGAlgorithms	Non-robust versions of various fundamental Computational Geometric algorithms, FOR TESTING PURPOSES ONLY!.
NonRobustLineIntersector	A non-robust version of .
PointLocator	Computes the topological relationship (Location) of a single point to a Geometry.
RobustCGAlgorithms	Stub version of RobustCGAlgorithms for backwards compatibility.
RobustDeterminant	Implements an algorithm to compute the sign of a 2x2 determinant for double precision values robustly.
RobustLineIntersector	A robust version of .
SimplePointInAreaLocator	Computes whether a point lies in the interior of an area Geometry.
SimplePointInRing	Tests whether a Coordinate lies inside a ring, using a linear-time algorithm.
SIRtreePointInRing	Implements PointInRing using a SIRtree index to increase performance.

Exception Summary

NotRepresentableException

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

Package com.vividsolutions.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