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

Package org.locationtech.jts.operation.overlayng

Contains classes that perform vector overlay to compute boolean set-theoretic spatial functions.

See: Description

Package org.locationtech.jts.operation.overlayng Description

Contains classes that perform vector overlay to compute boolean set-theoretic spatial functions. Overlay operations are used in spatial analysis for computing set-theoretic operations (boolean combinations) of input Geometrys.

The OverlayNG class provides the standard Simple Features boolean set-theoretic overlay operations. These are:

These operations are supported for all combinations of the basic geometry types and their homogeneous collections.

Additional operations include:

Semantics

The requirements for overlay input are:

The semantics of overlay output are:

Features

Functionality

Pluggable Noding

The noding phase of overlay uses a Noder subclass. This is determine automatically based on the precision model of the input. Or it can be provided explicity, which allows changing characteristics of performance and robustness. Examples of relevant noders include:

Topology Correction / Conversion

As noted above, the overlay process can handle polygonal inputs which are invalid according to the OGC topology model in certain limited ways. These invalid conditions are: These invalidities are corrected during the overlay process.

Some of these invalidities are considered as valid in other geometry models. By peforming a self-overlay these inputs can be converted into the JTS OGC topological model.

Codebase

Algorithm

For non-point inputs the overlay algorithm is:

  1. Check for empty input geometries, and return a result appropriate for the specified operation
  2. Extract linework and points from input geometries, with topology location information
  3. (If optimization enabled) Apply overlap envelope optimizations:
    1. For Intersection, check if the input envelopes are disjoint (using an envelope expansion adjustment to account for the precision grid).
    2. For Intersection and Difference, clip or limit the linework of the input geometries to the overlap envelope.
    3. If the optimized linework is empty, return an empty result of appropriate type.
  4. Node the linework. For full robustness snap-rounding noding is used. Other kinds of noder can be used as well (for instance, the full-precision noding algorithm as the original overlay code).
  5. Merge noded edges. Coincident edges from the two input geometries are merged, along with their topological labelling. Topology collapses are detected in this step, and are flagged in the labelling so they can be handled appropriately duing result polygon extraction
  6. Build a fully-labelled topology graph. This includes:
    1. Create a graph structure on the noded, merged edges
    2. Propagate topology locations around nodes in the graph
    3. Label edges that have incomplete topology locations. These occur when edges from an input geometry are isolated (disjoint from the edges of the other geometry in the graph).
  7. If result is empty return an empty geometry of appropriate type
  8. Generate the result geometry from the labelled graph:
    1. Build result polygons
      1. Mark edges which should be included in the result areas
      2. Link maximal rings together
      3. Convert maximal rings to minimal (valid) rings
      4. Determine nesting of holes
      5. Construct result polygons
    2. Build result linework
      1. Mark edges to be included in the result lines
      2. Extract edges as lines
    3. Build result points (certain intersection situations only)
      1. Output points occur where the inputs touch at single points
    4. Collect result elements into the result geometry

Package Specification

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

Copyright © 2020. All rights reserved.