Java Topology Suite

Discussion

JTS is an API which provides:

an implementation of the spatial data model defined in the OGC Simple Features Specification for SQL (SFS)
a complete, consistent, implementation of fundamental 2D spatial algorithms including binary predicates (such as touch and overlap) and spatial analysis methods (such as intersection and buffer)
an explicit precision model, with algorithms that gracefully handle situations that result in dimensional collapse.
robust implementations of key computational geometric operations
I/O in Well-Known Text format

It is written in 100% pure Java^TM (Version 1.2 and above).

Spatial Data Model

JTS provides the following spatial data types:

Point

MultiPoint

LineString	LinearRing	MultiLineString
Polygon	MultiPolygon	GeometryCollection

As in the SFS, Geometries in JTS have an Interior, a Boundary, and an Exterior.

Binary Predicates

JTS supports a complete set of binary predicates. Binary predicate methods take two Geometries as arguments and return a boolean indicating whether the Geometries have the named spatial relationship. The relationships supported are


							equals, disjoint, intersects, touches, crosses, within, contains, overlaps

. Also, the general relate operator is supported. relate can be used to determine the Dimensionally Extended 9 Intersection Matrix (DE-9IM) which completely describes the relationship of two Geometries.

The algorithm used for computing Binary Predicates in JTS is robust, and is not subject to dimensional collapse problems.

Example:

Two Geometries to compare

The Binary Predicates

The DE-9IM returned by relate

Spatial Analysis Methods

JTS supports the fundamental spatial analysis methods. Spatial analysis methods take one or two Geometries as arguments and return a new constructed Geometry.

The spatial analysis methods are:

Intersection

Union

Difference

Symmetric Difference

Convex Hull

Buffer (with both positive...

and negative widths)

All binary methods support heterogenous as well as homogeneous arguments:

Intersection of a LineString and a Polygon

Union of a MultiPoint and a LineString

Precision Model

JTS supports the concept of an explicit precision model for specifying the coordinates of Geometrys. It supports two types of Precision Model, Fixed and Floating

Fixed	Coordinates are represented as points on a grid with uniform spacing. (This can be assumed to be the integer grid, with the use of appropriate scale and offset factors). Computed coordinates are rounded to this grid.
Floating	Coordinates are represented as floating-point numbers. Computed coordinates may have more digits of precision than the input values (up the maximum allowed by the finite floating-point representation).

Implementing a precision model specifies how JTS is to correctly handle constructed points. It also allows control over how the algorithms handle robustness issues.

Constructed Points and Dimensional Collapse

Geometries computed by spatial analysis methods may contain constructed points which are not present in the input Geometries. These new points arise from intersections between line segments in the edges of the input Geometries. In the general case it is not possible to represent constructed points exactly. This is due to the fact that the coordinates of an intersection point may contain twice as many bits of precision as the coordinates of the input line segments. In order to represent these constructed points explicitly, JTS must truncate them to fit the Precision Model.

Unfortunately, truncating coordinates moves them slightly. Line segments which would not be coincident in the exact result may become coincident in the truncated representation. For Line-Area combinations, this can lead to dimensional collapses , which are situations where a computed element has a lower dimension than it would in the exact result.

JTS handles dimensional collapses as gracefully as possible, by forming the lower-dimension Geometry resulting from the collapse. For instance, an Area-Area overlay with a dimensional collapse would return a Line or Point Geometry as an element of the result, as seen in the following diagram.

Example of a dimensional collapse in the evaluation of A.difference(B).
(The square is 1 unit tall)

Robustness in JTS

Geometric 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 the numerical errors can propagate into the combinatorial computations and result in complete failure of the algorithm.

There are many approaches to dealing with the problem of robustness in geometric computation. Not surprisingly, most robust algorithms are substantially more complex and less performant than the non-robust versions. JTS attempts to deal with the problem of robustness in two ways:

The important fundamental geometric algorithms (such as Line Orientation, Line Intersection and the Point-In-Polygon test) have been implemented using robust algorithms. In particular, the implementation of several algorithms relies on the robust determinant evaluation presented in Avnaim et al.
The algorithms used to implement the SFS predicates and functions have been developed to eliminate or minimize robustness problems. The binary predicate algorithm is completely robust. The spatial overlay and buffer algorithms are non-robust, but should return correct answers in the majority of cases.