Namespace NetTopologySuite.Noding

Classes to compute nodings for arrangements of line segments and line segment sequences.

Classes

BasicSegmentString

Represents a read-only list of contiguous line segments. This can be used for detection of intersections or nodes. ISegmentStrings can carry a context object, which is useful for preserving topological or parentage information.

If adding nodes is required use NodedSegmentString.

BoundaryChainNoder

A noder which extracts chains of boundary segments as {@link SegmentString}s. Boundary segments are those which are not duplicated in the input. The segment strings are extracted in a way that maximises their length, and minimizes the total number of edges. This produces the most efficient topological graph structure.

Segments which are not on the boundary are those which have an identical segment in another polygon ring.

This enables fast overlay of polygonal coverages in {@link CoverageUnion}. This noder is faster than {@link SegmentExtractingNoder} and {@link BoundarySegmentNoder}.

No precision reduction is carried out. If that is required, another noder must be used (such as a snap-rounding noder), or the input must be precision-reduced beforehand.

BoundarySegmentNoder

A noder which extracts boundary line segments as ISegmentString. Boundary segments are those which are not duplicated in the input. It is appropriate for use with valid polygonal coverages.

No precision reduction is carried out. If that is required, another noder must be used (such as a snap-rounding noder), or the input must be precision-reduced beforehand.

FastNodingValidator

Validates that a collection of ISegmentStrings is correctly noded. Indexing is used to improve performance.

FastSegmentSetIntersectionFinder

Finds if two sets of ISegmentStrings intersect.

InteriorIntersectionFinderAdder

Finds interior intersections between line segments in NodedSegmentStrings, and adds them as nodes using AddIntersection(LineIntersector, Int32, Int32, Int32). This class is used primarily for Snap-Rounding. For general-purpose noding, use IntersectionAdder.

IntersectionAdder

Computes the possible intersections between two line segments in ISegmentStrings and adds them to each string using AddIntersection(LineIntersector, Int32, Int32, Int32).

IteratedNoder

Nodes a set of ISegmentStrings completely. The set of ISegmentStrings is fully noded; i.e. noding is repeated until no further intersections are detected.

Iterated noding using a Floating precision model is not guaranteed to converge, due to round off error. This problem is detected and an exception is thrown. Clients can choose to rerun the noding using a lower precision model.

MCIndexNoder

Nodes a set of ISegmentStrings using a index based on MonotoneChains and a ISpatialIndex<T>. The ISpatialIndex<T> used should be something that supports envelope (range) queries efficiently (such as a Quadtree" or STRtree<TItem>.

The noder supports using an overlap tolerance distance. This allows determining segment intersection using a buffer for uses involving snapping with a distance tolerance.

MCIndexNoder.SegmentOverlapAction

MCIndexSegmentSetMutualIntersector

Intersects two sets of ISegmentStrings using a index based on MonotoneChains and a ISpatialIndex<T>.

Thread-safe and immutable.

MCIndexSegmentSetMutualIntersector.SegmentOverlapAction

Segment overlap action class

NodedSegmentString

Represents a list of contiguous line segments, and supports noding the segments. The line segments are represented by an array of Coordinates. Intended to optimize the noding of contiguous segments by reducing the number of allocated objects. ISegmentStrings can carry a context object, which is useful for preserving topological or parentage information. All noded substrings are initialized with the same context object.

For read-only applications use BasicSegmentString, which is (slightly)more lightweight.

NodingIntersectionFinder

Finds non-noded intersections in a set of {@link SegmentString}s, if any exist.

Non-noded intersections include:

The finder can be limited to finding only interior intersections by setting InteriorIntersectionsOnly.

By default only the first intersection is found, but all can be found by setting FindAllIntersections.

NodingValidator

Validates that a collection of ISegmentStrings is correctly noded. Throws an appropriate exception if an noding error is found.

Octant

Methods for computing and working with Octants of the Cartesian plane.

OrientedCoordinateArray

Allows comparing Coordinate arrays in an orientation-independent way.

ScaledNoder

Wraps a INoder and transforms its input into the integer domain. This is intended for use with Snap-Rounding noders, which typically are only intended to work in the integer domain.

Clients should be aware that rescaling can involve loss of precision, which can cause zero-length line segments to be created. These in turn can cause problems when used to build a planar graph. This situation should be checked for and collapsed segments removed if necessary.

SegmentExtractingNoder

A noder which extracts all line segments as ISegmentStrings. This enables fast overlay of geometries which are known to be already fully noded. In particular, it provides fast union of polygonal and linear coverages. Unioning a noded set of lines is an effective way to perform line merging and line dissolving.

No precision reduction is carried out. If that is required, another noder must be used (such as a snap-rounding noder), or the input must be precision-reduced beforehand.

SegmentIntersectionDetector

Detects and records an intersection between two ISegmentStrings, if one exists. Only a single intersection is recorded.

SegmentNode

Represents an intersection point between two ISegmentStrings.

SegmentNodeList

A list of the SegmentNodes present along a noded ISegmentString.

SegmentPointComparator

Implements a robust method of comparing the relative position of two points along the same segment. The coordinates are assumed to lie "near" the segment. This means that this algorithm will only return correct results if the input coordinates have the same precision and correspond to rounded values of exact coordinates lying on the segment.

SegmentStringDissolver

Dissolves a noded collection of ISegmentStrings to produce a set of merged linework with unique segments.

SegmentStringUtil

Utility methods for processing ISegmentStrings

SimpleNoder

Nodes a set of ISegmentStrings by performing a brute-force comparison of every segment to every other one. This has n^2 performance, so is too slow for use on large numbers of segments.

SimpleSegmentSetMutualIntersector

Intersects two sets of ISegmentStrings using brute-force comparison.

SinglePassNoder

Base class for INoders which make a single pass to find intersections. This allows using a custom ISegmentIntersector (which for instance may simply identify intersections, rather than insert them).

ValidatingNoder

A wrapper for INoders which validates the output arrangement is correctly noded. An arrangement of line segments is fully noded if there is no line segment which has another segment intersecting its interior. If the noding is not correct, a TopologyException is thrown with details of the first invalid location found.

Interfaces

INodableSegmentString

An interface for classes which support adding nodes to a segment string.

INoder

Computes all intersections between segments in a set of ISegmentStrings. Intersections found are represented as SegmentNodes and added to the ISegmentStrings in which they occur. As a final step in the noding a new set of segment strings split at the nodes may be returned.

ISegmentIntersector

Processes possible intersections detected by a INoder.

ISegmentSetMutualIntersector

An intersector for the red-blue intersection problem. In this class of line arrangement problem, two disjoint sets of linestrings are intersected.

Implementing classes must provide a way of supplying the base set of segment strings to test against (e.g. in the constructor, for straightforward thread-safety).

In order to allow optimizing processing, the following condition is assumed to hold for each set:

Implementations can take advantage of this fact to optimize processing (i.e. by avoiding testing for intersections between linestrings belonging to the same set).

ISegmentString

An interface for classes which represent a sequence of contiguous line segments. SegmentStrings can carry a context object, which is useful for preserving topological or parentage information.

SegmentStringDissolver.ISegmentStringMerger

A merging strategy which can be used to update the context data of ISegmentStrings which are merged during the dissolve process.

Enums

Octants

Octants in the Cartesian plane. Octants are numbered as follows:

\2|1/ 3 \|/ 0 ---+-- 4 /|\ 7 /5|6\

If line segments lie along a coordinate axis, the octant is the lower of the two possible values.