A. General

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:

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

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.

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 set

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:

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).

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.

TBD

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

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...₂, 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:

• the result is only used to obtain derived quantities such as area or length
• the result is only used for visualization purposes
• the result vertices do not need to fully match the input

• The best way is to ensure that the original source of the input geometries provides only as much precision as is really required. If this is not possible to enforce, then it will be necessary to reduce the precision of the geometries once they are created.
• The SimpleGeometryPrecisionReducer class can be used to reduce the precision of geometry coordinates. Note that this class operates in a pointwise fashion, and thus in some situations may not maintain correct polygonal topology. If this is an issue, see the following item.
• The GeometryPrecisionReducer reduces geometry coordinate precision, and attempts to detect and correct invalid polygonal topology resulting from precision reduction.

E. Algorithms

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:

• E. Chan, J. Ng. A General and Efficient Implementation of Geometric Operators and Predicates; Proceedings of the 5th International Symposium on Advances in Spatial Databases, 1997.
• Schutte, Klamer. An edge-labeling approach to concave polygon clipping; submitted to ACM Transactions on Graphics, 1995.
• M. V. Leonov and A. G. Nikitin. An Efficient Algorithm for a Closed Set of Boolean Operations on Polygonal Regions in the Plane (draft English translation). A. P. Ershov Institute of Informatics Systems, Preprint 46, 1997.
• Vatti, B.R. A Generic Solution to Polygon Clipping; Communications of the ACM, 35(7), July 1992, pp.56-63.

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:

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.

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:

• Compute polygon.buffer(0). The buffer operation is fairly insensitive to topological invalidity, and the act of computing the buffer can often resolve minor issues such as self-intersecting rings. However, in some situations the computed result may not be what is desired (i.e. the buffer operation may be "confused" by certain topologies, and fail to produce a result which is close to the original. An example where this can happen is a "bow-tie: or "figure-8" polygon, with one very small lobe and one large one. Depending on the orientations of the lobes, the buffer(0) operation may keep the small lobe and discard the "valid" large lobe).
• If holes are overlapping the shell or other holes, create individual polygons from the shell and all the holes, and then subtract the holes from the shell using Geometry.difference().