Class 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 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
    • 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 a LineString forming an edge of the polygon graph.
        Parameters:
        line - the line to add
      • 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 EdgeRings 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 LineStrings 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
      • 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 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 -