Skip navigation links
org.locationtech.jts:jts-core 1.20.0

Package org.locationtech.jts.operation.relateng

Provides classes to implement the RelateNG algorithm computes topological relationships of Geometrys.

See: Description

Package org.locationtech.jts.operation.relateng Description

Provides classes to implement the RelateNG algorithm computes topological relationships of Geometrys. Topology is evaluated based on the Dimensionally-Extended 9-Intersection Model (DE-9IM). The RelateNG class supports computing the value of boolean topological predicates. Standard OGC named predicates are provided by the RelatePredicate functions. Custom relationships can be specified via testing against DE-9IM matrix patterns (see IntersectionMatrixPattern for examples). The full DE-9IM IntersectionMatrix can also be computed.

The algorithm has the following capabilities:

  1. Efficient short-circuited evaluation of topological predicates (including matching custom DE-9IM patterns)
  2. Optimized repeated evaluation of predicates against a single geometry via cached spatial indexes (AKA "prepared mode")
  3. Robust computation (since only point-local topology is required, so that invalid geometry topology cannot cause failures)
  4. Support for mixed-type and overlapping GeometryCollection inputs (using union semantics)
  5. Support for BoundaryNodeRule
RelateNG operates in 2D only; it ignores any Z ordinates.

Optimized Short-Circuited Evaluation

The RelateNG algorithm uses strategies to optimize the evaluation of topological predicates, including matching DE-9IM matrix patterns. These include fast tests of dimensions and envelopes, and short-circuited evaluation once the predicate value is known (either satisfied or failed) based on the value of matrix entries. Named predicates used explicit strategy code. DE-9IM matrix pattern matching are short-circuited where possible based on analysis of the pattern matrix entries. Spatial indexes are used to optimize topological computations (such as locating points in geometry elements, and analyzing the topological relationship between geometry edges).

Execution Modes

RelateNG provides two execution modes for evaluating predicates:

Robustness

RelateNG provides robust evaluation of topological relationships, up to the precision of double-precision computation. It computes topological relationships in the locality of discrete points, without constructing a full topology graph of the inputs. This means that invalid input geometries or numerical round-off do not cause exceptions (although they may return incorrect answers). However, it is necessary to node some inputs together (in particular, linear elements) in order to provide consistent evaluation of the topological structure.

GeometryCollection Handling

GeometryCollections may contain geometries of different dimensions, nested to any level. The element geometries may overlap in any combination. The OGC specification did not provide a definition for the topology of GeometryCollections, or how they behave under the DE-9IM model. RelateNG defines the topology for arbitrary collections of geometries using "union semantics". This is specified as:

Zero-length LineString Handling

Zero-length LineStrings are handled as topologically identical to a Point at the same coordinate.

Package Specification

Skip navigation links
org.locationtech.jts:jts-core 1.20.0

Copyright © 2024. All rights reserved.