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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

/**
 * Checks validity of a LineString.  Almost anything goes for linestrings!
 */
private void checkValid(LineString g) {
    this.checkInvalidCoordinates(g.getCoordinates());
    if (this.validErr != null) {
        return;
    }
    GeometryGraph graph = new GeometryGraph(0, g);
    this.checkTooFewPoints(graph);
}

/**
 * Checks the validity of a polygon.
 * Sets the validErr flag.
 */
private void checkValid(Polygon g) {
    this.checkInvalidCoordinates(g);
    if (this.validErr != null) {
        return;
    }
    this.checkClosedRings(g);
    if (this.validErr != null) {
        return;
    }

    GeometryGraph graph = new GeometryGraph(0, g);

    this.checkTooFewPoints(graph);
    if (this.validErr != null) {
        return;
    }
    this.checkConsistentArea(graph);
    if (this.validErr != null) {
        return;
    }

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

private void checkTooFewPoints(GeometryGraph graph) {
    if (graph.hasTooFewPoints()) {
        this.validErr = new TopologyValidationError(
                TopologyValidationError.TOO_FEW_POINTS,
                graph.getInvalidPoint());
    }
}

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

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

private void checkConnectedInteriors(GeometryGraph graph) {
    ConnectedInteriorTester cit = new ConnectedInteriorTester(graph);
    if (!cit.isInteriorsConnected()) {
        this.validErr = new TopologyValidationError(
                TopologyValidationError.DISCONNECTED_INTERIOR,
                cit.getCoordinate());
    }
}

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

public GeometryGraphOperation(Geometry g0, Geometry g1, BoundaryNodeRule boundaryNodeRule) {
    // use the most precise model for the result
    if (g0.getPrecisionModel().compareTo(g1.getPrecisionModel()) >= 0) {
        this.setComputationPrecision(g0.getPrecisionModel());
    } else {
        this.setComputationPrecision(g1.getPrecisionModel());
    }

    this.arg = new GeometryGraph[2];
    this.arg[0] = new GeometryGraph(0, g0, boundaryNodeRule);
    this.arg[1] = new GeometryGraph(1, g1, boundaryNodeRule);
}

LineString fullClosedLine(List<LineString> lines) {
    List<Coordinate> tail = new ArrayList<>();

    boolean found;
    do {
        found = false;
        for (int i = 0; i < lines.size(); i++) {
            if (addToClosed(tail, lines.get(i))) {
                lines.remove(i);
                i--;
                found = true;
            }
        }
    } while (found);

    LineString s = GeometryHelper.createLine(tail);
    if (!s.isClosed()) {
        throw new RuntimeException("Non-closed line starts from " + tail.get(0) + " ends to "
                + tail.get(tail.size() - 1));
    }
    if (!s.isSimple()) {
        GeometryGraph graph = new GeometryGraph(0, s);
        LineIntersector li = new RobustLineIntersector();
        SegmentIntersector si = graph.computeSelfNodes(li, true);
        if (si.hasProperInteriorIntersection()) {
            throw new RuntimeException("Self-intersection for " + relation.getObjectCode()
                    + " near point " + si.getProperIntersectionPoint());
        }else {
            throw new RuntimeException("Self-intersected line: " + s);
        }
    }
    return s;
}

/**
 * Checks validity of a LineString.  Almost anything goes for linestrings!
 */
private void checkValid(LineString g) {
    checkInvalidCoordinates(g.getCoordinates());
    if (validErr != null) return;
    GeometryGraph graph = new GeometryGraph(0, g);
    checkTooFewPoints(graph);
}

/**
 * Checks validity of a LinearRing.
 */
private void checkValid(LinearRing g) {
    checkInvalidCoordinates(g.getCoordinates());
    if (validErr != null) return;
    checkClosedRing(g);
    if (validErr != null) return;

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

private void checkTooFewPoints(GeometryGraph graph) {
    if (graph.hasTooFewPoints()) {
        validErr = new TopologyValidationError(
                TopologyValidationError.TOO_FEW_POINTS,
                graph.getInvalidPoint());
        return;
    }
}

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

/**
 * 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) {
            validErr = new TopologyValidationError(
                    TopologyValidationError.HOLE_OUTSIDE_SHELL,
                    holePt);
            return;
        }
    }
}

/**
 * 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);
            checkShellNotNested(shell, p2, graph);
            if (validErr != null) return;
        }
    }
}

/**
 * Check if a shell is incorrectly nested within a polygon.  This is the case
 * if the shell is inside the polygon shell, but not inside a polygon hole.
 * (If the shell is inside a polygon hole, the nesting is valid.)
 * <p/>
 * The algorithm used relies on the fact that the rings must be properly contained.
 * E.g. they cannot partially overlap (this has been previously checked by
 * <code>checkRelateConsistency</code> )
 */
private void checkShellNotNested(LinearRing shell, Polygon p, GeometryGraph graph) {
    Coordinate[] shellPts = shell.getCoordinates();
    // test if shell is inside polygon shell
    LinearRing polyShell = (LinearRing) p.getExteriorRing();
    Coordinate[] polyPts = polyShell.getCoordinates();
    Coordinate shellPt = findPtNotNode(shellPts, polyShell, graph);
    // if no point could be found, we can assume that the shell is outside the polygon
    if (shellPt == null)
        return;
    boolean insidePolyShell = CGAlgorithms.isPointInRing(shellPt, polyPts);
    if (!insidePolyShell) return;

    // if no holes, this is an error!
    if (p.getNumInteriorRing() <= 0) {
        validErr = new TopologyValidationError(
                TopologyValidationError.NESTED_SHELLS,
                shellPt);
        return;
    }

    /**
     * Check if the shell is inside one of the holes.
     * This is the case if one of the calls to checkShellInsideHole
     * returns a null coordinate.
     * Otherwise, the shell is not properly contained in a hole, which is an error.
     */
    Coordinate badNestedPt = null;
    for (int i = 0; i < p.getNumInteriorRing(); i++) {
        LinearRing hole = (LinearRing) p.getInteriorRingN(i);
        badNestedPt = checkShellInsideHole(shell, hole, graph);
        if (badNestedPt == null)
            return;
    }
    validErr = new TopologyValidationError(
            TopologyValidationError.NESTED_SHELLS,
            badNestedPt);
}

private void checkConnectedInteriors(GeometryGraph graph) {
    ConnectedInteriorTester cit = new ConnectedInteriorTester(graph);
    if (!cit.isInteriorsConnected())
        validErr = new TopologyValidationError(
                TopologyValidationError.DISCONNECTED_INTERIOR,
                cit.getCoordinate());
}

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

public GeometryGraphOperation(Geometry g0, Geometry g1, BoundaryNodeRule boundaryNodeRule) {
    // use the most precise model for the result
    if (g0.getPrecisionModel().compareTo(g1.getPrecisionModel()) >= 0)
        setComputationPrecision(g0.getPrecisionModel());
    else
        setComputationPrecision(g1.getPrecisionModel());

    arg = new GeometryGraph[2];
    arg[0] = new GeometryGraph(0, g0, boundaryNodeRule);
    arg[1] = new GeometryGraph(1, g1, boundaryNodeRule);
}

public GeometryGraphOperation(Geometry g0) {
    setComputationPrecision(g0.getPrecisionModel());

    arg = new GeometryGraph[1];
    arg[0] = new GeometryGraph(0, g0);
    ;
}

public Expression<K, C, Boolean> isInteriorDisconnected() {
    return new AbstractUnaryTestExpression<K, C, T>(this, "IsInteriorDisconnected") {
        @Override
        public boolean test(T value, C context) {
            if (!(value instanceof Surface)) {
                return false;
            }

            try {
                final GeometryValidator validator = context.validateGeometry(value).validator;
                final Surface polygon = (Surface) value;
                final Ring exterior = new DefaultLinearRing("exterior", null, null, polygon
                        .getExteriorRingCoordinates());

                final GeometryFactory geometryFactory = new GeometryFactory();

                final LinearRing exteriorRing = getJTSRing(exterior, validator);
                final ArrayList<LinearRing> interiorRings = new ArrayList<>();
                for (final Points points : polygon.getInteriorRingsCoordinates()) {
                    final Ring ring = new DefaultLinearRing("interior", null, null, points);
                    interiorRings.add(getJTSRing(ring, validator));
                }

                com.vividsolutions.jts.geom.Polygon jtsPolygon = geometryFactory.createPolygon(exteriorRing,
                        interiorRings.toArray(new LinearRing[interiorRings.size()]));

                final GeometryGraph geometryGraph = new GeometryGraph(0, jtsPolygon);
                geometryGraph.computeSelfNodes(new RobustLineIntersector(), true);

                ConnectedInteriorTester connectedInteriorTester = new ConnectedInteriorTester(geometryGraph);

                return !connectedInteriorTester.isInteriorsConnected();
            } catch (InvocationTargetException | IllegalArgumentException | IllegalAccessException e) {
                throw new ExpressionEvaluationException(e);
            }
        }
    };
}

public GeometryGraphOperation(Geometry g0, Geometry g1, BoundaryNodeRule boundaryNodeRule)
{
  // use the most precise model for the result
  if (g0.getPrecisionModel().compareTo(g1.getPrecisionModel()) >= 0)
    setComputationPrecision(g0.getPrecisionModel());
  else
    setComputationPrecision(g1.getPrecisionModel());

  arg = new GeometryGraph[2];
  arg[0] = new GeometryGraph(0, g0, boundaryNodeRule);
  arg[1] = new GeometryGraph(1, g1, boundaryNodeRule);
}

public GeometryGraphOperation(Geometry g0, Geometry g1, BoundaryNodeRule boundaryNodeRule)
{
  // use the most precise model for the result
  if (g0.getPrecisionModel().compareTo(g1.getPrecisionModel()) >= 0)
    setComputationPrecision(g0.getPrecisionModel());
  else
    setComputationPrecision(g1.getPrecisionModel());

  arg = new GeometryGraph[2];
  arg[0] = new GeometryGraph(0, g0, boundaryNodeRule);
  arg[1] = new GeometryGraph(1, g1, boundaryNodeRule);
}