jts

Robustness

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

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

The Java Topology Suite (JTS) is a Java API that implements a core set of spatial data operations using an explicit precision model and robust geometric algorithms. JTS is intended to be used in the development of applications that support the validation, cleaning, integration and querying of spatial datasets.

JTS attempts to implement the OpenGIS Simple Features Specification (SFS) as accurately as possible. In some cases the SFS is unclear or omits a specification; in this case JTS attempts to choose a reasonable and consistent alternative. Differences from and elaborations of the SFS are documented in this specification.

Package Specification

• Java Topology Suite Technical Specifications
• OpenGIS Simple Features Specification for SQL

The Java Topology Suite (JTS) is a Java API that implements a core set of spatial data operations using an explicit precision model and robust geometric algorithms. JTS is intended to be used in the development of applications that support the validation, cleaning, integration and querying of spatial datasets.

JTS attempts to implement the OpenGIS Simple Features Specification (SFS) as accurately as possible. In some cases the SFS is unclear or omits a specification; in this case JTS attempts to choose a reasonable and consistent alternative. Differences from and elaborations of the SFS are documented in this specification.

Package Specification

• Java Topology Suite Technical Specifications
• OpenGIS Simple Features Specification for SQL

The Java Topology Suite (JTS) is a Java API that implements a core set of spatial data operations using an explicit precision model and robust geometric algorithms. JTS is intended to be used in the development of applications that support the validation, cleaning, integration and querying of spatial datasets.

JTS attempts to implement the OpenGIS Simple Features Specification (SFS) as accurately as possible. In some cases the SFS is unclear or omits a specification; in this case JTS attempts to choose a reasonable and consistent alternative. Differences from and elaborations of the SFS are documented in this specification.

Package Specification

• Java Topology Suite Technical Specifications
• OpenGIS Simple Features Specification for SQL

Linear Referencing

• Linear Location - a linear location is a triple (component index, segment index, segment fraction) which precisely specifies a point on a linear geometry. It allows for efficient mapping of the index value to actual coordinate values.
• Length - the natural concept of using the length along the geometry to specify a position.

  Package Specification

  • Java Topology Suite Technical Specifications
  • OpenGIS Simple Features Specification for SQL

The Overlay Algorithm is used in spatial analysis methods for computing set-theoretic operations (boolean combinations) of input {@link Geometry}s. The algorithm for computing the overlay uses the intersection operations supported by topology graphs. To compute an overlay it is necessary to explicitly compute the resultant graph formed by the computed intersections.

The algorithm to compute a set-theoretic spatial analysis method has the following steps:

• Build topology graphs of the two input geometries. For each geometry all self-intersection nodes are computed and added to the graph.
• Compute nodes for all intersections between edges and nodes of the graphs.
• Compute the labeling for the computed nodes by merging the labels from the input graphs.
• Compute new edges between the compute intersection nodes. Label the edges appropriately.
• Build the resultant graph from the new nodes and edges.
• Compute the labeling for isolated components of the graph. Add the isolated components to the resultant graph.
• Compute the result of the boolean combination by selecting the node and edges with the appropriate labels. Polygonize areas and sew linear geometries together.

Package Specification

• Java Topology Suite Technical Specifications
• OpenGIS Simple Features Specification for SQL

The relate algorithm computes the IntersectionMatrix describing the relationship of two Geometrys. The algorithm for computing relate uses the intersection operations supported by topology graphs. Although the relate result depends on the resultant graph formed by the computed intersections, there is no need to explicitly compute the entire graph. It is sufficient to compute the local structure of the graph at each intersection node.

The algorithm to compute relate has the following steps:

• Build topology graphs of the two input geometries. For each geometry all self-intersection nodes are computed and added to the graph.
• Compute nodes for all intersections between edges and nodes of the graphs.
• Compute the labeling for the computed nodes by merging the labels from the input graphs.
• Compute the labeling for isolated components of the graph (see below)
• Compute the IntersectionMatrix from the labels on the nodes and edges.

Labeling isolated components

Package Specification

• Java Topology Suite Technical Specifications
• OpenGIS Simple Features Specification for SQL