JTS Frequently Asked Questions

Last Update: November 21, 2012

A. General
1. What Java versions does JTS work with?

B. Design and Structure
1. How can I use JTS algorithms with a different geometry model ?
2. Why does JTS allow geometries to be constructed with invalid topology ?
3. What is the difference between a Point and a Coordinate ?
4. Does JTS support 3D operations?
5. What coordinate system and/or units does JTS use?
6. Why does JTS use clockwise as the canonical polygon exterior ring orientation?

C. Geometry Predicates
1. How are spatial predicates computed?
2. Why does relate(POINT(20 20), POINT(20 30), "FF0FFF0F2") = true ?
3. Why is the result of a predicate different in JTS than in another software application/library ?

D. Robustness & Precision
1. Why is a TopologyException thrown?
2. Why does the coordinate given in a TopologyException not appear in the input data?
3. What is a "robustness failure"?
4. What is a "topology collapse"?
5. What is the PrecisionModel for?
6. Why does JTS not enforce the specified PrecisionModel when creating new geometry?
7. Why do the overlay operations not obey the axioms of set theory?
8. Why does JTS report the intersection of LINESTRING (0 0, 5 3) and LINESTRING (0 0, 1.2 0.72) as a point rather than a line?
9. How can I prevent TopologyExceptions or incorrect results in overlay operations ?

E. Algorithms
1. Are there any references which describe the algorithms used in JTS?
2. Is there a skeletonization algorithm which works with JTS?
3. How can JTS be used to perform polygon overlay?
4. How can JTS be used to node a set of lines?
5. How can JTS be used to determine whether a set of lines is fully noded?
6. How can JTS be used to determine the intersection points in a fully-noded set of lines?
7. Why does the JTS intersection method sometimes return a geometry collection of mixed dimension?

F. Geodetic Operations
1. Does JTS support computation on the geodetic spheroid ?
2. Can JTS be used to compute a geographically accurate range circle ?

G. Geometry Cleaning and Conflation
1. How can I correct the topology of a Polygon that JTS is reporting as invalid ?


A. General


A1. What Java versions does JTS work with?

JTS is developed using Java 1.4.2. It should work with all newer versions. With a small amount of work the library can be made to work with almost all previous Java versions as well.

B. Design and Structure


B1. How can I use JTS algorithms with a different geometry model?

The solution to this is to use Facade objects which wrap the non-JTS geometry model classes. In order to avoid having to create and copy large numbers of Coordinate objects, JTS provides the CoordinateSequence interface. A CoordinateSequence-based adapter can be written for whatever structure the foreign model uses to represent sequences of points. JTS Geometry objects will still need to be created to represent the structure of the geometries containing the points, but these are relatively lightweight in comparison.


B2. Why does JTS allow geometries to be constructed with invalid topology?

JTS intentionally allows topologically invalid geometries to be constructed for the following reasons:

  1. It allows a wider set of geometry to be read, stored and written from external data sources
  2. It allows geometries to be constructed and then validated
  3. It avoids the costly overhead of validating topology every time a geometry is constructed

B3. What is the difference between a Point and a Coordinate?

A Coordinate is a relatively simple class which represents a location on the Cartesian plane (optionally with an associated height value). Coordinates are usually treated as mutable objects, in order to simplify certain algorithms.

A Point is a subclass of Geometry that also represents a location on the Cartesian plane. It is a "heavy-weight" object (which for instance may contain an envelope) which support all methods that apply to Geometrys.


B4. Does JTS support 3D operations?

JTS does not provide support for true 3D geometry and operations. However, JTS does allow Coordinates to carry an elevation or Z value. This does not provide true 3D support, but does allow "2.5D" uses which are required in some geospatial applications.


B5. What coordinate system and/or units does JTS use?

JTS uses the implicit coordinate system of the input data. The only assumption it makes is that the coordinate system is infinite, planar and Euclidean (i.e. rectilinear and obeying the standard Euclidean distance metric). In the same way JTS does not specify any particular units for coordinates and geometries. Instead, the units are implicitly defined by the input data provided. This implies that in most cases input geometries to operations should be defined with the same coordinate system.


B6. Why does JTS use clockwise as the canonical polygon exterior ring orientation?

