Java 类com.vividsolutions.jts.geomgraph.Node 实例源码

/**
 * Isolated nodes are nodes whose labels are incomplete
 * (e.g. the location for one Geometry is null).
 * This is the case because nodes in one graph which don't intersect
 * nodes in the other are not completely labelled by the initial process
 * of adding nodes to the nodeList.
 * To complete the labelling we need to check for nodes that lie in the
 * interior of edges, and in the interior of areas.
 */
private void labelIsolatedNodes() {
    for (Iterator ni = this.nodes.iterator(); ni.hasNext(); ) {
        Node n = (Node) ni.next();
        Label label = n.getLabel();
        // isolated nodes should always have at least one geometry in their label
        Assert.isTrue(label.getGeometryCount() > 0, "node with empty label found");
        if (n.isIsolated()) {
            if (label.isNull(0)) {
                this.labelIsolatedNode(n, 0);
            } else {
                this.labelIsolatedNode(n, 1);
            }
        }
    }
}

/**
     * Find and mark L edges which are "covered" by the result area (if any).
     * L edges at nodes which also have A edges can be checked by checking
     * their depth at that node.
     * L edges at nodes which do not have A edges can be checked by doing a
     * point-in-polygon test with the previously computed result areas.
     */
    private void findCoveredLineEdges() {
        // first set covered for all L edges at nodes which have A edges too
        for (Object o1 : op.getGraph().getNodes()) {
            Node node = (Node) o1;
//node.print(System.out);
            ((DirectedEdgeStar) node.getEdges()).findCoveredLineEdges();
        }

        /**
         * For all L edges which weren't handled by the above,
         * use a point-in-poly test to determine whether they are covered
         */
        for (Object o : op.getGraph().getEdgeEnds()) {
            DirectedEdge de = (DirectedEdge) o;
            Edge e = de.getEdge();
            if (de.isLineEdge() && !e.isCoveredSet()) {
                boolean isCovered = this.op.isCoveredByA(de.getCoordinate());
                e.setCovered(isCovered);
            }
        }
    }

/**
     * Incomplete nodes are nodes whose labels are incomplete.
     * (e.g. the location for one Geometry is null).
     * These are either isolated nodes,
     * or nodes which have edges from only a single Geometry incident on them.
     * <p>
     * Isolated nodes are found because nodes in one graph which don't intersect
     * nodes in the other are not completely labelled by the initial process
     * of adding nodes to the nodeList.
     * To complete the labelling we need to check for nodes that lie in the
     * interior of edges, and in the interior of areas.
     * <p>
     * When each node labelling is completed, the labelling of the incident
     * edges is updated, to complete their labelling as well.
     */
    private void labelIncompleteNodes() {
        int nodeCount = 0;
        for (Object o : graph.getNodes()) {
            Node n = (Node) o;
            Label label = n.getLabel();
            if (n.isIsolated()) {
                nodeCount++;
                if (label.isNull(0)) {
                    this.labelIncompleteNode(n, 0);
                } else {
                    this.labelIncompleteNode(n, 1);
                }
            }
            // now update the labelling for the DirectedEdges incident on this node
            ((DirectedEdgeStar) n.getEdges()).updateLabelling(label);
//n.print(System.out);
        }
    /*
    int nPoly0 = arg[0].getGeometry().getNumGeometries();
    int nPoly1 = arg[1].getGeometry().getNumGeometries();
    System.out.println("# isolated nodes= " + nodeCount 
            + "   # poly[0] = " + nPoly0
            + "   # poly[1] = " + nPoly1);
    */
    }

private List createSubgraphs(PlanarGraph graph) {
    List subgraphList = new ArrayList();
    for (Object o : graph.getNodes()) {
        Node node = (Node) o;
        if (!node.isVisited()) {
            BufferSubgraph subgraph = new BufferSubgraph();
            subgraph.create(node);
            subgraphList.add(subgraph);
        }
    }
    /**
     * Sort the subgraphs in descending order of their rightmost coordinate.
     * This ensures that when the Polygons for the subgraphs are built,
     * subgraphs for shells will have been built before the subgraphs for
     * any holes they contain.
     */
    subgraphList.sort(Collections.reverseOrder());
    return subgraphList;
}

