B. Design and Structure
C. Geometry Predicates
D. Robustness & Precision
F. Geodetic Operations
G. Geometry Cleaning and Conflation
D. Robustness & Precision
F. Geodetic Operations
G. Geometry Cleaning and Conflation
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.
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.
JTS intentionally allows topologically invalid geometries to be constructed for the following reasons:
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.
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.
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.
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.
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.
According to the SFS 1.1, section 2.1.3:
The boundary of a Point is the empty setSince 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
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.
This is due to the fact that GeometryCollections can have arbitrarily complex topology
(and in particular, polygons can overlap). Because of this computing predicates in the general case
requires the equivalent of a full overlay to be carried out.
This requires more complex code, and would be difficult to implement fully robustly.
(However, more specific predicates such as
intersects could be computed efficiently and robustly.
It is hoped to enhance JTS to handle these kinds of cases. )
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:
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.
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.
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.
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.
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) = Ato 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.
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).
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:
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:
Yes. See the Refractions Research Skeletonizer
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 has poor performance. A better approach is the following:
JTS provides several ways of noding lines. They vary in terms of simplicity, peformance, robustness and flexibility. Options are:
SegmentStrings, without dissolving
Represent the set of lines as a
MultiLineString, and use the
true if and only if the only intersections
between the lines occur at their endpoints.
Represent the set of lines as a
MultiLineString, and use the
This omputes the boundary as the set of line endpoints which occur more than once.
intersectionmethod 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
Note that the SFS does not specify the precise semantics for the return value from overlay operations, so the JTS design chose to provide a more inclusive semantics.
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.
A geographically-accurate range circle is a shape on a spheroid modelling the surface of the Earth which is the boundary of the set of 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 an ellipse. 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.
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:
buffer(0)operation may keep the small lobe and discard the "valid" large lobe).