Class PolygonizeGraph
java.lang.Object
org.locationtech.jts.planargraph.PlanarGraph
org.locationtech.jts.operation.polygonize.PolygonizeGraph
Represents a planar graph of edges that can be used to compute a
polygonization, and implements the algorithms to compute the
formed by the graph.
invalid reference
EdgeRings
The marked flag on DirectedEdge
s is used to indicate that a directed edge
has be logically deleted from the graph.
- Version:
- 1.7
-
Field Summary
FieldsFields inherited from class org.locationtech.jts.planargraph.PlanarGraph
dirEdges, edges, nodeMap
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
addEdge
(LineString line) Add aLineString
forming an edge of the polygon graph.void
Traverses the polygonized edge rings in the graph and computes the depth parity (odd or even) relative to the exterior of the graph.private void
Traverses all connected edges, computing the depth parity of the associated polygons.private static void
computeNextCCWEdges
(Node node, long label) Computes the next edge pointers going CCW around the given node, for the given edgering label.private void
private static void
computeNextCWEdges
(Node node) private void
convertMaximalToMinimalEdgeRings
(List ringEdges) Convert the maximal edge rings found by the initial graph traversal into the minimal edge rings required by JTS polygon topology rules.static void
deleteAllEdges
(Node node) Deletes all edges at a nodeFinds and removes all cut edges from the graph.Marks all edges from the graph which are "dangles".private EdgeRing
findEdgeRing
(PolygonizeDirectedEdge startDE) private static List
findIntersectionNodes
(PolygonizeDirectedEdge startDE, long label) Finds all nodes in a maximal edgering which are self-intersection nodesprivate static List
findLabeledEdgeRings
(Collection dirEdges) Finds and labels all edgerings in the graph.private static int
private static int
getDegreeNonDeleted
(Node node) Computes the minimal EdgeRings formed by the edges in this graph.private Node
getNode
(Coordinate pt) private static void
label
(Collection dirEdges, long label) Methods inherited from class org.locationtech.jts.planargraph.PlanarGraph
add, add, add, contains, contains, dirEdgeIterator, edgeIterator, findNode, findNodesOfDegree, getEdges, getNodes, nodeIterator, remove, remove, remove
-
Field Details
-
factory
-
-
Constructor Details
-
PolygonizeGraph
Create a new polygonization graph.
-
-
Method Details
-
getDegreeNonDeleted
-
getDegree
-
deleteAllEdges
Deletes all edges at a node -
addEdge
Add aLineString
forming an edge of the polygon graph.- Parameters:
line
- the line to add
-
getNode
-
computeNextCWEdges
private void computeNextCWEdges() -
convertMaximalToMinimalEdgeRings
Convert the maximal edge rings found by the initial graph traversal into the minimal edge rings required by JTS polygon topology rules.- Parameters:
ringEdges
- the list of start edges for the edgeRings to convert.
-
findIntersectionNodes
Finds all nodes in a maximal edgering which are self-intersection nodes- Parameters:
startDE
-label
-- Returns:
- the list of intersection nodes found,
or
null
if no intersection nodes were found
-
getEdgeRings
Computes the minimal EdgeRings formed by the edges in this graph.- Returns:
- a list of the
EdgeRing
s found by the polygonization process.
-
findLabeledEdgeRings
Finds and labels all edgerings in the graph. The edge rings are labeling with unique integers. The labeling allows detecting cut edges.- Parameters:
dirEdges
- a List of the DirectedEdges in the graph- Returns:
- a List of DirectedEdges, one for each edge ring found
-
deleteCutEdges
Finds and removes all cut edges from the graph.- Returns:
- a list of the
LineString
s forming the removed cut edges
-
label
-
computeNextCWEdges
-
computeNextCCWEdges
Computes the next edge pointers going CCW around the given node, for the given edgering label. This algorithm has the effect of converting maximal edgerings into minimal edgerings -
findEdgeRing
-
deleteDangles
Marks all edges from the graph which are "dangles". Dangles are which are incident on a node with degree 1. This process is recursive, since removing a dangling edge may result in another edge becoming a dangle. In order to handle large recursion depths efficiently, an explicit recursion stack is used- Returns:
- a List containing the
LineString
s that formed dangles
-
computeDepthParity
public void computeDepthParity()Traverses the polygonized edge rings in the graph and computes the depth parity (odd or even) relative to the exterior of the graph. If the client has requested that the output be polygonally valid, only odd polygons will be constructed. -
computeDepthParity
Traverses all connected edges, computing the depth parity of the associated polygons.- Parameters:
de
-
-