/**
 * Adds the argument node and all its out edges to the subgraph
 *
 * @param node the node to add
 * @param nodeStack the current set of nodes being traversed
 */
private void add(Node node, Stack nodeStack) {
    node.setVisited(true);
    this.nodes.add(node);
    for (Iterator i = node.getEdges().iterator(); i.hasNext(); ) {
        DirectedEdge de = (DirectedEdge) i.next();
        this.dirEdgeList.add(de);
        DirectedEdge sym = de.getSym();
        Node symNode = sym.getNode();
        /**
         * NOTE: this is a depth-first traversal of the graph.
         * This will cause a large depth of recursion.
         * It might be better to do a breadth-first traversal.
         */
        if (!symNode.isVisited()) {
            nodeStack.push(symNode);
        }
    }
}

/**
 * Tests whether the result geometry is consistent
 *
 * @throws TopologyException if inconsistent topology is found
 */
public void check(int opCode) {
    for (Iterator nodeit = this.graph.getNodeIterator(); nodeit.hasNext(); ) {
        Node node = (Node) nodeit.next();
        this.testLinkResultDirectedEdges((DirectedEdgeStar) node.getEdges(), opCode);
    }
}

/**
 * For all nodes in this EdgeRing,
 * link the DirectedEdges at the node to form minimalEdgeRings
 */
public void linkDirectedEdgesForMinimalEdgeRings() {
    DirectedEdge de = this.startDe;
    do {
        Node node = de.getNode();
        ((DirectedEdgeStar) node.getEdges()).linkMinimalDirectedEdges(this);
        de = de.getNext();
    } while (de != this.startDe);
}

/**
 * Determines nodes which are in the result, and creates {@link Point}s for them.
 * <p>
 * This method determines nodes which are candidates for the result via their
 * labelling and their graph topology.
 *
 * @param opCode the overlay operation
 */
private void extractNonCoveredResultNodes(int opCode) {
    // testing only
    //if (true) return resultNodeList;

    for (Object o : op.getGraph().getNodes()) {
        Node n = (Node) o;

        // filter out nodes which are known to be in the result
        if (n.isInResult()) {
            continue;
        }
        // if an incident edge is in the result, then the node coordinate is included already
        if (n.isIncidentEdgeInResult()) {
            continue;
        }
        if (n.getEdges().getDegree() == 0 || opCode == OverlayOp.INTERSECTION) {

            /**
             * For nodes on edges, only INTERSECTION can result in edge nodes being included even
             * if none of their incident edges are included
             */
            Label label = n.getLabel();
            if (OverlayOp.isResultOfOp(label, opCode)) {
                this.filterCoveredNodeToPoint(n);
            }
        }
    }
    //System.out.println("connectedResultNodes collected = " + connectedResultNodes.size());
}

/**
     * Compute initial labelling for all DirectedEdges at each node.
     * In this step, DirectedEdges will acquire a complete labelling
     * (i.e. one with labels for both Geometries)
     * only if they
     * are incident on a node which has edges for both Geometries
     */
    private void computeLabelling() {
        for (Object o : graph.getNodes()) {
            Node node = (Node) o;
//if (node.getCoordinate().equals(new Coordinate(222, 100)) ) Debug.addWatch(node.getEdges());
            node.getEdges().computeLabelling(this.arg);
        }
        this.mergeSymLabels();
        this.updateNodeLabelling();
    }

/**
     * For nodes which have edges from only one Geometry incident on them,
     * the previous step will have left their dirEdges with no labelling for the other
     * Geometry.  However, the sym dirEdge may have a labelling for the other
     * Geometry, so merge the two labels.
     */
    private void mergeSymLabels() {
        for (Object o : graph.getNodes()) {
            Node node = (Node) o;
            ((DirectedEdgeStar) node.getEdges()).mergeSymLabels();
//node.print(System.out);
        }
    }

private void updateNodeLabelling() {
    // update the labels for nodes
    // The label for a node is updated from the edges incident on it
    // (Note that a node may have already been labelled
    // because it is a point in one of the input geometries)
    for (Object o : graph.getNodes()) {
        Node node = (Node) o;
        Label lbl = ((DirectedEdgeStar) node.getEdges()).getLabel();
        node.getLabel().merge(lbl);
    }
}

