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

/**
     * Insert nodes for all intersections on the edges of a Geometry.
     * Label the created nodes the same as the edge label if they do not already have a label.
     * This allows nodes created by either self-intersections or
     * mutual intersections to be labelled.
     * Endpoint nodes will already be labelled from when they were inserted.
     */
    private void computeIntersectionNodes(int argIndex) {
        for (Iterator i = this.arg[argIndex].getEdgeIterator(); i.hasNext(); ) {
            Edge e = (Edge) i.next();
            int eLoc = e.getLabel().getLocation(argIndex);
            for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
                EdgeIntersection ei = (EdgeIntersection) eiIt.next();
                RelateNode n = (RelateNode) this.nodes.addNode(ei.coord);
                if (eLoc == Location.BOUNDARY) {
                    n.setLabelBoundary(argIndex);
                } else {
                    if (n.getLabel().isNull(argIndex)) {
                        n.setLabel(argIndex, Location.INTERIOR);
                    }
                }
//Debug.println(n);
            }
        }
    }

/**
     * For all intersections on the edges of a Geometry,
     * label the corresponding node IF it doesn't already have a label.
     * This allows nodes created by either self-intersections or
     * mutual intersections to be labelled.
     * Endpoint nodes will already be labelled from when they were inserted.
     */
    private void labelIntersectionNodes(int argIndex) {
        for (Iterator i = this.arg[argIndex].getEdgeIterator(); i.hasNext(); ) {
            Edge e = (Edge) i.next();
            int eLoc = e.getLabel().getLocation(argIndex);
            for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
                EdgeIntersection ei = (EdgeIntersection) eiIt.next();
                RelateNode n = (RelateNode) this.nodes.find(ei.coord);
                if (n.getLabel().isNull(argIndex)) {
                    if (eLoc == Location.BOUNDARY) {
                        n.setLabelBoundary(argIndex);
                    } else {
                        n.setLabel(argIndex, Location.INTERIOR);
                    }
                }
//n.print(System.out);
            }
        }
    }

/**
     * update the IM with the sum of the IMs for each component
     */
    private void updateIM(IntersectionMatrix im) {
//Debug.println(im);
        for (Object isolatedEdge : isolatedEdges) {
            Edge e = (Edge) isolatedEdge;
            e.updateIM(im);
//Debug.println(im);
        }
        for (Iterator ni = this.nodes.iterator(); ni.hasNext(); ) {
            RelateNode node = (RelateNode) ni.next();
            node.updateIM(im);
//Debug.println(im);
            node.updateIMFromEdges(im);
//Debug.println(im);
//node.print(System.out);
        }
    }

/**
     * Create a StubEdge for the edge after the intersection eiCurr.
     * The next intersection is provided
     * in case it is the endpoint for the stub edge.
     * Otherwise, the next point from the parent edge will be the endpoint.
     * <br>
     * eiCurr will always be an EdgeIntersection, but eiNext may be null.
     */
    void createEdgeEndForNext(
            Edge edge,
            List l,
            EdgeIntersection eiCurr,
            EdgeIntersection eiNext) {

        int iNext = eiCurr.segmentIndex + 1;
        // if there is no next edge there is nothing to do
        if (iNext >= edge.getNumPoints() && eiNext == null) {
            return;
        }

        Coordinate pNext = edge.getCoordinate(iNext);

        // if the next intersection is in the same segment as the current, use it as the endpoint
        if (eiNext != null && eiNext.segmentIndex == eiCurr.segmentIndex) {
            pNext = eiNext.coord;
        }

        EdgeEnd e = new EdgeEnd(edge, eiCurr.coord, pNext, new Label(edge.getLabel()));
//Debug.println(e);
        l.add(e);
    }

/**
     * Insert nodes for all intersections on the edges of a Geometry.
     * Label the created nodes the same as the edge label if they do not already have a label.
     * This allows nodes created by either self-intersections or
     * mutual intersections to be labelled.
     * Endpoint nodes will already be labelled from when they were inserted.
     * <p>
     * Precondition: edge intersections have been computed.
     */
    public void computeIntersectionNodes(GeometryGraph geomGraph, int argIndex) {
        for (Iterator edgeIt = geomGraph.getEdgeIterator(); edgeIt.hasNext(); ) {
            Edge e = (Edge) edgeIt.next();
            int eLoc = e.getLabel().getLocation(argIndex);
            for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
                EdgeIntersection ei = (EdgeIntersection) eiIt.next();
                RelateNode n = (RelateNode) this.nodes.addNode(ei.coord);
                if (eLoc == Location.BOUNDARY) {
                    n.setLabelBoundary(argIndex);
                } else {
                    if (n.getLabel().isNull(argIndex)) {
                        n.setLabel(argIndex, Location.INTERIOR);
                    }
                }
//Debug.println(n);
            }
        }
    }

