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

/**
 * Form DirectedEdges in graph into Minimal EdgeRings.
 * (Minimal Edgerings must be used, because only they are guaranteed to provide
 * a correct isHole computation)
 */
private List buildEdgeRings(Collection dirEdges) {
    List edgeRings = new ArrayList();
    for (Object dirEdge : dirEdges) {
        DirectedEdge de = (DirectedEdge) dirEdge;
        // if this edge has not yet been processed
        if (de.isInResult()
                && de.getEdgeRing() == null) {
            MaximalEdgeRing er = new MaximalEdgeRing(de, this.geometryFactory);

            er.linkDirectedEdgesForMinimalEdgeRings();
            List minEdgeRings = er.buildMinimalRings();
            edgeRings.addAll(minEdgeRings);
        }
    }
    return edgeRings;
}

private void visitInteriorRing(LineString ring, PlanarGraph graph) {
    Coordinate[] pts = ring.getCoordinates();
    Coordinate pt0 = pts[0];
    /**
     * Find first point in coord list different to initial point.
     * Need special check since the first point may be repeated.
     */
    Coordinate pt1 = findDifferentPoint(pts, pt0);
    Edge e = graph.findEdgeInSameDirection(pt0, pt1);
    DirectedEdge de = (DirectedEdge) graph.findEdgeEnd(e);
    DirectedEdge intDe = null;
    if (de.getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
        intDe = de;
    } else if (de.getSym().getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
        intDe = de.getSym();
    }
    Assert.isTrue(intDe != null, "unable to find dirEdge with Interior on RHS");

    this.visitLinkedDirectedEdges(intDe);
}

/**
     * 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);
            }
        }
    }

/**
 * Collect edges from Area inputs which should be in the result but
 * which have not been included in a result area.
 * This happens ONLY:
 * <ul>
 * <li>during an intersection when the boundaries of two
 * areas touch in a line segment
 * <li> OR as a result of a dimensional collapse.
 * </ul>
 */
private void collectBoundaryTouchEdge(DirectedEdge de, int opCode, List edges) {
    Label label = de.getLabel();
    if (de.isLineEdge()) {
        return;  // only interested in area edges
    }
    if (de.isVisited()) {
        return;  // already processed
    }
    if (de.isInteriorAreaEdge()) {
        return;  // added to handle dimensional collapses
    }
    if (de.getEdge().isInResult()) {
        return;  // if the edge linework is already included, don't include it again
    }

    // sanity check for labelling of result edgerings
    Assert.isTrue(!(de.isInResult() || de.getSym().isInResult()) || !de.getEdge().isInResult());

    // include the linework if it's in the result of the operation
    if (OverlayOp.isResultOfOp(label, opCode)
            && opCode == OverlayOp.INTERSECTION) {
        edges.add(de.getEdge());
        de.setVisitedEdge(true);
    }
}

/**
     * for all DirectedEdges in result, form them into MaximalEdgeRings
     */
    private List buildMaximalEdgeRings(Collection dirEdges) {
        List maxEdgeRings = new ArrayList();
        for (Object dirEdge : dirEdges) {
            DirectedEdge de = (DirectedEdge) dirEdge;
            if (de.isInResult() && de.getLabel().isArea()) {
                // if this edge has not yet been processed
                if (de.getEdgeRing() == null) {
                    MaximalEdgeRing er = new MaximalEdgeRing(de, this.geometryFactory);
                    maxEdgeRings.add(er);
                    er.setInResult();
//System.out.println("max node degree = " + er.getMaxDegree());
                }
            }
        }
        return maxEdgeRings;
    }

/**
     * Find all edges whose label indicates that they are in the result area(s),
     * according to the operation being performed.  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.
     */
    private void findResultAreaEdges(int opCode) {
        for (Object o : graph.getEdgeEnds()) {
            DirectedEdge de = (DirectedEdge) o;
            // mark all dirEdges with the appropriate label
            Label label = de.getLabel();
            if (label.isArea()
                    && !de.isInteriorAreaEdge()
                    && isResultOfOp(
                    label.getLocation(0, Position.RIGHT),
                    label.getLocation(1, Position.RIGHT),
                    opCode)) {
                de.setInResult(true);
//Debug.print("in result "); Debug.println(de);
            }
        }
    }