/**
     * Label an isolated node with its relationship to the target geometry.
     */
    private void labelIncompleteNode(Node n, int targetIndex) {
        int loc = this.ptLocator.locate(n.getCoordinate(), this.arg[targetIndex].getGeometry());

        // MD - 2008-10-24 - experimental for now
//    int loc = arg[targetIndex].locate(n.getCoordinate());
        n.getLabel().setLocation(targetIndex, loc);
    }

private void findRightmostEdgeAtNode() {
    Node node = this.minDe.getNode();
    DirectedEdgeStar star = (DirectedEdgeStar) node.getEdges();
    this.minDe = star.getRightmostEdge();
    // the DirectedEdge returned by the previous call is not
    // necessarily in the forward direction. Use the sym edge if it isn't.
    if (!this.minDe.isForward()) {
        this.minDe = this.minDe.getSym();
        this.minIndex = this.minDe.getEdge().getCoordinates().length - 1;
    }
}

/**
 * Adds all nodes and edges reachable from this node to the subgraph.
 * Uses an explicit stack to avoid a large depth of recursion.
 *
 * @param node a node known to be in the subgraph
 */
private void addReachable(Node startNode) {
    Stack nodeStack = new Stack();
    nodeStack.add(startNode);
    while (!nodeStack.empty()) {
        Node node = (Node) nodeStack.pop();
        this.add(node, nodeStack);
    }
}

public void computeDepth(int outsideDepth) {
    this.clearVisitedEdges();
    // find an outside edge to assign depth to
    DirectedEdge de = this.finder.getEdge();
    Node n = de.getNode();
    Label label = de.getLabel();
    // right side of line returned by finder is on the outside
    de.setEdgeDepths(Position.RIGHT, outsideDepth);
    this.copySymDepths(de);

    //computeNodeDepth(n, de);
    this.computeDepths(de);
}

/**
     * Compute depths for all dirEdges via breadth-first traversal of nodes in graph
     *
     * @param startEdge edge to start processing with
     */
    // <FIX> MD - use iteration & queue rather than recursion, for speed and robustness
    private void computeDepths(DirectedEdge startEdge) {
        Set nodesVisited = new HashSet();
        LinkedList nodeQueue = new LinkedList();

        Node startNode = startEdge.getNode();
        nodeQueue.addLast(startNode);
        nodesVisited.add(startNode);
        startEdge.setVisited(true);

        while (!nodeQueue.isEmpty()) {
//System.out.println(nodes.size() + " queue: " + nodeQueue.size());
            Node n = (Node) nodeQueue.removeFirst();
            nodesVisited.add(n);
            // compute depths around node, starting at this edge since it has depths assigned
            this.computeNodeDepth(n);

            // add all adjacent nodes to process queue,
            // unless the node has been visited already
            for (Iterator i = n.getEdges().iterator(); i.hasNext(); ) {
                DirectedEdge de = (DirectedEdge) i.next();
                DirectedEdge sym = de.getSym();
                if (sym.isVisited()) {
                    continue;
                }
                Node adjNode = sym.getNode();
                if (!(nodesVisited.contains(adjNode))) {
                    nodeQueue.addLast(adjNode);
                    nodesVisited.add(adjNode);
                }
            }
        }
    }

private boolean isBoundaryPoint(LineIntersector li, Collection bdyNodes) {
    for (Object bdyNode : bdyNodes) {
        Node node = (Node) bdyNode;
        Coordinate pt = node.getCoordinate();
        if (li.isIntersection(pt)) {
            return true;
        }
    }
    return false;
}

/**
 * For all nodes in this EdgeRing,
 * link the DirectedEdges at the node to form minimalEdgeRings
 */
public void linkDirectedEdgesForMinimalEdgeRings() {
    DirectedEdge de = startDe;
    do {
        Node node = de.getNode();
        ((DirectedEdgeStar) node.getEdges()).linkMinimalDirectedEdges(this);
        de = de.getNext();
    } while (de != startDe);
}