/**
 * Find a point from the list of testCoords
 * that is NOT a node in the edge for the list of searchCoords
 *
 * @return the point found, or <code>null</code> if none found
 */
public static Coordinate findPtNotNode(
        Coordinate[] testCoords,
        LinearRing searchRing,
        GeometryGraph graph) {
    // find edge corresponding to searchRing.
    Edge searchEdge = graph.findEdge(searchRing);
    // find a point in the testCoords which is not a node of the searchRing
    EdgeIntersectionList eiList = searchEdge.getEdgeIntersectionList();
    // somewhat inefficient - is there a better way? (Use a node map, for instance?)
    for (Coordinate pt : testCoords) {
        if (!eiList.isIntersection(pt)) {
            return pt;
        }
    }
    return null;
}

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

/**
 * Tests that no edge intersection is the endpoint of a closed line.
 * This ensures that closed lines are not touched at their endpoint,
 * which is an interior point according to the Mod-2 rule
 * To check this we compute the degree of each endpoint.
 * The degree of endpoints of closed lines
 * must be exactly 2.
 */
private boolean hasClosedEndpointIntersection(GeometryGraph graph) {
    Map endPoints = new TreeMap();
    for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
        Edge e = (Edge) i.next();
        int maxSegmentIndex = e.getMaximumSegmentIndex();
        boolean isClosed = e.isClosed();
        Coordinate p0 = e.getCoordinate(0);
        this.addEndpoint(endPoints, p0, isClosed);
        Coordinate p1 = e.getCoordinate(e.getNumPoints() - 1);
        this.addEndpoint(endPoints, p1, isClosed);
    }

    for (Object o : endPoints.values()) {
        EndpointInfo eiInfo = (EndpointInfo) o;
        if (eiInfo.isClosed && eiInfo.degree != 2) {
            this.nonSimpleLocation = eiInfo.getCoordinate();
            return true;
        }
    }
    return false;
}

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

private void computeNodedEdges(List bufferSegStrList, PrecisionModel precisionModel) {
        Noder noder = this.getNoder(precisionModel);
        noder.computeNodes(bufferSegStrList);
        Collection nodedSegStrings = noder.getNodedSubstrings();
// DEBUGGING ONLY
//BufferDebug.saveEdges(nodedEdges, "run" + BufferDebug.runCount + "_nodedEdges");

        for (Object nodedSegString : nodedSegStrings) {
            SegmentString segStr = (SegmentString) nodedSegString;

            /**
             * Discard edges which have zero length,
             * since they carry no information and cause problems with topology building
             */
            Coordinate[] pts = segStr.getCoordinates();
            if (pts.length == 2 && pts[0].equals2D(pts[1])) {
                continue;
            }

            Label oldLabel = (Label) segStr.getData();
            Edge edge = new Edge(segStr.getCoordinates(), new Label(oldLabel));
            this.insertUniqueEdge(edge);
        }
        //saveEdges(edgeList.getEdges(), "run" + runCount + "_collapsedEdges");
    }

/**
 * A trivial intersection is an apparent self-intersection which in fact
 * is simply the point shared by adjacent line segments.
 * Note that closed edges require a special check for the point shared by the beginning
 * and end segments.
 */
private boolean isTrivialIntersection(Edge e0, int segIndex0, Edge e1, int segIndex1) {
    if (e0 == e1) {
        if (this.li.getIntersectionNum() == 1) {
            if (isAdjacentSegments(segIndex0, segIndex1)) {
                return true;
            }
            if (e0.isClosed()) {
                int maxSegIndex = e0.getNumPoints() - 1;
                if ((segIndex0 == 0 && segIndex1 == maxSegIndex)
                        || (segIndex1 == 0 && segIndex0 == maxSegIndex)) {
                    return true;
                }
            }
        }
    }
    return false;
}

