PolygonizeGraph.java

/*
 * Copyright (c) 2016 Vivid Solutions.
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 * and the Eclipse Distribution License is available at
 *
 * http://www.eclipse.org/org/documents/edl-v10.php.
 */
package org.locationtech.jts.operation.polygonize;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.CoordinateArrays;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.LineString;
import org.locationtech.jts.planargraph.DirectedEdge;
import org.locationtech.jts.planargraph.DirectedEdgeStar;
import org.locationtech.jts.planargraph.Edge;
import org.locationtech.jts.planargraph.Node;
import org.locationtech.jts.planargraph.PlanarGraph;
import org.locationtech.jts.util.Assert;

/**
 * Represents a planar graph of edges that can be used to compute a
 * polygonization, and implements the algorithms to compute the
 * {@link EdgeRing}s formed by the graph.
 * <p>
 * The marked flag on {@link DirectedEdge}s is used to indicate that a directed edge
 * has be logically deleted from the graph.
 *
 * @version 1.7
 */
class PolygonizeGraph
    extends PlanarGraph
{

  private static int getDegreeNonDeleted(Node node)
  {
    List<DirectedEdge> edges = node.getOutEdges().getEdges();
    int degree = 0;
    for (Iterator<DirectedEdge> i = edges.iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
      if (! de.isMarked()) degree++;
    }
    return degree;
  }

  private static int getDegree(Node node, long label)
  {
    List<DirectedEdge> edges = node.getOutEdges().getEdges();
    int degree = 0;
    for (Iterator<DirectedEdge> i = edges.iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
      if (de.getLabel() == label) degree++;
    }
    return degree;
  }

  /**
   * Deletes all edges at a node
   */
  public static void deleteAllEdges(Node node)
  {
    List<DirectedEdge> edges = node.getOutEdges().getEdges();
    for (Iterator<DirectedEdge> i = edges.iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
      de.setMarked(true);
      PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();
      if (sym != null)
        sym.setMarked(true);
    }
  }

  private GeometryFactory factory;

  //private List labelledRings;
 
  /**
   * Create a new polygonization graph.
   */
  public PolygonizeGraph(GeometryFactory factory)
  {
    this.factory = factory;
  }

  /**
   * Add a {@link LineString} forming an edge of the polygon graph.
   * @param line the line to add
   */
  public void addEdge(LineString line)
  {
    if (line.isEmpty()) { return; }
    Coordinate[] linePts = CoordinateArrays.removeRepeatedPoints(line.getCoordinates());
    
    if (linePts.length < 2) { return; }
    
    Coordinate startPt = linePts[0];
    Coordinate endPt = linePts[linePts.length - 1];

    Node nStart = getNode(startPt);
    Node nEnd = getNode(endPt);

    DirectedEdge de0 = new PolygonizeDirectedEdge(nStart, nEnd, linePts[1], true);
    DirectedEdge de1 = new PolygonizeDirectedEdge(nEnd, nStart, linePts[linePts.length - 2], false);
    Edge edge = new PolygonizeEdge(line);
    edge.setDirectedEdges(de0, de1);
    add(edge);
  }

  private Node getNode(Coordinate pt)
  {
    Node node = findNode(pt);
    if (node == null) {
      node = new Node(pt);
      // ensure node is only added once to graph
      add(node);
    }
    return node;
  }

  private void computeNextCWEdges()
  {
    // set the next pointers for the edges around each node
    for (Iterator<?> iNode = nodeIterator(); iNode.hasNext(); ) {
      Node node = (Node) iNode.next();
      computeNextCWEdges(node);
    }
  }

  /**
   * Convert the maximal edge rings found by the initial graph traversal
   * into the minimal edge rings required by JTS polygon topology rules.
   *
   * @param ringEdges the list of start edges for the edgeRings to convert.
   */
  private void convertMaximalToMinimalEdgeRings(List<PolygonizeDirectedEdge> ringEdges)
  {
    for (PolygonizeDirectedEdge de : ringEdges) {
      long label = de.getLabel();
      List<Node> intNodes = findIntersectionNodes(de, label);

      if (intNodes == null) continue;
      // flip the next pointers on the intersection nodes to create minimal edge rings
      for (Node node : intNodes) {
        computeNextCCWEdges(node, label);
      }
    }
  }

  /**
   * Finds all nodes in a maximal edgering which are self-intersection nodes
   * @param startDE
   * @param label
   * @return the list of intersection nodes found,
   * or <code>null</code> if no intersection nodes were found
   */
  private static List<Node> findIntersectionNodes(PolygonizeDirectedEdge startDE, long label)
  {
    PolygonizeDirectedEdge de = startDE;
    List<Node> intNodes = null;
    do {
      Node node = de.getFromNode();
      if (getDegree(node, label) > 1) {
        if (intNodes == null)
          intNodes = new ArrayList<Node>();
        intNodes.add(node);
      }

      de = de.getNext();
      Assert.isTrue(de != null, "found null DE in ring");
      Assert.isTrue(de == startDE || ! de.isInRing(), "found DE already in ring");
    } while (de != startDE);

    return intNodes;
  }

  /**
   * Computes the minimal EdgeRings formed by the edges in this graph.
   * @return a list of the {@link EdgeRing}s found by the polygonization process.
   */
  public List<EdgeRing> getEdgeRings()
  {
    // maybe could optimize this, since most of these pointers should be set correctly already
    // by deleteCutEdges()
    computeNextCWEdges();
    // clear labels of all edges in graph
    label(dirEdges, -1);
    List<PolygonizeDirectedEdge> maximalRings = findLabeledEdgeRings(dirEdges);
    convertMaximalToMinimalEdgeRings(maximalRings);

    // find all edgerings (which will now be minimal ones, as required)
    List<EdgeRing> edgeRingList = new ArrayList<EdgeRing>();
    for (Iterator<?> i = dirEdges.iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
      if (de.isMarked()) continue;
      if (de.isInRing()) continue;

      EdgeRing er = findEdgeRing(de);
      edgeRingList.add(er);
    }
    return edgeRingList;
  }

  /**
   * Finds and labels all edgerings in the graph.
   * The edge rings are labeling with unique integers.
   * The labeling allows detecting cut edges.
   * 
   * @param dirEdges a List of the DirectedEdges in the graph
   * @return a List of DirectedEdges, one for each edge ring found
   */
  private static List<PolygonizeDirectedEdge> findLabeledEdgeRings(Collection<PolygonizeDirectedEdge> dirEdges)
  {
    List<PolygonizeDirectedEdge> edgeRingStarts = new ArrayList<PolygonizeDirectedEdge>();
    // label the edge rings formed
    long currLabel = 1;
    for (Iterator<PolygonizeDirectedEdge> i = dirEdges.iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
      if (de.isMarked()) continue;
      if (de.getLabel() >= 0) continue;

      edgeRingStarts.add(de);
      List<PolygonizeDirectedEdge> edges = EdgeRing.findDirEdgesInRing(de);

      label(edges, currLabel);
      currLabel++;
    }
    return edgeRingStarts;
  }

  /**
   * Finds and removes all cut edges from the graph.
   * @return a list of the {@link LineString}s forming the removed cut edges
   */
  @SuppressWarnings("unchecked")
  public List<LineString> deleteCutEdges()
  {
    computeNextCWEdges();
    // label the current set of edgerings
    findLabeledEdgeRings(dirEdges);

    /**
     * Cut Edges are edges where both dirEdges have the same label.
     * Delete them, and record them
     */
    List<LineString> cutLines = new ArrayList<LineString>();
    for (Iterator<PolygonizeDirectedEdge> i = dirEdges.iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
      if (de.isMarked()) continue;

      PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();

      if (de.getLabel() == sym.getLabel()) {
        de.setMarked(true);
        sym.setMarked(true);

        // save the line as a cut edge
        PolygonizeEdge e = (PolygonizeEdge) de.getEdge();
        cutLines.add(e.getLine());
      }
    }
    return cutLines;
  }

  private static void label(Collection<?> dirEdges, long label)
  {
    for (Iterator<?> i = dirEdges.iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
      de.setLabel(label);
    }
  }
  private static void computeNextCWEdges(Node node)
  {
    DirectedEdgeStar deStar = node.getOutEdges();
    PolygonizeDirectedEdge startDE = null;
    PolygonizeDirectedEdge prevDE = null;

    // the edges are stored in CCW order around the star
    for (Iterator<?> i = deStar.getEdges().iterator(); i.hasNext(); ) {
      PolygonizeDirectedEdge outDE = (PolygonizeDirectedEdge) i.next();
      if (outDE.isMarked()) continue;

      if (startDE == null)
        startDE = outDE;
      if (prevDE != null) {
        PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) prevDE.getSym();
        sym.setNext(outDE);
      }
      prevDE = outDE;
    }
    if (prevDE != null) {
      PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) prevDE.getSym();
      sym.setNext(startDE);
    }
  }
  /**
   * 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
   */
  private static void computeNextCCWEdges(Node node, long label)
  {
    DirectedEdgeStar deStar = node.getOutEdges();
    //PolyDirectedEdge lastInDE = null;
    PolygonizeDirectedEdge firstOutDE = null;
    PolygonizeDirectedEdge prevInDE = null;

    // the edges are stored in CCW order around the star
    List<?> edges = deStar.getEdges();
    //for (Iterator i = deStar.getEdges().iterator(); i.hasNext(); ) {
    for (int i = edges.size() - 1; i >= 0; i--) {
      PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) edges.get(i);
      PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();

      PolygonizeDirectedEdge outDE = null;
      if (  de.getLabel() == label) outDE = de;
      PolygonizeDirectedEdge inDE = null;
      if (  sym.getLabel() == label) inDE =  sym;

      if (outDE == null && inDE == null) continue;  // this edge is not in edgering

      if (inDE != null) {
        prevInDE = inDE;
      }

      if (outDE != null) {
        if (prevInDE != null) {
          prevInDE.setNext(outDE);
          prevInDE = null;
        }
        if (firstOutDE == null)
          firstOutDE = outDE;
      }
    }
    if (prevInDE != null) {
      Assert.isTrue(firstOutDE != null);
      prevInDE.setNext(firstOutDE);
    }
  }

  private EdgeRing findEdgeRing(PolygonizeDirectedEdge startDE)
  {
    EdgeRing er = new EdgeRing(factory);
    er.build(startDE);
    return er;
  }

  /**
   * 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
   *
   * @return a List containing the {@link LineString}s that formed dangles
   */
  public List<LineString> deleteDangles()
  {
    @SuppressWarnings("unchecked")
    List<Node> nodesToRemove = findNodesOfDegree(1);
    List<LineString> dangleLines = new ArrayList<LineString>();

    Stack<Node> nodeStack = new Stack<Node>();
    for (Iterator<Node> i = nodesToRemove.iterator(); i.hasNext(); ) {
      nodeStack.push(i.next());
    }

    while (! nodeStack.isEmpty()) {
      Node node = (Node) nodeStack.pop();

      deleteAllEdges(node);
      List<?> nodeOutEdges = node.getOutEdges().getEdges();
      for (Iterator<?> i = nodeOutEdges.iterator(); i.hasNext(); ) {
        PolygonizeDirectedEdge de = (PolygonizeDirectedEdge) i.next();
        // delete this edge and its sym
        de.setMarked(true);
        PolygonizeDirectedEdge sym = (PolygonizeDirectedEdge) de.getSym();
        if (sym != null)
          sym.setMarked(true);

        // save the line as a dangle
        PolygonizeEdge e = (PolygonizeEdge) de.getEdge();
        dangleLines.add(e.getLine());

        Node toNode = de.getToNode();
        // add the toNode to the list to be processed, if it is now a dangle
        if (getDegreeNonDeleted(toNode) == 1)
          nodeStack.push(toNode);
      }
    }
    return dangleLines;
  }
  
}