LineMerge and Polygonize
Two operations close the gap between lines and areas. LineMerge joins the paths of a polyline into longer paths where exactly two path ends meet; it is what Union of lines deliberately does not do (ADR 0005, ADR 0018: a path is cut where different input lines meet or end). Polygonize turns a polyline into the areas it encloses: every bounded face of the arrangement of the lines becomes a polygon, which together with Cut gives a complete subdivision of an area by lines. There is no public Node: Union of a polyline with itself (for example new[] { line }.UnionAll()) already nodes the lines at their crossings and removes duplicates, and Polygonize nodes internally.
German version: 0023-linemerge-und-polygonize.de.md
Consequences
- Placement:
LineMergein the static classConstructions(a geometric result through the factory, ADR 0019),PolygonizeinOverlays(it runs the overlay core), both inSpatialNET.Extensions, namespaceSpatialNET. For the package validation this is an addition only. LineMerge(this IPolyline2D line, bool directed = false, IGeometryFactory? factory = null)returnsIPolyline2D:- A node joins two paths only if exactly two path ends meet there (exact equality of X and Y, no tolerance; snap the data first if needed). A node where three or more ends meet, or where a single end lies, keeps its paths apart.
- A cycle of paths becomes one closed path. A path that already closes on itself stays as it is unless another path ends at its start point (then three ends meet and nothing is joined).
- Direction: by default a path is reversed where needed, and the direction of the first path in the input order prevails for the merged path. With
directed: true, two paths are joined only if the end of one is the start of the other, and exactly one path ends and exactly one path starts at the node. LineMergedoes not node. Crossing lines stay as they are; runUnionfirst for that.- Paths of fewer than two distinct points are dropped (they are no lines, as in
MakeValid, ADR 0020). Z and M of the coordinates are kept, at a joined vertex those of the earlier path. The result is deterministic: the paths come in the order in which their first path appears in the input.
Polygonize(this IPolyline2D line, IGeometryFactory? factory = null, double? gridSize = null)returnsIReadOnlyList<IPolygon2D>:- The lines are noded first, by snap rounding on the grid like
Union(gridSize, otherwisePrecision.DefaultGridSize, otherwise automatic, ADR 0005), so the vertices of the result lie on the grid. Overlapping duplicates collapse into one edge. - Every bounded face becomes a polygon of its own, in a flat list like the pieces of
Cut(ADR 0007): a face with the components of lines inside it as holes (shell counter-clockwise, holes clockwise, ADR 0003), an island in a hole a face of its own. Adjacent faces are separate polygons that share their edge. A face that touches itself at a vertex gives one polygon per lobe, so every polygon is valid. - Dangles (edges with a free end) and cut edges (edges that have the same face on both sides, for example a bridge between two parts) enclose no area and are dropped; a face is not cut by them. The unbounded outer face is never returned.
- A polyline that encloses nothing gives an empty list. The order of the list is deterministic.
- Z and M of the vertices follow the rules of the overlays (ADR 0005, ADR 0015).
- The result type is the plain list. A result with the dangles and cut edges (the JTS
Polygonizerhas them) can follow without a break.
- The lines are noded first, by snap rounding on the grid like
- Exceptions (ADR 0012):
ArgumentNullExceptionfornull,ArgumentOutOfRangeExceptionfor an invalidgridSize,InvalidOperationExceptionwithout a factory. Empty and degenerate lines never throw. - Implementation:
Polygonizebuilds the planar graph of the overlay core from the lines and assembles the polygons from all faces of it, the assembly that the overlays use for their results. A closed ring of lines needs no special case. - Tests (ADR 0008):
lineMergeandpolygonizefixtures with the mandatory tag catalog (exceptions justified in_catalog.json: lines have no rings, holes or nesting in the sense of the tags).LineMergeis compared with the NTSLineMerger(as sets of lines, each in a canonical direction and, for rings, a canonical start),Polygonizewith the NTSPolygonizeron the same lines noded by NTS (as sets of polygons by area and symmetric difference, since the nodes differ by the grid).- Property and stress tests: every polygon is valid; the faces do not overlap and their areas add up; every edge of a face belongs to at most two faces;
LineMergekeeps the total length and the set of vertices, never merges at a node of three ends, and merging twice changes nothing.
- Playground and documentation: descriptors for both (ADR 0011;
Polygonizeshows the list of faces likeCut), a section in the concept page for the overlays and the constructions, glossary entries.
Considered Options
- A public
Node(rejected:Unionof the line with itself does it, andPolygonizenodes internally; one more name for the same step) LineMergethat nodes first (rejected: merging and noding are different steps, and noding rounds to the grid, whichLineMergedoes not)LineMergewith a snap tolerance (rejected: exact equality is predictable; snapping is a separate, data-dependent step)- Directed merging only (rejected: most line data has no meaningful direction, and the undirected case is what JTS offers by default)
Polygonizereturning one multi-part polygon of all faces (rejected: adjacent faces would lose their identity; the flat list ofCutis the established form)- A result type with dangles, cut edges and invalid rings (rejected for now: nothing asks for it yet, and it can be added without a break)
Polygonizethat expects noded input and throws or returns garbage otherwise (rejected: noding on the grid is the library's own step, and the result must not depend on the input being prepared)