/**
 * Find a point from the list of testCoords
 * that is NOT a node in the edge for the list of searchCoords
 *
 * @return the point found, or <code>null</code> if none found
 */
public static Coordinate findPtNotNode(
        Coordinate[] testCoords,
        LinearRing searchRing,
        GeometryGraph graph) {
    // find edge corresponding to searchRing.
    Edge searchEdge = graph.findEdge(searchRing);
    // find a point in the testCoords which is not a node of the searchRing
    EdgeIntersectionList eiList = searchEdge.getEdgeIntersectionList();
    // somewhat inefficient - is there a better way? (Use a node map, for instance?)
    for (int i = 0; i < testCoords.length; i++) {
        Coordinate pt = testCoords[i];
        if (!eiList.isIntersection(pt))
            return pt;
    }
    return null;
}

/**
 * Tests that no edge intersection is the endpoint of a closed line.
 * This ensures that closed lines are not touched at their endpoint,
 * which is an interior point according to the Mod-2 rule
 * To check this we compute the degree of each endpoint.
 * The degree of endpoints of closed lines
 * must be exactly 2.
 */
private boolean hasClosedEndpointIntersection(GeometryGraph graph) {
    Map endPoints = new TreeMap();
    for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
        Edge e = (Edge) i.next();
        int maxSegmentIndex = e.getMaximumSegmentIndex();
        boolean isClosed = e.isClosed();
        Coordinate p0 = e.getCoordinate(0);
        addEndpoint(endPoints, p0, isClosed);
        Coordinate p1 = e.getCoordinate(e.getNumPoints() - 1);
        addEndpoint(endPoints, p1, isClosed);
    }

    for (Iterator i = endPoints.values().iterator(); i.hasNext(); ) {
        EndpointInfo eiInfo = (EndpointInfo) i.next();
        if (eiInfo.isClosed && eiInfo.degree != 2) {
            nonSimpleLocation = eiInfo.getCoordinate();
            return true;
        }
    }
    return false;
}

/**
 * A trivial intersection is an apparent self-intersection which in fact
 * is simply the point shared by adjacent line segments.
 * Note that closed edges require a special check for the point shared by the beginning
 * and end segments.
 */
private boolean isTrivialIntersection(Edge e0, int segIndex0, Edge e1, int segIndex1) {
    if (e0 == e1) {
        if (li.getIntersectionNum() == 1) {
            if (isAdjacentSegments(segIndex0, segIndex1))
                return true;
            if (e0.isClosed()) {
                int maxSegIndex = e0.getNumPoints() - 1;
                if ((segIndex0 == 0 && segIndex1 == maxSegIndex)
                        || (segIndex1 == 0 && segIndex0 == maxSegIndex)) {
                    return true;
                }
            }
        }
    }
    return false;
}

/**
 * Processes isolated edges by computing their labelling and adding them
 * to the isolated edges list.
 * Isolated edges are guaranteed not to touch the boundary of the target (since if they
 * did, they would have caused an intersection to be computed and hence would
 * not be isolated)
 */
private void labelIsolatedEdges(int thisIndex, int targetIndex) {
    for (Iterator ei = this.arg[thisIndex].getEdgeIterator(); ei.hasNext(); ) {
        Edge e = (Edge) ei.next();
        if (e.isIsolated()) {
            this.labelIsolatedEdge(e, targetIndex, this.arg[targetIndex].getGeometry());
            this.isolatedEdges.add(e);
        }
    }
}

/**
     * Label an isolated edge of a graph with its relationship to the target geometry.
     * If the target has dim 2 or 1, the edge can either be in the interior or the exterior.
     * If the target has dim 0, the edge must be in the exterior
     */
    private void labelIsolatedEdge(Edge e, int targetIndex, Geometry target) {
        // this won't work for GeometryCollections with both dim 2 and 1 geoms
        if (target.getDimension() > 0) {
            // since edge is not in boundary, may not need the full generality of PointLocator?
            // Possibly should use ptInArea locator instead?  We probably know here
            // that the edge does not touch the bdy of the target Geometry
            int loc = this.ptLocator.locate(e.getCoordinate(), target);
            e.getLabel().setAllLocations(targetIndex, loc);
        } else {
            e.getLabel().setAllLocations(targetIndex, Location.EXTERIOR);
        }
//System.out.println(e.getLabel());
    }