private int getRightmostSideOfSegment(DirectedEdge de, int i) {
    Edge e = de.getEdge();
    Coordinate coord[] = e.getCoordinates();

    if (i < 0 || i + 1 >= coord.length) {
        return -1;
    }
    if (coord[i].y == coord[i + 1].y) {
        return -1;    // indicates edge is parallel to x-axis
    }

    int pos = Position.LEFT;
    if (coord[i].y < coord[i + 1].y) {
        pos = Position.RIGHT;
    }
    return pos;
}

/**
 * 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);
        }
    }
}

/**
     * 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.
     */
    public void findResultEdges() {
        for (Object aDirEdgeList : dirEdgeList) {
            DirectedEdge de = (DirectedEdge) aDirEdgeList;
            /**
             * Select edges which have an interior depth on the RHS
             * and an exterior depth on the LHS.
             * Note that because of weird rounding effects there may be
             * edges which have negative depths!  Negative depths
             * count as "outside".
             */
            // <FIX> - handle negative depths
            if (de.getDepth(Position.RIGHT) >= 1
                    && de.getDepth(Position.LEFT) <= 0
                    && !de.isInteriorAreaEdge()) {
                de.setInResult(true);
//Debug.print("in result "); Debug.println(de);
            }
        }
    }

/**
 * Finds all non-horizontal segments intersecting the stabbing line
 * in the list of dirEdges.
 * The stabbing line is the ray to the right of stabbingRayLeftPt.
 *
 * @param stabbingRayLeftPt the left-hand origin of the stabbing line
 * @param stabbedSegments the current list of {@link DepthSegments} intersecting the stabbing line
 */
private void findStabbedSegments(Coordinate stabbingRayLeftPt,
                                 List dirEdges,
                                 List stabbedSegments) {
    /**
     * Check all forward DirectedEdges only.  This is still general,
     * because each Edge has a forward DirectedEdge.
     */
    for (Object dirEdge : dirEdges) {
        DirectedEdge de = (DirectedEdge) dirEdge;
        if (!de.isForward()) {
            continue;
        }
        this.findStabbedSegments(stabbingRayLeftPt, de, stabbedSegments);
    }
}

/**
     * for all DirectedEdges in result, form them into MaximalEdgeRings
     */
    private List buildMaximalEdgeRings(Collection dirEdges) {
        List maxEdgeRings = new ArrayList();
        for (Iterator it = dirEdges.iterator(); it.hasNext(); ) {
            DirectedEdge de = (DirectedEdge) it.next();
            if (de.isInResult() && de.getLabel().isArea()) {
                // if this edge has not yet been processed
                if (de.getEdgeRing() == null) {
                    MaximalEdgeRing er = new MaximalEdgeRing(de, geometryFactory);
                    maxEdgeRings.add(er);
                    er.setInResult();
//System.out.println("max node degree = " + er.getMaxDegree());
                }
            }
        }
        return maxEdgeRings;
    }

private void setInteriorEdgesInResult(PlanarGraph graph) {
    for (Object o : graph.getEdgeEnds()) {
        DirectedEdge de = (DirectedEdge) o;
        if (de.getLabel().getLocation(0, Position.RIGHT) == Location.INTERIOR) {
            de.setInResult(true);
        }
    }
}

protected void visitLinkedDirectedEdges(DirectedEdge start) {
    DirectedEdge startDe = start;
    DirectedEdge de = start;
    do {
        Assert.isTrue(de != null, "found null Directed Edge");
        de.setVisited(true);
        de = de.getNext();
    } while (de != startDe);
}

private void collectLines(int opCode) {
    for (Object o : op.getGraph().getEdgeEnds()) {
        DirectedEdge de = (DirectedEdge) o;
        this.collectLineEdge(de, opCode, this.lineEdgesList);
        this.collectBoundaryTouchEdge(de, opCode, this.lineEdgesList);
    }
}