/**
 * Determines nodes which are in the result, and creates {@link Point}s for them.
 * <p/>
 * This method determines nodes which are candidates for the result via their
 * labelling and their graph topology.
 *
 * @param opCode the overlay operation
 */
private void extractNonCoveredResultNodes(int opCode) {
    // testing only
    //if (true) return resultNodeList;

    for (Iterator nodeit = op.getGraph().getNodes().iterator(); nodeit.hasNext(); ) {
        Node n = (Node) nodeit.next();

        // filter out nodes which are known to be in the result
        if (n.isInResult())
            continue;
        // if an incident edge is in the result, then the node coordinate is included already
        if (n.isIncidentEdgeInResult())
            continue;
        if (n.getEdges().getDegree() == 0 || opCode == OverlayOp.INTERSECTION) {

            /**
             * For nodes on edges, only INTERSECTION can result in edge nodes being included even
             * if none of their incident edges are included
             */
            Label label = n.getLabel();
            if (OverlayOp.isResultOfOp(label, opCode)) {
                filterCoveredNodeToPoint(n);
            }
        }
    }
    //System.out.println("connectedResultNodes collected = " + connectedResultNodes.size());
}

private boolean isBoundaryPoint(LineIntersector li, Collection bdyNodes) {
    for (Iterator i = bdyNodes.iterator(); i.hasNext(); ) {
        Node node = (Node) i.next();
        Coordinate pt = node.getCoordinate();
        if (li.isIntersection(pt)) return true;
    }
    return false;
}

/**
 * This method expects that a node has a coordinate value.
 */
public Node addNode(Coordinate coord)
{
  Node node = (Node) nodeMap.get(coord);
  if (node == null) {
    node = nodeFact.createNode(coord);
    nodeMap.put(coord, node);
  }
  return node;
}

public Node addNode(Node n)
{
  Node node = (Node) nodeMap.get(n.getCoordinate());
  if (node == null) {
    nodeMap.put(n.getCoordinate(), n);
    return n;
  }
  node.mergeLabel(n);
  return node;
}

/**
 * Adds a node for the start point of this EdgeEnd
 * (if one does not already exist in this map).
 * Adds the EdgeEnd to the (possibly new) node.
 */
public void add(EdgeEnd e)
{
  Coordinate p = e.getCoordinate();
  Node n = addNode(p);
  n.add(e);
}

public Collection getBoundaryNodes(int geomIndex)
{
  Collection bdyNodes = new ArrayList();
  for (Iterator i = iterator(); i.hasNext(); ) {
    Node node = (Node) i.next();
    if (node.getLabel().getLocation(geomIndex) == Location.BOUNDARY)
      bdyNodes.add(node);
  }
  return bdyNodes;
}

public void print(PrintStream out)
{
  for (Iterator it = iterator(); it.hasNext(); )
  {
    Node n = (Node) it.next();
    n.print(out);
  }
}

/**
 * This method expects that a node has a coordinate value.
 */
public Node addNode(Coordinate coord)
{
  Node node = (Node) nodeMap.get(coord);
  if (node == null) {
    node = nodeFact.createNode(coord);
    nodeMap.put(coord, node);
  }
  return node;
}

public Node addNode(Node n)
{
  Node node = (Node) nodeMap.get(n.getCoordinate());
  if (node == null) {
    nodeMap.put(n.getCoordinate(), n);
    return n;
  }
  node.mergeLabel(n);
  return node;
}

/**
 * Adds a node for the start point of this EdgeEnd
 * (if one does not already exist in this map).
 * Adds the EdgeEnd to the (possibly new) node.
 */
public void add(EdgeEnd e)
{
  Coordinate p = e.getCoordinate();
  Node n = addNode(p);
  n.add(e);
}

public Collection getBoundaryNodes(int geomIndex)
{
  Collection bdyNodes = new ArrayList();
  for (Iterator i = iterator(); i.hasNext(); ) {
    Node node = (Node) i.next();
    if (node.getLabel().getLocation(geomIndex) == Location.BOUNDARY)
      bdyNodes.add(node);
  }
  return bdyNodes;
}

public void print(PrintStream out)
{
  for (Iterator it = iterator(); it.hasNext(); )
  {
    Node n = (Node) it.next();
    n.print(out);
  }
}