The first version of the OGC Simple Features for SQL specification did not define a canonical orientation for polygon rings. JTS was designed to meet this specification, and it was necessary to choose a canonical orientation. For historical reasons the choice was to have the canonical orientations be CW for exterior rings and CCW for interior rings. (This was not arbitrary - it followed the convention used in the ESRI SDE, one of the leading spatial database systems at the time). Note that as per the OGC SFS spec, JTS operations do not assume any particular orientation for the rings of input polygons.

Subsequent versions of the OGC specifications have chosen to specify an orientation convention, and unfortunately they chose the opposite one to JTS.

A future version of JTS might make the canonical orientation selectable by the user (on a library-wide basis). JTS never assumes any particular orientation for input, so this is mostly a matter of reversing output rings where required. Of course, the user can do this themselves if necessary.

C. Geometry Predicates


C1. How are spatial predicates computed?

The two input geometries are decomposed into labelled topology graphs (GeometryGraphs). The labels are on the nodes and edges of the graphs. They contain full information about the topology of the node/edge in the points/lines/polygons of the original geometry. The labelled topology graphs are merged. This includes merging the labels wherever there is common nodes or edges. For each geometry at each node, the label information is propagated to all edges incident on that node. The resulting relationship (Intersection Matrix, or IM) is determined by the merged label information at the nodes of the merged graph. The labelling of each node and its incident edges is inspected, and the topological relationship information it contributes is added to the overall IM. At the end of this process the IM has been completely determined.


C2. Why does relate(POINT(20 20), POINT(20 30), "FF0FFF0F2") = true?

According to the SFS 1.1, section 2.1.3:

The boundary of a Point is the empty set
Since points do not have boundaries, all the intersection matrix entries relating to the geometry boundaries are "F".

In some situations it is desirable to use a different definition for determining whether geometry endpoints are on their boundary. To support this, JTS provides the ability to specify a custom BoundaryNodeRule to the RelateOp class.


C3. Why is the result of a predicate different in JTS than in another software application/library ?

This is usually due to the fact that JTS predicates are computed exactly, using the full precision of the double-precision coordinates. Other geometry engines sometimes compute in lower precision, or round input coordinates, or use a tolerance when determining whether two lines intersect or cross.

As a specific example, in the following case:

A: POLYGON ((1368.62186660165 17722.3281808793, -1653 9287.5, 4038.14058906538 8613.02390521266, 1368.62186660165 17722.3281808793))

B: POLYGON ((-5846 9287.5, 7453 8380, 9082 16600, -6326.5 18842, -5846 9287.5))
JTS reports A.overlaps(B) = true, whereas another application reports false. The Overlaps result is correct - the bottom right point in the triangle B lies outside the quadrilateral A. This is demonstrated by intersecting the bottom edge of A
LINESTRING (-5846 9287.5, 7453 8380)
with B. The value of the intersection is a line segment:
LINESTRING (4038.140589065375 8613.02390521266, 4038.14058906538 8613.02390521266)
which shows that B crosses the boundary of A, and thus overlaps A.

D. Robustness & Precision


D1. Why is a TopologyException thrown?

TopologyExceptions are thrown when JTS encounters an inconsistency in the internal topology structures it creates to compute certain spatial operations (in particular, spatial predicates and overlay operations). These inconsistencies can happen for two reasons:

  1. Invalid input geometry. If input geometry is invalid according to the JTS (and OGC SFS) model, the results of operations is undefined, and may produce exceptions. Geometry validity can be checked by using the Geometry#isValid() method.
  2. Robustness failure due to floating-point roundoff errors. Floating-point errors can cause incorrect results to be computed for internal operations (such as computing point-line orientation, computing the intersection of two line segments, or computing the noded arrangement of a set of line segments).
Both of these situations can cause the topological properties of computed geometries to become inconsistent. When this issue is detected JTS throws a TopologyException.

In some rare cases, it is not possible to recognize an inconsistent topological situation. In these cases, no exception will be thrown, but the returned geometry will not correctly reflect the true result of the operation. JTS contains special checks to detect and prevent this from occurring for the overwhelming majority of inputs, however.

Unfortunately there is no guaranteed way of avoiding TopologyExceptions. However, a heuristic which often helps is to ensure that input geometry coordinates do not carry excessive precision. Instead of providing coordinates with a full 16 digits of precision (which usually far exceeds the actual accuracy of the input data), try reducing precision to a few decimal places. Of course, correct geometry topology must still be maintained. (This is primarily an issue for polygons, and can be tricky to do in some pathological cases). JTS provides the SimpleGeometryPrecisionReducer class to do a simple reduction in coordinate precision, although this class is not guaranteed to maintain correct geometry topology.