/**
     * Collect line edges which are in the result.
     * Line edges are in the result if they are not part of
     * an area boundary, if they are in the result of the overlay operation,
     * and if they are not covered by a result area.
     *
     * @param de the directed edge to test
     * @param opCode the overlap operation
     * @param edges the list of included line edges
     */
    private void collectLineEdge(DirectedEdge de, int opCode, List edges) {
        Label label = de.getLabel();
        Edge e = de.getEdge();
        // include L edges which are in the result
        if (de.isLineEdge()) {
            if (!de.isVisited() && OverlayOp.isResultOfOp(label, opCode) && !e.isCovered()) {
//Debug.println("de: " + de.getLabel());
//Debug.println("edge: " + e.getLabel());

                edges.add(e);
                de.setVisitedEdge(true);
            }
        }
    }

private List getPotentialResultAreaEdges(DirectedEdgeStar deStar, int opCode) {
//print(System.out);
        List resultAreaEdgeList = new ArrayList();
        for (Iterator it = deStar.iterator(); it.hasNext(); ) {
            DirectedEdge de = (DirectedEdge) it.next();
            if (this.isPotentialResultAreaEdge(de, opCode) || this.isPotentialResultAreaEdge(de.getSym(), opCode)) {
                resultAreaEdgeList.add(de);
            }
        }
        return resultAreaEdgeList;
    }

private boolean isPotentialResultAreaEdge(DirectedEdge de, int opCode) {
    // mark all dirEdges with the appropriate label
    Label label = de.getLabel();
    return label.isArea()
            && !de.isInteriorAreaEdge()
            && OverlayOp.isResultOfOp(
            label.getLocation(0, Position.RIGHT),
            label.getLocation(1, Position.RIGHT),
            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);
}

public List buildMinimalRings() {
    List minEdgeRings = new ArrayList();
    DirectedEdge de = this.startDe;
    do {
        if (de.getMinEdgeRing() == null) {
            EdgeRing minEr = new MinimalEdgeRing(de, this.geometryFactory);
            minEdgeRings.add(minEr);
        }
        de = de.getNext();
    } while (de != this.startDe);
    return minEdgeRings;
}

/**
     * If both a dirEdge and its sym are marked as being in the result, cancel
     * them out.
     */
    private void cancelDuplicateResultEdges() {
        // remove any dirEdges whose sym is also included
        // (they "cancel each other out")
        for (Object o : graph.getEdgeEnds()) {
            DirectedEdge de = (DirectedEdge) o;
            DirectedEdge sym = de.getSym();
            if (de.isInResult() && sym.isInResult()) {
                de.setInResult(false);
                sym.setInResult(false);
//Debug.print("cancelled "); Debug.println(de); Debug.println(sym);
            }
        }
    }

public void findEdge(List dirEdgeList) {
    /**
     * Check all forward DirectedEdges only.  This is still general,
     * because each edge has a forward DirectedEdge.
     */
    for (Object aDirEdgeList : dirEdgeList) {
        DirectedEdge de = (DirectedEdge) aDirEdgeList;
        if (!de.isForward()) {
            continue;
        }
        this.checkForRightmostCoordinate(de);
    }

    /**
     * If the rightmost point is a node, we need to identify which of
     * the incident edges is rightmost.
     */
    Assert.isTrue(this.minIndex != 0 || this.minCoord.equals(this.minDe.getCoordinate()), "inconsistency in rightmost processing");
    if (this.minIndex == 0) {
        this.findRightmostEdgeAtNode();
    } else {
        this.findRightmostEdgeAtVertex();
    }
    /**
     * now check that the extreme side is the R side.
     * If not, use the sym instead.
     */
    this.orientedDe = this.minDe;
    int rightmostSide = this.getRightmostSide(this.minDe, this.minIndex);
    if (rightmostSide == Position.LEFT) {
        this.orientedDe = this.minDe.getSym();
    }
}