public List computeEdgeEnds(Iterator edges) {
    List l = new ArrayList();
    for (Iterator i = edges; i.hasNext(); ) {
        Edge e = (Edge) i.next();
        this.computeEdgeEnds(e, l);
    }
    return l;
}

/**
     * Creates stub edges for all the intersections in this
     * Edge (if any) and inserts them into the graph.
     */
    public void computeEdgeEnds(Edge edge, List l) {
        EdgeIntersectionList eiList = edge.getEdgeIntersectionList();
//Debug.print(eiList);
        // ensure that the list has entries for the first and last point of the edge
        eiList.addEndpoints();

        Iterator it = eiList.iterator();
        EdgeIntersection eiPrev = null;
        EdgeIntersection eiCurr = null;
        // no intersections, so there is nothing to do
        if (!it.hasNext()) {
            return;
        }
        EdgeIntersection eiNext = (EdgeIntersection) it.next();
        do {
            eiPrev = eiCurr;
            eiCurr = eiNext;
            eiNext = null;
            if (it.hasNext()) {
                eiNext = (EdgeIntersection) it.next();
            }

            if (eiCurr != null) {
                this.createEdgeEndForPrev(edge, l, eiCurr, eiPrev);
                this.createEdgeEndForNext(edge, l, eiCurr, eiNext);
            }
        } while (eiCurr != null);
    }

/**
     * Create a EdgeStub for the edge before the intersection eiCurr.
     * The previous intersection is provided
     * in case it is the endpoint for the stub edge.
     * Otherwise, the previous point from the parent edge will be the endpoint.
     * <br>
     * eiCurr will always be an EdgeIntersection, but eiPrev may be null.
     */
    void createEdgeEndForPrev(
            Edge edge,
            List l,
            EdgeIntersection eiCurr,
            EdgeIntersection eiPrev) {

        int iPrev = eiCurr.segmentIndex;
        if (eiCurr.dist == 0.0) {
            // if at the start of the edge there is no previous edge
            if (iPrev == 0) {
                return;
            }
            iPrev--;
        }
        Coordinate pPrev = edge.getCoordinate(iPrev);
        // if prev intersection is past the previous vertex, use it instead
        if (eiPrev != null && eiPrev.segmentIndex >= iPrev) {
            pPrev = eiPrev.coord;
        }

        Label label = new Label(edge.getLabel());
        // since edgeStub is oriented opposite to it's parent edge, have to flip sides for edge label
        label.flip();
        EdgeEnd e = new EdgeEnd(edge, eiCurr.coord, pPrev, label);
//e.print(System.out);  System.out.println();
        l.add(e);
    }

/**
 * Check that there is no ring which self-intersects (except of course at its endpoints).
 * This is required by OGC topology rules (but not by other models
 * such as ESRI SDE, which allow inverted shells and exverted holes).
 *
 * @param graph the topology graph of the geometry
 */
private void checkNoSelfIntersectingRings(GeometryGraph graph) {
    for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
        Edge e = (Edge) i.next();
        this.checkNoSelfIntersectingRing(e.getEdgeIntersectionList());
        if (this.validErr != null) {
            return;
        }
    }
}

/**
     * 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 void buildLines(int opCode) {
    for (Object aLineEdgesList : lineEdgesList) {
        Edge e = (Edge) aLineEdgesList;
        Label label = e.getLabel();
        LineString line = this.geometryFactory.createLineString(e.getCoordinates());
        this.resultLineList.add(line);
        e.setInResult(true);
    }
}

private void labelIsolatedLines(List edgesList) {
        for (Object anEdgesList : edgesList) {
            Edge e = (Edge) anEdgesList;
            Label label = e.getLabel();
//n.print(System.out);
            if (e.isIsolated()) {
                if (label.isNull(0)) {
                    this.labelIsolatedLine(e, 0);
                } else {
                    this.labelIsolatedLine(e, 1);
                }
            }
        }
    }

public List getNodedEdges() {
        EdgeSetIntersector esi = new SimpleMCSweepLineIntersector();
        SegmentIntersector si = new SegmentIntersector(this.li, true, false);
        esi.computeIntersections(this.inputEdges, si, true);
//Debug.println("has proper int = " + si.hasProperIntersection());

        List splitEdges = new ArrayList();
        for (Object inputEdge : inputEdges) {
            Edge e = (Edge) inputEdge;
            e.getEdgeIntersectionList().addSplitEdges(splitEdges);
        }
        return splitEdges;
    }

/**
 * Update the labels for edges according to their depths.
 * For each edge, the depths are first normalized.
 * Then, if the depths for the edge are equal,
 * this edge must have collapsed into a line edge.
 * If the depths are not equal, update the label
 * with the locations corresponding to the depths
 * (i.e. a depth of 0 corresponds to a Location of EXTERIOR,
 * a depth of 1 corresponds to INTERIOR)
 */
