Class BufferSubgraph

  • All Implemented Interfaces:
    java.lang.Comparable

    class BufferSubgraph
    extends java.lang.Object
    implements java.lang.Comparable
    A connected subset of the graph of DirectedEdges and Nodes. Its edges will generate either
    • a single polygon in the complete buffer, with zero or more holes, or
    • one or more connected holes
    Version:
    1.7
    • Field Detail

      • dirEdgeList

        private java.util.List dirEdgeList
      • nodes

        private java.util.List nodes
      • rightMostCoord

        private Coordinate rightMostCoord
    • Constructor Detail

      • BufferSubgraph

        public BufferSubgraph()
    • Method Detail

      • getDirectedEdges

        public java.util.List getDirectedEdges()
      • getNodes

        public java.util.List getNodes()
      • getEnvelope

        public Envelope getEnvelope()
        Computes the envelope of the edges in the subgraph. The envelope is cached after being computed.
        Returns:
        the envelope of the graph.
      • getRightmostCoordinate

        public Coordinate getRightmostCoordinate()
        Gets the rightmost coordinate in the edges of the subgraph
      • create

        public void create​(Node node)
        Creates the subgraph consisting of all edges reachable from this node. Finds the edges in the graph and the rightmost coordinate.
        Parameters:
        node - a node to start the graph traversal from
      • addReachable

        private void addReachable​(Node startNode)
        Adds all nodes and edges reachable from this node to the subgraph. Uses an explicit stack to avoid a large depth of recursion.
        Parameters:
        node - a node known to be in the subgraph
      • add

        private void add​(Node node,
                         java.util.Stack nodeStack)
        Adds the argument node and all its out edges to the subgraph
        Parameters:
        node - the node to add
        nodeStack - the current set of nodes being traversed
      • clearVisitedEdges

        private void clearVisitedEdges()
      • computeDepth

        public void computeDepth​(int outsideDepth)
      • computeDepths

        private void computeDepths​(DirectedEdge startEdge)
        Compute depths for all dirEdges via breadth-first traversal of nodes in graph
        Parameters:
        startEdge - edge to start processing with
      • computeNodeDepth

        private void computeNodeDepth​(Node n)
      • copySymDepths

        private void copySymDepths​(DirectedEdge de)
      • findResultEdges

        public void findResultEdges()
        Find all edges whose depths indicates that they are in the result area(s). Since we want polygon shells to be oriented CW, choose dirEdges with the interior of the result on the RHS. Mark them as being in the result. Interior Area edges are the result of dimensional collapses. They do not form part of the result area boundary.
      • compareTo

        public int compareTo​(java.lang.Object o)
        BufferSubgraphs are compared on the x-value of their rightmost Coordinate. This defines a partial ordering on the graphs such that:

        g1 >= g2 <==> Ring(g2) does not contain Ring(g1)

        where Polygon(g) is the buffer polygon that is built from g.

        This relationship is used to sort the BufferSubgraphs so that shells are guaranteed to be built before holes.

        Specified by:
        compareTo in interface java.lang.Comparable