private void checkForRightmostCoordinate(DirectedEdge de) {
    Coordinate[] coord = de.getEdge().getCoordinates();
    for (int i = 0; i < coord.length - 1; i++) {
        // only check vertices which are the start or end point of a non-horizontal segment
        // <FIX> MD 19 Sep 03 - NO!  we can test all vertices, since the rightmost must have a non-horiz segment adjacent to it
        if (this.minCoord == null || coord[i].x > this.minCoord.x) {
            this.minDe = de;
            this.minIndex = i;
            this.minCoord = coord[i];
        }
        //}
    }
}

private int getRightmostSide(DirectedEdge de, int index) {
    int side = this.getRightmostSideOfSegment(de, index);
    if (side < 0) {
        side = this.getRightmostSideOfSegment(de, index - 1);
    }
    if (side < 0) {
        // reaching here can indicate that segment is horizontal
        //Assert.shouldNeverReachHere("problem with finding rightmost side of segment at " + de.getCoordinate());
        // testing only
        this.minCoord = null;
        this.checkForRightmostCoordinate(de);
    }
    return side;
}

/**
 * Computes the envelope of the edges in the subgraph.
 * The envelope is cached after being computed.
 *
 * @return the envelope of the graph.
 */
public Envelope getEnvelope() {
    if (this.env == null) {
        Envelope edgeEnv = new Envelope();
        for (Object aDirEdgeList : dirEdgeList) {
            DirectedEdge dirEdge = (DirectedEdge) aDirEdgeList;
            Coordinate[] pts = dirEdge.getEdge().getCoordinates();
            for (int i = 0; i < pts.length - 1; i++) {
                edgeEnv.expandToInclude(pts[i]);
            }
        }
        this.env = edgeEnv;
    }
    return this.env;
}

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);
                }
            }
        }
    }

/**
 * 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);
}

public List buildMinimalRings() {
    List minEdgeRings = new ArrayList();
    DirectedEdge de = startDe;
    do {
        if (de.getMinEdgeRing() == null) {
            EdgeRing minEr = new MinimalEdgeRing(de, geometryFactory);
            minEdgeRings.add(minEr);
        }
        de = de.getNext();
    } while (de != startDe);
    return minEdgeRings;
}

/**
 * Finds all non-horizontal segments intersecting the stabbing line
 * in the list of dirEdges.
 * The stabbing line is the ray to the right of stabbingRayLeftPt.
 *
 * @param stabbingRayLeftPt the left-hand origin of the stabbing line
 * @param stabbedSegments   the current list of {@link DepthSegments} intersecting the stabbing line
 */
private void findStabbedSegments(Coordinate stabbingRayLeftPt,
                                 List dirEdges,
                                 List stabbedSegments) {
    /**
     * Check all forward DirectedEdges only.  This is still general,
     * because each Edge has a forward DirectedEdge.
     */
    for (Iterator i = dirEdges.iterator(); i.hasNext(); ) {
        DirectedEdge de = (DirectedEdge) i.next();
        if (!de.isForward())
            continue;
        findStabbedSegments(stabbingRayLeftPt, de, stabbedSegments);
    }
}

/**
 * Finds all non-horizontal segments intersecting the stabbing line
 * in the input dirEdge.
 * The stabbing line is the ray to the right of stabbingRayLeftPt.
 *
 * @param stabbingRayLeftPt the left-hand origin of the stabbing line
 * @param stabbedSegments   the current list of {@link DepthSegments} intersecting the stabbing line
 */