D2. Why does the coordinate given in a TopologyException not appear in the input data?

In order to reduce robustness problems during overlay operations, JTS/GEOS sometimes transforms geometry into a different coordinate system. The coordinates in a TopologyException message are presented in the working coordinate system, rather than the input coordinate system. This may not match the input data.


D3. What is a "robustness failure"?

A robustness failure is a situation in which a JTS operation on valid inputs either fails to complete (by throwing an exception) or produces an incorrect answer. This situation is usually caused by the unavoidable internal finite-precision arithmetic causing round-off error, which in turn causes invalid geometric topology to be created at some point during the evaluation of the algorithm.

The operations which are notably susceptible to robustness errors are the overlay operations (intersection, union, difference and symDifference). The input geometries which are most likely to trigger this behaviour are ones which contain a lot of precision (e.g. 14-16 significant digits of precision), and/or ones which contain line segments which are nearly, but not exactly, coincident.


D4. What is a "topology collapse"?

A topology collapse is a situation in which the finite-precision numerical representation used in JTS (Java's IEEE-754 double-precision floating point) is unable to accurately represent a particular geometric configuration exactly. This causes vertices to be slightly shifted from their mathematically exact position. In certain geometric configurations, this can result in the computed geometry being topologically invalid.

Typically this occurs in situations where polygon vertices are very close to other line segments. If the vertex is shifted slightly it may cross the line segment, resulting in a ring which self-intersects.


D5. What is the PrecisionModel for? TBD
D6. Why does JTS not enforce the specified PrecisionModel when creating new geometry?

TBD


D7. Why do the overlay operations not obey the axioms of set theory?

This question is sometimes framed as:

"When I intersect two geometries why is the result not contained in either of the originals?"

or: "When I union two geometries why does the result not contain either of the originals?"

or: "Why does A union (B difference A) != A ?"

The standard axioms of geometric set theory apply only in a theoretical realm in which all arithmetic is carried out exactly with infite precision real numbers. In this realm operations such as union and intersection are exact, which means that the usual axioms of commutativity and associativity hold. This allows equations such as

A union (B difference A) = A
to be correct.

Since JTS uses finite-precision floating point arithmetic it can only approximates this ideal. JTS uses double-precision floating point numbers to represent the coordinates of geometries (specifically, IEEE-754 double-precision floating point, which provides 56 bits of precision). This provides the illusion of computing using real numbers - but it's only an illusion. The finite representation of real numbers forces rounding to take place during arithmetic computation. This means that operations are not commutative or associative. This in turn has the effect that geometric axioms are not maintained. (For the same reason, as is well known and documented finite-precision floating-point computation does not fully obey the axioms of arithmetic.)

Furthermore, JTS contains code which adjusts input geometries in small ways in order to try and prevent robustness errors from occuring. These minor perturbations may also result in computed results which do not necessarily obey the set theory axioms.

However, a major JTS design goal is that the output of geometric operations is "close" to the theoretically correct result (using some small epsilon of tolerance and a suitable geometric distance metric.) This is the best that can be achieved by a finite-precision implementation. This goal is generally met by the JTS algorithms. Moreover, the precision of JTS geometric operations is almost always much greater than the inherent accuracy of the input data.


D8. Why does JTS report the intersection of LINESTRING (0 0, 5 3) and LINESTRING (0 0, 1.2 0.72) as a point rather than a line?

This is a specific case of D7 above. It is interesting because it shows how very simple geometric cases can reveal the limitations of finite-precision binary floating-point arithmetic. In this case, the mathematical point (1.2 0.72) lies exactly on the line LINESTRING (0 0, 5 3), so the the true mathematical value of the intersection is LINESTRING (0 0, 1.2, 0.72). However, JTS computes the intersection as POINT(0 0).

The reason for this is that the values 1.2 and 0.72 cannot be represented precisely as binary numbers. For instance, the binary value of 1.2 is the infinite repeating value 1.001100110011...2, and similarly for 0.72. So JTS is computing the intersection using the truncated approximation to the point - which does NOT lie on the line (0 0, 5 3). Thus the intersection is reported (correctly, as far as JTS can determine) as POINT (0 0).


D9. How can I prevent TopologyExceptions or incorrect results in overlay operations ?

TopologyExceptions and incorrect results encountered during overlay computations are symptoms of robustness issues. Robustness issues are caused by the limitations of using finite-precision numerical values in geometric algorithms. During overlay this problem is often caused by intersecting line segments which are nearly parallel. This often happens when overlaying geometries which share similar sections of linework.

Currently the surest way to prevent robustness issues is to limit the numerical precision of the input geometries to something less than the available 16 digits. To be safe, the precision of the input geometry coordinates should be no more than 14 decimal digits (and possibly as few as 10 or 12). This is still plenty of precision to represent the accuracy of real-world data.

Reducing the precision of the input data means that result vertices will not perfectly match the input ones. Thus this technique is particularly useful in situations where it is not necessary to perfectly preserve vertex-to-vertex faithfulness to the source geometry. Example use cases are:

Coordinate precision can be controlled in several ways: Another heuristic technique that can be used is to perturb the vertices of one or both geometries by a small amount. This can be done by translating by a small vector, or rotating by a small angle around the centroid.

E. Algorithms


E1. Are there any references which describe the algorithms used in JTS?

Many of the details of JTS algorithms (particularly in the areas of performance and robustness) are unique to JTS. However, the design of the algorithms for computing spatial predicates and spatial overlay follow a generally-accepted strategy for computing with 2-dimensional planar linear topological structures. Some papers which present similar approaches are:


E2. Is there a skeletonization algorithm which works with JTS?

Yes. See the Refractions Research Skeletonizer


E3. How can JTS be used to perform polygon coverage overlay?

The overlay operations currently in JTS are designed to work on pairs of geometries. Although they can be used to perform polygon coverage overlay, this approach is complex and non-performant. A better approach is the following:


E4. How can JTS be used to node a set of lines?

JTS provides several ways of noding lines. They vary in terms of simplicity, peformance, robustness and flexibility. Options are:


E5. How can JTS be used to determine whether a set of lines is fully noded?

Represent the set of lines as a MultiLineString, and use the IsSimpleOp with the BoundaryNodeRule.ENDPOINT_BOUNDARY_RULE. This reports true if and only if the only intersections between the lines occur at their endpoints.


E6. How can JTS be used to determine the intersection points in a fully-noded set of lines?

Represent the set of lines as a MultiLineString, and use the BoundaryOp with the BoundaryNodeRule.MULTIVALENT_ENDPOINT_BOUNDARY_RULE. This omputes the boundary as the set of line endpoints which occur more than once.


E7. Why does the JTS intersection method sometimes return a geometry collection of mixed dimension?

The intersection of two geometries may result in resultants of any dimension equal to or lower than the minimum dimension of the input. The overlay algorithm used in JTS can compute all such resultants. In order to preserve maximum information, JTS returns all resultants. If only the highest-dimension resultants are desired, it is possible to filter them out using utility classes such as PolygonExtracter or GeometryExtracter.

Note that the SFS does not specify the precise semantics for the return value from overlay operations.

F. Geodetic Operations


F1. Does JTS support computation on the geodetic spheroid ?

No. JTS currently assumes that geometries are defined in a Cartesian, planar, 2-dimensional space. Thus it cannot be used to compute accurate metrics, predicates or constructions on the geodetic spheroid which is usually used to model the surface of the Earth.

It is hoped to provide geodetic operations in a future version.


F2. Can JTS be used to compute a geographically accurate range circle?

A geographically accurate range circle is a shape on the ellipsoid modelling the surface of the Earth which represents all points which are a given distance from a fixed point on the spheroid. This is a more complicated shape than either a circle or even a sphere. In general JTS cannot compute this shape, since JTS assumes a Cartesian coordinate system (i.e. a two-dimensional plane extending infinitely in all directions). This is not a good approximation to the surface of the spheroid, except over very small distances. Computing a true range circle requires complex spherical mathematics as well as a richer coordinate system model. This is outside the current scope of JTS.

G. Geometry Cleaning and Conflation


G1. How can I correct the topology of a Polygon that JTS is reporting as invalid ?

There are many ways in which polygon topology can be invalid, and there are correspondingly various heuristic techniques that can be used to correct it: