Namespace NetTopologySuite.Operation.Relate

Contains classes to implement the computation of the spatial relationships of Geometrys.

The relate algorithm computes the IntersectionMatrix describing the relationship of two Geometrys. The algorithm for computing relate uses the intersection operations supported by topology graphs. Although the relate result depends on the resultant graph formed by the computed intersections, there is no need to explicitly compute the entire graph. It is sufficient to compute the local structure of the graph at each intersection node.

The algorithm to compute relate has the following steps:

  • Build topology graphs of the two input geometries. For each geometry all self-intersection nodes are computed and added to the graph.
  • Compute nodes for all intersections between edges and nodes of the graphs.
  • Compute the labeling for the computed nodes by merging the labels from the input graphs.
  • Compute the labeling for isolated components of the graph (see below)
  • Compute the IntersectionMatrix from the labels on the nodes and edges.
  • Labeling isolated components

Isolated components are components (edges or nodes) of an input Geometry which do not contain any intersections with the other input Geometry. The topological relationship of these components to the other input Geometry must be computed in order to determine the complete labeling of the component. This can be done by testing whether the component lies in the interior or exterior of the other Geometry. If the other Geometry is 1-dimensional, the isolated component must lie in the exterior (since otherwise it would have an intersection with an edge of the Geometry). If the other Geometry is 2-dimensional, a Point-In-Polygon test can be used to determine whether the isolated component is in the interior or exterior.

Package Specification

Classes

EdgeEndBuilder

An EdgeEndBuilder creates EdgeEnds for all the "split edges" created by the intersections determined for an Edge. Computes the EdgeEnds which arise from a noded Edge.

EdgeEndBundle

A collection of EdgeStubs which obey the following invariant: They originate at the same node and have the same direction. Contains all EdgeEnds which start at the same point and are parallel.

EdgeEndBundleStar

An ordered list of EdgeEndBundles around a RelateNode. They are maintained in CCW order (starting with the positive x-axis) around the node for efficient lookup and topology building.

RelateComputer

Computes the topological relationship between two Geometries. RelateComputer does not need to build a complete graph structure to compute the IntersectionMatrix. The relationship between the geometries can be computed by simply examining the labelling of edges incident on each node. RelateComputer does not currently support arbitrary GeometryCollections. This is because GeometryCollections can contain overlapping Polygons. In order to correct compute relate on overlapping Polygons, they would first need to be noded and merged (if not explicitly, at least implicitly).

RelateNode

A RelateNode is a Node that maintains a list of EdgeStubs for the edges that are incident on it.

RelateNodeFactory

Used by the NodeMap in a RelateNodeGraph to create RelateNodes.

RelateNodeGraph

Implements the simple graph of Nodes and EdgeEnd which is all that is required to determine topological relationships between Geometries. Also supports building a topological graph of a single Geometry, to allow verification of valid topology. It is not necessary to create a fully linked PlanarGraph to determine relationships, since it is sufficient to know how the Geometries interact locally around the nodes. In fact, this is not even feasible, since it is not possible to compute exact intersection points, and hence the topology around those nodes cannot be computed robustly. The only Nodes that are created are for improper intersections; that is, nodes which occur at existing vertices of the Geometries. Proper intersections (e.g. ones which occur between the interior of line segments) have their topology determined implicitly, without creating a Node object to represent them.

RelateOp

Implements the SFS relate() generalized spatial predicate on two Geometrys.
The class supports specifying a custom IBoundaryNodeRule to be used during the relate computation.