Namespace NetTopologySuite.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
These operations are supported for all combinations of the basic geometry types and their homogeneous collections.
Additional operations include:
- UnaryUnion unions collections of geometries in an efficient way
- CoverageUnion provides enhanced performance for unioning valid polygonal and lineal coverages
- PrecisionReducer 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, resultMultiPolygon
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 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 NTS 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 a INoder 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 a ValidatingNoder wrapper to detect noding failures.
- SnappingNoder - a robust full-precision noder
- SnapRoundingNoder - a noder which enforces a supplied fixed precision model by snapping vertices and intersections to a grid
- ValidatingNoder - a wrapper which can be used to verify the noding prior to topology building
- SegmentExtractingNoder - requires node-clean input, and provides very fast noding
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).
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
- 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).
- Uses a simpler topology graph data structure (based on 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<./li>
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
- Construct node-to-node linework
- Build result points
- For intersection only, output point occur where the input touch at single points
- Collect result elements into the result geometry
- Build result polygons
Package Specification
- OpenGIS Simple Features Specification for SQL
Classes
CoverageUnion
Unions a valid coverage of polygons or lines in an efficient way.
A polygonal coverage is a collection of Polygons which satisfy the following conditions:
- Vector-cleanLine segments within the collection must either be identical or intersect only at endpoints.
- Non-overlappingNo two polygons may overlap. Equivalently, polygons must be interior-disjoint.
A linear coverage is a collection of LineStrings which satisfies the Vector-clean condition. Note that this does not require the LineStrings to be fully noded - i.e. they may contain coincident linework. Coincident line segments are dissolved by the union. Currently linear output is not merged (this may be added in a future release.)
No checking is done to determine whether the input is a valid coverage. This is because coverage validation involves segment intersection detection, which is much more expensive than the union phase. If the input is not a valid coverage then in some cases this will be detected during processing and a TopologyException is thrown. Otherwise, the computation will produce output, but it will be invalid.
Unioning a valid coverage implies that no new vertices are created. This means that a precision model does not need to be specified. The precision of the vertices in the output geometry is not changed.
LineLimiter
Limits the segments in a list of segments to those which intersect an envelope. This creates zero or more sections of the input segment sequences, containing only line segments which intersect the limit envelope. Segments are not clipped, since that can move line segments enough to alter topology, and it happens in the overlay in any case. This can substantially reduce the number of vertices which need to be processed during overlay.
This optimization is only applicable to Line geometries, since it does not maintain the closed topology of rings. Polygonal geometries are optimized using the RingClipper.
OverlayNG
Computes the geometric overlay of two Geometrys, using an explicit precision model to allow robust computation.
The overlay can be used to determine any of the following set-theoretic operations (boolean combinations) of the geometries:
- Intersectionall points which lie in both geometries
- Unionall points which lie in at least one geometry
- Differenceall points which lie in the first geometry but not the second
- SymDifferenceall points which lie in one geometry but not both
The precision model used for the computation can be supplied independent of the precision model of the input geometry. The main use for this is to allow using a fixed precision for geometry with a floating precision model. This does two things: ensures robust computation; and forces the output to be validly rounded to the precision model.
For fixed precision models noding is performed using a SnapRoundingNoder. This provides robust computation(as long as precision is limited to around 13 decimal digits).
For floating precision an MCIndexNoder is used. This is not fully robust, so can sometimes result in TopologyExceptions being thrown. For robust full-precision overlay see OverlayNGRobust.
A custom INoder can be supplied. This allows using a more performant noding strategy in specific cases, for instance in CoverageUnion.
Note: If a SnappingNoder is used it is best to specify a fairly small snap tolerance, since the intersection clipping optimization can interact with the snapping to alter the result.
Optionally the overlay computation can process using strict mode
(via StrictMode = true
).
In strict mode result semantics are:
- Lines and Points resulting from topology collapses are not included in the result
- Result geometry is homogeneous for the Intersection and Difference operations.
- Result geometry is homogeneous for the Union and SymDifference operations if the inputs have the same dimension
- Results are simpler
- Overlay operations are easily chainable without needing to remove lower-dimension elements
If a robustness error occurs, a TopologyException is thrown. These are usually caused by numerical rounding causing the noding output to not be fully noded. For robust computation with full-precision OverlayNGRobust can be used.
OverlayNGRobust
Performs an overlay operation using OverlayNG, increasing robustness by using a series of increasingly robust (but slower) noding strategies.
The noding strategies used are:
- A simple fast noder using Floating precision
- A SnappingNoder using an automatically-determined snap tolerance
- First snapping each geometry to itself, and then overlaying them wih a SnappingNoder
- The above two strategies are repeated with increasing snap tolerance, up to a limit
- Finally a SnapRoundingNoder is used with a automatically-determined scale factor.
This algorithm relies on each overlay operation execution throwing a TopologyException if it is unable to compute the overlay correctly. Generally this occurs because the noding phase does not produce a valid noding. This requires the use of a ValidatingNoder in order to check the results of using a floating noder.
PrecisionReducer
Functions to reduce the precision of a geometry by rounding it to a given precision model.
This class handles only polygonal and linear inputs. For full functionality GeometryPrecisionReducer.
PrecisionUtility
Functions for computing precision model scale factors that ensure robust geometry operations. In particular, these can be used to automatically determine appropriate scale factors for operations using limited-precision noding (such as OverlayNG).
WARNING: the inherentScale
and robustScale
functions can be very slow, due to the method used to determine
number of decimal places of a number.
These are not recommended for production use.
RingClipper
Clips a ring of points to an rectangle. Uses a variant of Cohen-Sutherland clipping.
In general the output is not topologically valid. In particular, the output may contain coincident non-noded line segments along the clip rectangle sides. However, the output is sufficiently well-structured that it can be used as input to the OverlayNG algorithm (which is able to process coincident linework due to the need to handle topology collapse under precision reduction).
Because of the likelihood of creating extraneous line segments along the clipping rectangle sides, this class is not suitable for clipping linestrings.
The clipping envelope should be generated using NetTopologySuite.Operation.OverlayNG.RobustClipEnvelopeComputer, to ensure that intersecting line segments are not perturbed by clipping. This is required to ensure that the overlay of the clipped geometry is robust and correct (i.e. the same as if clipping was not used).
UnaryUnionNG
Unions a collection of geometries in an efficient way, using OverlayNG to ensure robust computation.
This class is most useful for performing UnaryUnion using
a fixed-precision model.
For unary union using floating precision,
Union(Geometry) should be used.