Package org.locationtech.jts.operation.polygonize

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 the
invalid reference 
EdgeRings
formed by the graph.

The marked flag on DirectedEdges is used to indicate that a directed edge has be logically deleted from the graph.

Version:
1.7

  • Field Details

  • Constructor Details

    • PolygonizeGraph

      public PolygonizeGraph(GeometryFactory factory)
      Create a new polygonization graph.

  • Method Details

    • 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 a LineString 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(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 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 List getEdgeRings()
      Computes the minimal EdgeRings formed by the edges in this graph.
      Returns:
      a list of the EdgeRings found by the polygonization process.

    • findLabeledEdgeRings

      private static List findLabeledEdgeRings(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 List deleteCutEdges()
      Finds and removes all cut edges from the graph.
      Returns:
      a list of the LineStrings forming the removed cut edges

    • label

      private static void label(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 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 LineStrings 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 -