Class PolygonizeGraph
- java.lang.Object
-
- org.locationtech.jts.planargraph.PlanarGraph
-
- org.locationtech.jts.operation.polygonize.PolygonizeGraph
-
class PolygonizeGraph extends PlanarGraph
Represents a planar graph of edges that can be used to compute a polygonization, and implements the algorithms to compute theEdgeRings
formed by the graph.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
Fields Modifier and Type Field Description private GeometryFactory
factory
-
Fields inherited from class org.locationtech.jts.planargraph.PlanarGraph
dirEdges, edges, nodeMap
-
-
Constructor Summary
Constructors Constructor Description PolygonizeGraph(GeometryFactory factory)
Create a new polygonization graph.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEdge(LineString line)
Add aLineString
forming an edge of the polygon graph.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.private void
computeDepthParity(PolygonizeDirectedEdge de)
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
computeNextCWEdges()
private static void
computeNextCWEdges(Node node)
private void
convertMaximalToMinimalEdgeRings(java.util.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 nodejava.util.List
deleteCutEdges()
Finds and removes all cut edges from the graph.java.util.Collection
deleteDangles()
Marks all edges from the graph which are "dangles".private EdgeRing
findEdgeRing(PolygonizeDirectedEdge startDE)
private static java.util.List
findIntersectionNodes(PolygonizeDirectedEdge startDE, long label)
Finds all nodes in a maximal edgering which are self-intersection nodesprivate static java.util.List
findLabeledEdgeRings(java.util.Collection dirEdges)
Finds and labels all edgerings in the graph.private static int
getDegree(Node node, long label)
private static int
getDegreeNonDeleted(Node node)
java.util.List
getEdgeRings()
Computes the minimal EdgeRings formed by the edges in this graph.private Node
getNode(Coordinate pt)
private static void
label(java.util.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 Detail
-
factory
private GeometryFactory factory
-
-
Constructor Detail
-
PolygonizeGraph
public PolygonizeGraph(GeometryFactory factory)
Create a new polygonization graph.
-
-
Method Detail
-
getDegreeNonDeleted
private static int getDegreeNonDeleted(Node node)
-
getDegree
private static int getDegree(Node node, long label)
-
deleteAllEdges
public static void deleteAllEdges(Node node)
Deletes all edges at a node
-
addEdge
public void addEdge(LineString line)
Add aLineString
forming an edge of the polygon graph.- Parameters:
line
- the line to add
-
getNode
private Node getNode(Coordinate pt)
-
computeNextCWEdges
private void computeNextCWEdges()
-
convertMaximalToMinimalEdgeRings
private void convertMaximalToMinimalEdgeRings(java.util.List ringEdges)
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
private static java.util.List findIntersectionNodes(PolygonizeDirectedEdge startDE, long label)
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
public java.util.List 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
private static java.util.List findLabeledEdgeRings(java.util.Collection dirEdges)
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
public java.util.List deleteCutEdges()
Finds and removes all cut edges from the graph.- Returns:
- a list of the
LineString
s forming the removed cut edges
-
label
private static void label(java.util.Collection dirEdges, long label)
-
computeNextCWEdges
private static void computeNextCWEdges(Node node)
-
computeNextCCWEdges
private static void computeNextCCWEdges(Node node, long label)
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
private EdgeRing findEdgeRing(PolygonizeDirectedEdge startDE)
-
deleteDangles
public java.util.Collection 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
private void computeDepthParity(PolygonizeDirectedEdge de)
Traverses all connected edges, computing the depth parity of the associated polygons.- Parameters:
de
-
-
-