Detect if two polygons have an area in common

Question

I need to know if some part of a Polygon is being shown on screen. I have two ArrayLists of LatLng, one containing the list of points forming the Polygon, and the second one containing the four corners of the screen.

This is my code:

protected boolean doPolygonsHaveAnyCoincidingArea(ArrayList<LatLng> polygon1, final ArrayList<LatLng> polygon2) {
    for (LatLng point : polygon1) {
        if (isPointInsidePolygon(point, polygon2)) {
            return true;
        }
    }
    for (LatLng point : polygon2) {
        if (isPointInsidePolygon(point, polygon1)) {
            return true;
        }
    }
    return false;
}

private boolean isPointInsidePolygon(final LatLng tap, final ArrayList<LatLng> vertices) {      
    int intersectCount = 0;
    for (int j = 0; j < vertices.size() - 1; j++) {
        if (rayCastIntersect(tap, vertices.get(j), vertices.get(j + 1))) {
            intersectCount++;
        }
    }
    return (intersectCount % 2) == 1;
}

private boolean rayCastIntersect(final LatLng tap, final LatLng vertA, final LatLng vertB) {
    final double aY = vertA.latitude;
    final double bY = vertB.latitude;
    final double aX = vertA.longitude;
    final double bX = vertB.longitude;
    final double pY = tap.latitude;
    final double pX = tap.longitude;
    if ((aY > pY && bY > pY) || (aY < pY && bY < pY) || (aX < pX && bX < pX)) {
        return false;
    }
    final double m = (aY - bY) / (aX - bX);
    final double bee = (-aX) * m + aY;
    final double x = (pY - bee) / m;
    return x > pX;
} 

However, I think doPolygonsHaveAnyCoincidingArea is slower than it could, as sometimes the common area is just a little triangle, so only one of those isPointInsidePolygon will return true.

Is there any faster way to determine if two polygons collide or one contains the other?

Answer 1

It is not enough to check that any vertice of one polygon is inside the second (imagine two equal squares, one rotated 45 degrees).

You have to:

1. Find whether any side of polygon intersects axis-aligned rectangle (screen). Try metamal answer here.

2. If not, check whether one vertice of polygon is inside the rectangle (very simple test)

3. If not, check whether one vertice of rectange is inside the polygon (use your function)