/**
     * Label an isolated node with its relationship to the target geometry.
     */
    private void labelIsolatedNode(Node n, int targetIndex) {
        int loc = this.ptLocator.locate(n.getCoordinate(), this.arg[targetIndex].getGeometry());
        n.getLabel().setAllLocations(targetIndex, loc);
//debugPrintln(n.getLabel());
    }

@Override
public Node createNode(Coordinate coord) {
    return new RelateNode(coord, new EdgeEndBundleStar());
}

@Override
public Node createNode(Coordinate coord) {
    return new Node(coord, new DirectedEdgeStar());
}

public Node createNode(Coordinate coord) {
    return new RelateNode(coord, new EdgeEndBundleStar());
}

public Node createNode(Coordinate coord) {
    return new Node(coord, new DirectedEdgeStar());
}

/**
     * Copy all nodes from an arg geometry into this graph.
     * The node label in the arg geometry overrides any previously computed
     * label for that argIndex.
     * (E.g. a node may be an intersection node with
     * a computed label of BOUNDARY,
     * but in the original arg Geometry it is actually
     * in the interior due to the Boundary Determination Rule)
     */
    private void copyNodesAndLabels(int argIndex) {
        for (Iterator i = this.arg[argIndex].getNodeIterator(); i.hasNext(); ) {
            Node graphNode = (Node) i.next();
            Node newNode = this.nodes.addNode(graphNode.getCoordinate());
            newNode.setLabel(argIndex, graphNode.getLabel().getLocation(argIndex));
//node.print(System.out);
        }
    }

/**
     * Copy all nodes from an arg geometry into this graph.
     * The node label in the arg geometry overrides any previously computed
     * label for that argIndex.
     * (E.g. a node may be an intersection node with
     * a computed label of BOUNDARY,
     * but in the original arg Geometry it is actually
     * in the interior due to the Boundary Determination Rule)
     */
    public void copyNodesAndLabels(GeometryGraph geomGraph, int argIndex) {
        for (Iterator nodeIt = geomGraph.getNodeIterator(); nodeIt.hasNext(); ) {
            Node graphNode = (Node) nodeIt.next();
            Node newNode = this.nodes.addNode(graphNode.getCoordinate());
            newNode.setLabel(argIndex, graphNode.getLabel().getLocation(argIndex));
//node.print(System.out);
        }
    }

/**
 * Converts non-covered nodes to Point objects and adds them to the result.
 * <p>
 * A node is covered if it is contained in another element Geometry
 * with higher dimension (e.g. a node point might be contained in a polygon,
 * in which case the point can be eliminated from the result).
 *
 * @param n the node to test
 */
private void filterCoveredNodeToPoint(Node n) {
    Coordinate coord = n.getCoordinate();
    if (!this.op.isCoveredByLA(coord)) {
        Point pt = this.geometryFactory.createPoint(coord);
        this.resultPointList.add(pt);
    }
}

/**
 * Copy all nodes from an arg geometry into this graph.
 * The node label in the arg geometry overrides any previously computed
 * label for that argIndex.
 * (E.g. a node may be an intersection node with
 * a previously computed label of BOUNDARY,
 * but in the original arg Geometry it is actually
 * in the interior due to the Boundary Determination Rule)
 */
private void copyPoints(int argIndex) {
    for (Iterator i = this.arg[argIndex].getNodeIterator(); i.hasNext(); ) {
        Node graphNode = (Node) i.next();
        Node newNode = this.graph.addNode(graphNode.getCoordinate());
        newNode.setLabel(argIndex, graphNode.getLabel().getLocation(argIndex));
    }
}

/**
 * Converts non-covered nodes to Point objects and adds them to the result.
 * <p/>
 * A node is covered if it is contained in another element Geometry
 * with higher dimension (e.g. a node point might be contained in a polygon,
 * in which case the point can be eliminated from the result).
 *
 * @param n the node to test
 */
private void filterCoveredNodeToPoint(Node n) {
    Coordinate coord = n.getCoordinate();
    if (!op.isCoveredByLA(coord)) {
        Point pt = geometryFactory.createPoint(coord);
        resultPointList.add(pt);
    }
}