private void computeLabelsFromDepths() {
    for (Iterator it = this.edgeList.iterator(); it.hasNext(); ) {
        Edge e = (Edge) it.next();
        Label lbl = e.getLabel();
        Depth depth = e.getDepth();
        /**
         * Only check edges for which there were duplicates,
         * since these are the only ones which might
         * be the result of dimensional collapses.
         */
        if (!depth.isNull()) {
            depth.normalize();
            for (int i = 0; i < 2; i++) {
                if (!lbl.isNull(i) && lbl.isArea() && !depth.isNull(i)) {
                    /**
                     * if the depths are equal, this edge is the result of
                     * the dimensional collapse of two or more edges.
                     * It has the same location on both sides of the edge,
                     * so it has collapsed to a line.
                     */
                    if (depth.getDelta(i) == 0) {
                        lbl.toLine(i);
                    } else {
                        /**
                         * This edge may be the result of a dimensional collapse,
                         * but it still has different locations on both sides.  The
                         * label of the edge must be updated to reflect the resultant
                         * side locations indicated by the depth values.
                         */
                        Assert.isTrue(!depth.isNull(i, Position.LEFT), "depth of LEFT side has not been initialized");
                        lbl.setLocation(i, Position.LEFT, depth.getLocation(i, Position.LEFT));
                        Assert.isTrue(!depth.isNull(i, Position.RIGHT), "depth of RIGHT side has not been initialized");
                        lbl.setLocation(i, Position.RIGHT, depth.getLocation(i, Position.RIGHT));
                    }
                }
            }
        }
    }
}

/**
     * If edges which have undergone dimensional collapse are found,
     * replace them with a new edge which is a L edge
     */
    private void replaceCollapsedEdges() {
        List newEdges = new ArrayList();
        for (Iterator it = this.edgeList.iterator(); it.hasNext(); ) {
            Edge e = (Edge) it.next();
            if (e.isCollapsed()) {
//Debug.print(e);
                it.remove();
                newEdges.add(e.getCollapsedEdge());
            }
        }
        this.edgeList.addAll(newEdges);
    }

/**
 * For all edges, check if there are any intersections which are NOT at an endpoint.
 * The Geometry is not simple if there are intersections not at endpoints.
 */
private boolean hasNonEndpointIntersection(GeometryGraph graph) {
    for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
        Edge e = (Edge) i.next();
        int maxSegmentIndex = e.getMaximumSegmentIndex();
        for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
            EdgeIntersection ei = (EdgeIntersection) eiIt.next();
            if (!ei.isEndPoint(maxSegmentIndex)) {
                this.nonSimpleLocation = ei.getCoordinate();
                return true;
            }
        }
    }
    return false;
}

private void add(List edges) {
    for (Object edge1 : edges) {
        Edge edge = (Edge) edge1;
        // edge is its own group
        this.add(edge, edge);
    }
}

private void add(Edge edge, Object edgeSet) {
    Coordinate[] pts = edge.getCoordinates();
    for (int i = 0; i < pts.length - 1; i++) {
        SweepLineSegment ss = new SweepLineSegment(edge, i);
        SweepLineEvent insertEvent = new SweepLineEvent(edgeSet, ss.getMinX(), null, ss);
        this.events.add(insertEvent);
        this.events.add(new SweepLineEvent(edgeSet, ss.getMaxX(), insertEvent, ss));
    }
}

@Override
public void computeIntersections(List edges, SegmentIntersector si, boolean testAllSegments) {
    this.nOverlaps = 0;

    for (Object edge2 : edges) {
        Edge edge0 = (Edge) edge2;
        for (Object edge : edges) {
            Edge edge1 = (Edge) edge;
            if (testAllSegments || edge0 != edge1) {
                this.computeIntersects(edge0, edge1, si);
            }
        }
    }
}

