Detecting multiple polygon intersections (java)

Question

Background: This project involves mapping regions in GIS environment. I need to find then the intersection of one set of polygons with another set of polygons. I achieved this by casting my map-compatible polygons as Polygon2d (http://geom-java.sourceforge.net/api/math/geom2d/polygon/package-summary.html) and used the intersection method to find the list of vertices for the intersection polygons.

The problem: This works except when there are multiple over lapping regions between the same two polygons. The list of vertices is correct, but I need to seperate the list into each individual polygon.

The first image is what it should look like, the second is what is actually generated:

(ignore the area at the top. Thats a result of a different bug)

How do I detect and correct this situation?

Answer 1

You can use JTS.

1. Create your Polygons using LinearRing
2. Use the intersection method

Simple code example:

// build polygon p1
LinearRing p1 = new GeometryFactory().createLinearRing(new Coordinate[]{new Coordinate(0,0), new Coordinate(0,10), new Coordinate(10,10), new Coordinate(10,0), new Coordinate(0,0)});
// build polygon p2
LinearRing p2 = new GeometryFactory().createLinearRing(new Coordinate[]{new Coordinate(5,5), new Coordinate(15,5), new Coordinate(15,15), new Coordinate(5,15), new Coordinate(5,5)});
// calculate intersecting points
Geometry intersectingPoints = p1.intersection(p2);
// print result
for(Coordinate c : intersectingPoints.getCoordinates()){
    System.out.println(c.toString());
}

Output is (like expected):

(5.0, 10.0, NaN)
(10.0, 5.0, NaN)

Answer 2

Well I figured it out. I took the vertex list for the intersection polygon (blue), iterated through each pair of point, cast each line segment in the two original polygons as LineSegment2D objects and used the .contains method to check if each pair of points was in one of the line segments. If each pair of points wasn't contained within 1 line, then there is an error.

Heres the method, but keep in mind there are several proprietary classes involved.

public static boolean noErrors(SurfacePolygonX p1, SurfacePolygonX p2, List<LatLon> list) {
    boolean allPointsInSamePolygon = true;

    //for each latlon jl in locations, cast jl and jl2 as points    
    for (int j = 0; j < list.size(); j++) {
        LatLon jl = list.get(j);
        LatLon jl2 = list.get((j == list.size() - 1) ? 0 : j + 1);
        Point2D pt = new Point2D(jl.longitude.degrees, jl.latitude.degrees);
        Point2D pt2 = new Point2D(jl2.longitude.degrees, jl2.latitude.degrees);

        List<LatLon> corners = p1.getCorners();

        boolean bothPointsInSameSegment = false;

        //for each latlon k selectedShape cast k and k+1 as 2lineseg
        for (int k = 0; k < corners.size(); k++) {
            LatLon kl = corners.get(k);
            LatLon kl2 = corners.get((k == corners.size() - 1) ? 0 : k + 1);

            LineSegment2D segment = new LineSegment2D(kl.longitude.degrees, kl.latitude.degrees, kl2.longitude.degrees, kl2.latitude.degrees);

            boolean segContainsP1 = segment.contains(pt);
            boolean segContainsP2 = segment.contains(pt2);

            System.out.println("selectedShape: segment "+k+" contains p"+j+":("+segContainsP1+") and p"+(j+1)+":("+segContainsP2+")");

            //check if each line contains the points.
            if (segContainsP1 && segContainsP2)
            {
                bothPointsInSameSegment = true;
            }

        }

        corners = p2.getCorners();
        //for each latlon k tempShape cast k and k+1 as 2lineseg
        for (int k = 0; k < corners.size(); k++) {
            LatLon kl = corners.get(k);
            LatLon kl2 = corners.get((k == corners.size() - 1) ? 0 : k + 1);

            LineSegment2D segment = new LineSegment2D(kl.longitude.degrees, kl.latitude.degrees, kl2.longitude.degrees, kl2.latitude.degrees);


            boolean segContainsP1 = segment.contains(pt);
            boolean segContainsP2 = segment.contains(pt2);

            System.out.println("intersectingShape: segment "+k+" contains p"+j+":("+segContainsP1+") and p"+(j+1)+":("+segContainsP2+")");

            //check if each line contains the points.
            if (segContainsP1 && segContainsP2)
            {
                bothPointsInSameSegment = true;
            }

        }

        if (!bothPointsInSameSegment) allPointsInSamePolygon = false;

    }

    //if both points are not in the same line, then theres a conflict
    return allPointsInSamePolygon;
}