Namespace NetTopologySuite.Noding.Snapround

Contains classes to implement the Snap Rounding algorithm for noding linestrings.

Classes

GeometryNoder

Nodes the linework in a list of Geometrys using Snap-Rounding to a given PrecisionModel.

The input coordinates do not need to be rounded to the precision model. All output coordinates are rounded to the precision model.

This class does not dissolve the output linework, so there may be duplicate linestrings in the output. Subsequent processing (e.g. polygonization) may require the linework to be unique. Using UnaryUnion is one way to do this (although this is an inefficient approach).

HotPixel

Implements a "hot pixel" as used in the Snap Rounding algorithm. A hot pixel is a square region centred on the rounded valud of the coordinate given, and of width equal to the size of the scale factor. It is a partially open region, which contains the interior of the tolerance square and the boundary minus the top and right segments. This ensures that every point of the space lies in a unique hot pixel. It also matches the rounding semantics for numbers.

The hot pixel operations are all computed in the integer domain to avoid rounding problems.

Hot Pixels support being marked as nodes. This is used to prevent introducing nodes at line vertices which do not have other lines snapped to them.

MCIndexPointSnapper

"Snaps" all ISegmentStrings in a ISpatialIndex<T> containing MonotoneChains to a given HotPixel.

MCIndexPointSnapper.HotPixelSnapAction

MCIndexSnapRounder

Uses Snap Rounding to compute a rounded, fully noded arrangement from a set of ISegmentStrings. Implements the Snap Rounding technique described in papers by Hobby, Guibas and Marimont, and Goodrich et al. Snap Rounding assumes that all vertices lie on a uniform grid; hence the precision model of the input must be fixed precision, and all the input vertices must be rounded to that precision.

This implementation uses a monotone chains and a spatial index to speed up the intersection tests.

KNOWN BUGS

This implementation is not fully robust. instead.

SimpleSnapRounder

Uses Snap Rounding to compute a rounded, fully noded arrangement from a set of ISegmentStrings.

Implements the Snap Rounding technique described in the papers by Hobby, Guibas & Marimont, and Goodrich et al. Snap Rounding enforces that all vertices lie on a uniform grid, which is determined by the provided PrecisionModel. Input vertices do not have to be rounded to this grid; this will be done during the snap-rounding process.

This implementation uses simple iteration over the line segments. This is not an efficient approach for large sets of segments. This implementation appears to be fully robust using an integer precision model. It will function with non-integer precision models, but the results are not 100% guaranteed to be correctly noded.

SnapRoundingIntersectionAdder

Finds intersections between line segments which will be snap-rounded, and adds them as nodes to the segments.

Intersections are detected and computed using full precision. Snapping takes place in a subsequent phase.

The intersection points are recorded, so that HotPixels can be created for them.

To avoid robustness issues with vertices which lie very close to line segments a heuristic is used: nodes are created if a vertex lies within a tolerance distance of the interior of a segment. The tolerance distance is chosen to be significantly below the snap-rounding grid size. This has empirically proven to eliminate noding failures.

SnapRoundingNoder

Uses Snap Rounding to compute a rounded, fully noded arrangement from a set of ISegmentStrings, in a performant way, and avoiding unnecessary noding.

Implements the Snap Rounding technique described in the papers by Hobby, Guibas & Marimont, and Goodrich et al. Snap Rounding enforces that all output vertices lie on a uniform grid, which is determined by the provided PrecisionModel.

Input vertices do not have to be rounded to the grid beforehand; this is done during the snap-rounding process. In fact, rounding cannot be done a priori, since rounding vertices by themselves can distort the rounded topology of the arrangement (i.e. by moving segments away from hot pixels that would otherwise intersect them, or by moving vertices across segments).

To minimize the number of introduced nodes, the Snap-Rounding Noder avoids creating nodes at edge vertices if there is no intersection or snap at that location. However, if two different input edges contain identical segments, each of the segment vertices will be noded. This still provides fully-noded output. This is the same behaviour provided by other noders, such as MCIndexNoder and SnappingNoder.