@Override
public void computeIntersections(List edges0, List edges1, SegmentIntersector si) {
    this.nOverlaps = 0;

    for (Object anEdges0 : edges0) {
        Edge edge0 = (Edge) anEdges0;
        for (Object anEdges1 : edges1) {
            Edge edge1 = (Edge) anEdges1;
            this.computeIntersects(edge0, edge1, si);
        }
    }
}

/**
 * Performs a brute-force comparison of every segment in each Edge.
 * This has n^2 performance, and is about 100 times slower than using
 * monotone chains.
 */
private void computeIntersects(Edge e0, Edge e1, SegmentIntersector si) {
    Coordinate[] pts0 = e0.getCoordinates();
    Coordinate[] pts1 = e1.getCoordinates();
    for (int i0 = 0; i0 < pts0.length - 1; i0++) {
        for (int i1 = 0; i1 < pts1.length - 1; i1++) {
            si.addIntersections(e0, i0, e1, i1);
        }
    }
}

private void add(List edges) {
    for (Object edge1 : edges) {
        Edge edge = (Edge) edge1;
        // edge is its own group
        this.add(edge, edge);
    }
}

private void add(Edge edge, Object edgeSet) {
    MonotoneChainEdge mce = edge.getMonotoneChainEdge();
    int[] startIndex = mce.getStartIndexes();
    for (int i = 0; i < startIndex.length - 1; i++) {
        MonotoneChain mc = new MonotoneChain(mce, i);
        SweepLineEvent insertEvent = new SweepLineEvent(edgeSet, mce.getMinX(i), null, mc);
        this.events.add(insertEvent);
        this.events.add(new SweepLineEvent(edgeSet, mce.getMaxX(i), insertEvent, mc));
    }
}

/**
 * Check that there is no ring which self-intersects (except of course at its endpoints).
 * This is required by OGC topology rules (but not by other models
 * such as ESRI SDE, which allow inverted shells and exverted holes).
 *
 * @param graph the topology graph of the geometry
 */
private void checkNoSelfIntersectingRings(GeometryGraph graph) {
    for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
        Edge e = (Edge) i.next();
        checkNoSelfIntersectingRing(e.getEdgeIntersectionList());
        if (validErr != null)
            return;
    }
}

public List getNodedEdges() {
        EdgeSetIntersector esi = new SimpleMCSweepLineIntersector();
        SegmentIntersector si = new SegmentIntersector(li, true, false);
        esi.computeIntersections(inputEdges, si, true);
//Debug.println("has proper int = " + si.hasProperIntersection());

        List splitEdges = new ArrayList();
        for (Iterator i = inputEdges.iterator(); i.hasNext(); ) {
            Edge e = (Edge) i.next();
            e.getEdgeIntersectionList().addSplitEdges(splitEdges);
        }
        return splitEdges;
    }

/**
 * For all edges, check if there are any intersections which are NOT at an endpoint.
 * The Geometry is not simple if there are intersections not at endpoints.
 */
private boolean hasNonEndpointIntersection(GeometryGraph graph) {
    for (Iterator i = graph.getEdgeIterator(); i.hasNext(); ) {
        Edge e = (Edge) i.next();
        int maxSegmentIndex = e.getMaximumSegmentIndex();
        for (Iterator eiIt = e.getEdgeIntersectionList().iterator(); eiIt.hasNext(); ) {
            EdgeIntersection ei = (EdgeIntersection) eiIt.next();
            if (!ei.isEndPoint(maxSegmentIndex)) {
                nonSimpleLocation = ei.getCoordinate();
                return true;
            }
        }
    }
    return false;
}

private void add(List edges) {
    for (Iterator i = edges.iterator(); i.hasNext(); ) {
        Edge edge = (Edge) i.next();
        // edge is its own group
        add(edge, edge);
    }
}

private void add(Edge edge, Object edgeSet) {
    Coordinate[] pts = edge.getCoordinates();
    for (int i = 0; i < pts.length - 1; i++) {
        SweepLineSegment ss = new SweepLineSegment(edge, i);
        SweepLineEvent insertEvent = new SweepLineEvent(edgeSet, ss.getMinX(), null);
        events.add(insertEvent);
        events.add(new SweepLineEvent(ss.getMaxX(), insertEvent));
    }
}