| com.vividsolutions.jts.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
|
| Java Source File Name | Type | Comment |
| EdgeEndBuilder.java | Class | Computes the
EdgeEnd s which arise from a noded
Edge . |
| EdgeEndBundle.java | Class | A collection of
EdgeEnd s which obey the following invariant:
They originate at the same node and have the same direction. |
| EdgeEndBundleStar.java | Class | An ordered list of
EdgeEndBundle s around a
RelateNode . |
| RelateComputer.java | Class | Computes the topological relationship between two Geometries.
RelateComputer does not need to build a complete graph structure to compute
the IntersectionMatrix. |
| RelateNode.java | Class | Represents a node in the topological graph used to compute spatial relationships. |
| RelateNodeFactory.java | Class | Used by the
NodeMap in a
RelateNodeGraph to create
RelateNode s. |
| RelateNodeGraph.java | Class | 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. |
| RelateOp.java | Class | Implements the SFS relate() operation on two
Geometry s.
This class supports specifying a custom
BoundaryNodeRule to be used during the relate computation.
Note: custom Boundary Node Rules do not (currently)
affect the results of other Geometry methods (such
as
Geometry.getBoundary . |