Package org.locationtech.jts.operation.overlayng
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 Geometry
s.
The OverlayNG
class provides the standard Simple Features
boolean set-theoretic overlay operations.
These are:
- Intersection - all points which lie in both geometries
- Union - all points which lie in at least one geometry
- Difference - all points which lie in the first geometry but not the second
- Symmetric Difference - all points which lie in one geometry but not both
Additional operations include:
UnaryUnionNG
unions collections of geometries in an efficient wayCoverageUnion
provides enhanced performance for unioning valid polygonal and lineal coveragesPrecisionReducer
allows reducing the precision of a geometry in a topologically-valid way
Semantics
The requirements for overlay input are:- Input geometries may have different dimension.
- Collections must be homogeneous (all elements must have the same dimension).
- In general, inputs must be valid geometries.
- However, polygonal inputs may contain the following two kinds of "mild" invalid topology:
- rings which self-touch at discrete points (sometimes called inverted shells and exverted holes).
- rings which touch along line segments (i.e. topology collapse).
The semantics of overlay output are:
- Results are always valid geometries.
In particular, result
MultiPolygon
s are valid. - Repeated vertices are removed.
- Linear results include all nodes (endpoints) present in the input.
In some cases more nodes will be present.
(If merged lines are required see
LineMerger
.) - Polygon edges which undergo topology collapse to lines (due to rounding or snapping) are included in the result. This means that all operations may produce a heterogeneous result. Usually this only occurs when using a fixed-precision model, but it can happen due to snapping performed to improve robustness.
- The
intersection
operation result includes all components of the intersection for geometries which intersect in components of the same and/or lower dimension. - The
difference
operation produces a homogeneous result if no topology collapses are present. In this case the result dimension is equal to that of the left-hand operand. - The
union
andsymmetric difference
operations may produce a heterogeneous result if the inputs are of mixed dimension. - Homogeneous results are output as
Multi
geometries. - Heterogeneous results are output as a
GeometryCollection
containing a set of atomic geometries. (This provides backwards compatibility with the original overlay implementation. However, it loses the information that the polygonal results have validMultiPolygon
topology.) - Empty results are atomic
EMPTY
geometries of dimension appropriate to the operation. - As far as possible, results preserve the order and direction of the inputs. For instance, a MultiLineString intersection with a Polygon will have resultants which are in the same order and have the same direction as the input lines (assuming the input lines are disjoint). If an input line is split into two or more parts, they are ordered in the direction of occurence along their parent line.
Features
Functionality
- Precision Model - operations are performed using a defined precision model (finite or floating)
- Robust Computation - provides fully robust computation when an appropriate noder is used
- Performance optimizations - including:
- Short-circuiting for disjoint input envelopes
- Reduction of input segment count via clipping / limiting to overlap envelope
- Optimizations can be disabled if required (e.g. for testing or performance evaluation)
- Pluggable Noding - allows using different noders to change characteristics of performance and accuracy
- Precision Reduction - in a topologically correct way. Implemented by unioning a single input with an empty geometry
- Topology Correction / Conversion - handles certain kinds of polygonal inputs which are invalid
- Fast Coverage Union - of valid polygonal and linear coverages
Pluggable Noding
The noding phase of overlay uses aNoder
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:
MCIndexNoder
- a fast full-precision noder, which however may not produce a valid noding in some situations. Should be combined with aValidatingNoder
wrapper to detect noding failures.SnappingNoder
- a robust full-precision noderSnapRoundingNoder
- a noder which enforces a supplied fixed precision model by snapping vertices and intersections to a gridSegmentExtractingNoder
- a special-purpose noder that provides very fast noding for valid polygonal coverages. Requires node-clean input to operate correctly.
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:- rings which self-touch at discrete points (sometimes called inverted shells and exverted holes).
- rings which touch along line segments (i.e. topology collapse).
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
- Defines a simple, full-featured topology model, with clear semantics. The topology model incorporates handling topology collapse, which is essential for snapping and fixed-precision noding.
- Uses a simple topology graph data structure (based on the winged edge pattern).
- Decouples noding and topology-build phases. This makes the code clearer, and makes it possible to allow supplying alternate implementations and semantics for each phase.
- All optimizations are implemented internally, so that clients do not have to add checks such as envelope overlap.
Algorithm
For non-point inputs the overlay algorithm is:
- Check for empty input geometries, and return a result appropriate for the specified operation
- Extract linework and points from input geometries, with topology location information
- (If optimization enabled) Apply overlap envelope optimizations:
- For Intersection, check if the input envelopes are disjoint (using an envelope expansion adjustment to account for the precision grid).
- For Intersection and Difference, clip or limit the linework of the input geometries to the overlap envelope.
- If the optimized linework is empty, return an empty result of appropriate type.
- 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).
- 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
- Build a fully-labelled topology graph. This includes:
- Create a graph structure on the noded, merged edges
- Propagate topology locations around nodes in the graph
- 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).
- If result is empty return an empty geometry of appropriate type
- Generate the result geometry from the labelled graph:
- Build result polygons
- Mark edges which should be included in the result areas
- Link maximal rings together
- Convert maximal rings to minimal (valid) rings
- Determine nesting of holes
- Construct result polygons
- Build result linework
- Mark edges to be included in the result lines
- Extract edges as lines
- Build result points (certain intersection situations only)
- Output points occur where the inputs touch at single points
- Collect result elements into the result geometry
- Build result polygons
Package Specification
-
Class Summary Class Description CoverageUnion Unions a valid coverage of polygons or lines in an efficient way.FastOverlayFilter LineLimiter Limits the segments in a list of segments to those which intersect an envelope.OverlayNG Computes the geometric overlay of twoGeometry
s, using an explicit precision model to allow robust computation.OverlayNGRobust Performs an overlay operation usingOverlayNG
, providing full robustness by using a series of increasingly robust (but slower) noding strategies.PrecisionReducer Functions to reduce the precision of a geometry by rounding it to a given precision model.PrecisionUtil Functions for computing precision model scale factors that ensure robust geometry operations.RingClipper Clips rings of points to a rectangle.UnaryUnionNG Unions a geometry or collection of geometries in an efficient way, usingOverlayNG
to ensure robust computation.