import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
public void build(GeometryGraph geomGraph) {
        // compute nodes for intersections between previously noded edges
        this.computeIntersectionNodes(geomGraph, 0);
        /**
         * Copy the labelling for the nodes in the parent Geometry.  These override
         * any labels determined by intersections.
         */
        this.copyNodesAndLabels(geomGraph, 0);

        /**
         * Build EdgeEnds for all intersections.
         */
        EdgeEndBuilder eeBuilder = new EdgeEndBuilder();
        List eeList = eeBuilder.computeEdgeEnds(geomGraph.getEdgeIterator());
        this.insertEdgeEnds(eeList);

//Debug.println("==== NodeList ===");
//Debug.print(nodes);
    }
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
     * 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);
            }
        }
    }
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * 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;
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Checks validity of a LinearRing.
 */
private void checkValid(LinearRing g) {
    this.checkInvalidCoordinates(g.getCoordinates());
    if (this.validErr != null) {
        return;
    }
    this.checkClosedRing(g);
    if (this.validErr != null) {
        return;
    }

    GeometryGraph graph = new GeometryGraph(0, g);
    this.checkTooFewPoints(graph);
    if (this.validErr != null) {
        return;
    }
    LineIntersector li = new RobustLineIntersector();
    graph.computeSelfNodes(li, true);
    this.checkNoSelfIntersectingRings(graph);
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Checks that the arrangement of edges in a polygonal geometry graph
 * forms a consistent area.
 *
 * @param graph
 * @see ConsistentAreaTester
 */
private void checkConsistentArea(GeometryGraph graph) {
    ConsistentAreaTester cat = new ConsistentAreaTester(graph);
    boolean isValidArea = cat.isNodeConsistentArea();
    if (!isValidArea) {
        this.validErr = new TopologyValidationError(
                TopologyValidationError.SELF_INTERSECTION,
                cat.getInvalidPoint());
        return;
    }
    if (cat.hasDuplicateRings()) {
        this.validErr = new TopologyValidationError(
                TopologyValidationError.DUPLICATE_RINGS,
                cat.getInvalidPoint());
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Tests that no hole is nested inside another hole.
 * This routine assumes that the holes are disjoint.
 * To ensure this, holes have previously been tested
 * to ensure that:
 * <ul>
 * <li>they do not partially overlap
 * (checked by <code>checkRelateConsistency</code>)
 * <li>they are not identical
 * (checked by <code>checkRelateConsistency</code>)
 * </ul>
 */
private void checkHolesNotNested(Polygon p, GeometryGraph graph) {
    IndexedNestedRingTester nestedTester = new IndexedNestedRingTester(graph);
    //SimpleNestedRingTester nestedTester = new SimpleNestedRingTester(arg[0]);
    //SweeplineNestedRingTester nestedTester = new SweeplineNestedRingTester(arg[0]);

    for (int i = 0; i < p.getNumInteriorRing(); i++) {
        LinearRing innerHole = (LinearRing) p.getInteriorRingN(i);
        nestedTester.add(innerHole);
    }
    boolean isNonNested = nestedTester.isNonNested();
    if (!isNonNested) {
        this.validErr = new TopologyValidationError(
                TopologyValidationError.NESTED_HOLES,
                nestedTester.getNestedPoint());
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Tests that no element polygon is wholly in the interior of another element polygon.
 * <p>
 * Preconditions:
 * <ul>
 * <li>shells do not partially overlap
 * <li>shells do not touch along an edge
 * <li>no duplicate rings exist
 * </ul>
 * This routine relies on the fact that while polygon shells may touch at one or
 * more vertices, they cannot touch at ALL vertices.
 */
private void checkShellsNotNested(MultiPolygon mp, GeometryGraph graph) {
    for (int i = 0; i < mp.getNumGeometries(); i++) {
        Polygon p = (Polygon) mp.getGeometryN(i);
        LinearRing shell = (LinearRing) p.getExteriorRing();
        for (int j = 0; j < mp.getNumGeometries(); j++) {
            if (i == j) {
                continue;
            }
            Polygon p2 = (Polygon) mp.getGeometryN(j);
            this.checkShellNotNested(shell, p2, graph);
            if (this.validErr != null) {
                return;
            }
        }
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * This routine checks to see if a shell is properly contained in a hole.
 * It assumes that the edges of the shell and hole do not
 * properly intersect.
 *
 * @return <code>null</code> if the shell is properly contained, or
 * a Coordinate which is not inside the hole if it is not
 */
private Coordinate checkShellInsideHole(LinearRing shell, LinearRing hole, GeometryGraph graph) {
    Coordinate[] shellPts = shell.getCoordinates();
    Coordinate[] holePts = hole.getCoordinates();
    // TODO: improve performance of this - by sorting pointlists for instance?
    Coordinate shellPt = findPtNotNode(shellPts, hole, graph);
    // if point is on shell but not hole, check that the shell is inside the hole
    if (shellPt != null) {
        boolean insideHole = CGAlgorithms.isPointInRing(shellPt, holePts);
        if (!insideHole) {
            return shellPt;
        }
    }
    Coordinate holePt = findPtNotNode(holePts, shell, graph);
    // if point is on hole but not shell, check that the hole is outside the shell
    if (holePt != null) {
        boolean insideShell = CGAlgorithms.isPointInRing(holePt, shellPts);
        if (insideShell) {
            return holePt;
        }
        return null;
    }
    Assert.shouldNeverReachHere("points in shell and hole appear to be equal");
    return null;
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
private boolean isSimpleLinearGeometry(Geometry geom) {
    if (geom.isEmpty()) {
        return true;
    }
    GeometryGraph graph = new GeometryGraph(0, geom);
    LineIntersector li = new RobustLineIntersector();
    SegmentIntersector si = graph.computeSelfNodes(li, true);
    // if no self-intersection, must be simple
    if (!si.hasIntersection()) {
        return true;
    }
    if (si.hasProperIntersection()) {
        this.nonSimpleLocation = si.getProperIntersectionPoint();
        return false;
    }
    if (this.hasNonEndpointIntersection(graph)) {
        return false;
    }
    if (this.isClosedEndpointsInInterior) {
        if (this.hasClosedEndpointIntersection(graph)) {
            return false;
        }
    }
    return true;
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * 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;
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * 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;
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Checks the validity of a polygon.
 * Sets the validErr flag.
 */
private void checkValid(Polygon g) {
    checkInvalidCoordinates(g);
    if (validErr != null) return;
    checkClosedRings(g);
    if (validErr != null) return;

    GeometryGraph graph = new GeometryGraph(0, g);

    checkTooFewPoints(graph);
    if (validErr != null) return;
    checkConsistentArea(graph);
    if (validErr != null) return;

    if (!isSelfTouchingRingFormingHoleValid) {
        checkNoSelfIntersectingRings(graph);
        if (validErr != null) return;
    }
    checkHolesInShell(g, graph);
    if (validErr != null) return;
    //SLOWcheckHolesNotNested(g);
    checkHolesNotNested(g, graph);
    if (validErr != null) return;
    checkConnectedInteriors(graph);
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Checks that the arrangement of edges in a polygonal geometry graph
 * forms a consistent area.
 *
 * @param graph
 * @see ConsistentAreaTester
 */
private void checkConsistentArea(GeometryGraph graph) {
    ConsistentAreaTester cat = new ConsistentAreaTester(graph);
    boolean isValidArea = cat.isNodeConsistentArea();
    if (!isValidArea) {
        validErr = new TopologyValidationError(
                TopologyValidationError.SELF_INTERSECTION,
                cat.getInvalidPoint());
        return;
    }
    if (cat.hasDuplicateRings()) {
        validErr = new TopologyValidationError(
                TopologyValidationError.DUPLICATE_RINGS,
                cat.getInvalidPoint());
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Tests that no hole is nested inside another hole.
 * This routine assumes that the holes are disjoint.
 * To ensure this, holes have previously been tested
 * to ensure that:
 * <ul>
 * <li>they do not partially overlap
 * (checked by <code>checkRelateConsistency</code>)
 * <li>they are not identical
 * (checked by <code>checkRelateConsistency</code>)
 * </ul>
 */
private void checkHolesNotNested(Polygon p, GeometryGraph graph) {
    IndexedNestedRingTester nestedTester = new IndexedNestedRingTester(graph);
    //SimpleNestedRingTester nestedTester = new SimpleNestedRingTester(arg[0]);
    //SweeplineNestedRingTester nestedTester = new SweeplineNestedRingTester(arg[0]);

    for (int i = 0; i < p.getNumInteriorRing(); i++) {
        LinearRing innerHole = (LinearRing) p.getInteriorRingN(i);
        nestedTester.add(innerHole);
    }
    boolean isNonNested = nestedTester.isNonNested();
    if (!isNonNested) {
        validErr = new TopologyValidationError(
                TopologyValidationError.NESTED_HOLES,
                nestedTester.getNestedPoint());
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
private boolean isSimpleLinearGeometry(Geometry geom) {
    if (geom.isEmpty()) return true;
    GeometryGraph graph = new GeometryGraph(0, geom);
    LineIntersector li = new RobustLineIntersector();
    SegmentIntersector si = graph.computeSelfNodes(li, true);
    // if no self-intersection, must be simple
    if (!si.hasIntersection()) return true;
    if (si.hasProperIntersection()) {
        nonSimpleLocation = si.getProperIntersectionPoint();
        return false;
    }
    if (hasNonEndpointIntersection(graph)) return false;
    if (isClosedEndpointsInInterior) {
        if (hasClosedEndpointIntersection(graph)) return false;
    }
    return true;
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * 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;
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
private void checkTooFewPoints(GeometryGraph graph) {
    if (graph.hasTooFewPoints()) {
        this.validErr = new TopologyValidationError(
                TopologyValidationError.TOO_FEW_POINTS,
                graph.getInvalidPoint());
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * 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;
        }
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
/**
 * Tests that each hole is inside the polygon shell.
 * This routine assumes that the holes have previously been tested
 * to ensure that all vertices lie on the shell oon the same side of it
 * (i.e that the hole rings do not cross the shell ring).
 * In other words, this test is only correct if the ConsistentArea test is passed first.
 * Given this, a simple point-in-polygon test of a single point in the hole can be used,
 * provided the point is chosen such that it does not lie on the shell.
 *
 * @param p the polygon to be tested for hole inclusion
 * @param graph a GeometryGraph incorporating the polygon
 */
private void checkHolesInShell(Polygon p, GeometryGraph graph) {
    LinearRing shell = (LinearRing) p.getExteriorRing();

    //PointInRing pir = new SimplePointInRing(shell);
    //PointInRing pir = new SIRtreePointInRing(shell);
    PointInRing pir = new MCPointInRing(shell);

    for (int i = 0; i < p.getNumInteriorRing(); i++) {

        LinearRing hole = (LinearRing) p.getInteriorRingN(i);
        Coordinate holePt = findPtNotNode(hole.getCoordinates(), shell, graph);
        /**
         * If no non-node hole vertex can be found, the hole must
         * split the polygon into disconnected interiors.
         * This will be caught by a subsequent check.
         */
        if (holePt == null) {
            return;
        }

        boolean outside = !pir.isInside(holePt);
        if (outside) {
            this.validErr = new TopologyValidationError(
                    TopologyValidationError.HOLE_OUTSIDE_SHELL,
                    holePt);
            return;
        }
    }
}
 

import com.vividsolutions.jts.geomgraph.GeometryGraph; //导入依赖的package包/类
private void checkConnectedInteriors(GeometryGraph graph) {
    ConnectedInteriorTester cit = new ConnectedInteriorTester(graph);
    if (!cit.isInteriorsConnected()) {
        this.validErr = new TopologyValidationError(
                TopologyValidationError.DISCONNECTED_INTERIOR,
                cit.getCoordinate());
    }
}