private void findStabbedSegments(Coordinate stabbingRayLeftPt,
                                 DirectedEdge dirEdge,
                                 List stabbedSegments) {
    Coordinate[] pts = dirEdge.getEdge().getCoordinates();
    for (int i = 0; i < pts.length - 1; i++) {
        seg.p0 = pts[i];
        seg.p1 = pts[i + 1];
        // ensure segment always points upwards
        if (seg.p0.y > seg.p1.y)
            seg.reverse();

        // skip segment if it is left of the stabbing line
        double maxx = Math.max(seg.p0.x, seg.p1.x);
        if (maxx < stabbingRayLeftPt.x)
            continue;

        // skip horizontal segments (there will be a non-horizontal one carrying the same depth info
        if (seg.isHorizontal())
            continue;

        // skip if segment is above or below stabbing line
        if (stabbingRayLeftPt.y < seg.p0.y || stabbingRayLeftPt.y > seg.p1.y)
            continue;

        // skip if stabbing ray is right of the segment
        if (CGAlgorithms.computeOrientation(seg.p0, seg.p1, stabbingRayLeftPt)
                == CGAlgorithms.RIGHT)
            continue;

        // stabbing line cuts this segment, so record it
        int depth = dirEdge.getDepth(Position.LEFT);
        // if segment direction was flipped, use RHS depth instead
        if (!seg.p0.equals(pts[i]))
            depth = dirEdge.getDepth(Position.RIGHT);
        DepthSegment ds = new DepthSegment(seg, depth);
        stabbedSegments.add(ds);
    }
}

private void testLinkResultDirectedEdges(DirectedEdgeStar deStar, int opCode) {
        // make sure edges are copied to resultAreaEdges list
        List ringEdges = this.getPotentialResultAreaEdges(deStar, opCode);
        // find first area edge (if any) to start linking at
        DirectedEdge firstOut = null;
        DirectedEdge incoming = null;
        int state = this.SCANNING_FOR_INCOMING;
        // link edges in CCW order
        for (Object ringEdge : ringEdges) {
            DirectedEdge nextOut = (DirectedEdge) ringEdge;
            DirectedEdge nextIn = nextOut.getSym();

            // skip de's that we're not interested in
            if (!nextOut.getLabel().isArea()) {
                continue;
            }

            // record first outgoing edge, in order to link the last incoming edge
            if (firstOut == null
                    && this.isPotentialResultAreaEdge(nextOut, opCode)) {
                firstOut = nextOut;
            }
            // assert: sym.isInResult() == false, since pairs of dirEdges should have been removed already

            switch (state) {
                case SCANNING_FOR_INCOMING:
                    if (!this.isPotentialResultAreaEdge(nextIn, opCode)) {
                        continue;
                    }
                    incoming = nextIn;
                    state = this.LINKING_TO_OUTGOING;
                    break;
                case LINKING_TO_OUTGOING:
                    if (!this.isPotentialResultAreaEdge(nextOut, opCode)) {
                        continue;
                    }
                    //incoming.setNext(nextOut);
                    state = this.SCANNING_FOR_INCOMING;
                    break;
            }
        }
//Debug.print(this);
        if (state == this.LINKING_TO_OUTGOING) {
//Debug.print(firstOut == null, this);
            if (firstOut == null) {
                throw new TopologyException("no outgoing dirEdge found", deStar.getCoordinate());
            }
        }
    }

public MaximalEdgeRing(DirectedEdge start, GeometryFactory geometryFactory) {
    super(start, geometryFactory);
}

@Override
public DirectedEdge getNext(DirectedEdge de) {
    return de.getNext();
}

@Override
public void setEdgeRing(DirectedEdge de, EdgeRing er) {
    de.setEdgeRing(er);
}

public MinimalEdgeRing(DirectedEdge start, GeometryFactory geometryFactory) {
    super(start, geometryFactory);
}

@Override
public DirectedEdge getNext(DirectedEdge de) {
    return de.getNextMin();
}

@Override
public void setEdgeRing(DirectedEdge de, EdgeRing er) {
    de.setMinEdgeRing(er);
}

public DirectedEdge getEdge() {
    return this.orientedDe;
}

private void clearVisitedEdges() {
    for (Object aDirEdgeList : dirEdgeList) {
        DirectedEdge de = (DirectedEdge) aDirEdgeList;
        de.setVisited(false);
    }
}

private void copySymDepths(DirectedEdge de) {
    DirectedEdge sym = de.getSym();
    sym.setDepth(Position.LEFT, de.getDepth(Position.RIGHT));
    sym.setDepth(Position.RIGHT, de.getDepth(Position.LEFT));
}