android - 检测两个多边形是否有共同区域

Question

我需要知道屏幕上是否显示了 Polygon 的某些部分。我有两个 LatLng 的 ArrayList，一个包含构成 Polygon 的点列表，第二个包含屏幕的四个角.

这是我的代码:

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

但是，我认为 doPolygonsHaveAnyCoincidingArea 比它本来的要慢，因为有时公共(public)区域只是一个小三角形，所以只有其中一个 isPointInsidePolygon 会返回 true。

有没有更快的方法来确定两个多边形是否碰撞或一个包含另一个？

Answer 1

检查一个多边形的任何顶点是否在第二个内部是不够的(想象两个相等的正方形，一个旋转 45 度)。

你必须:

1. 查找多边形的任一侧是否与轴对齐的矩形(屏幕)相交。尝试 metamal answer here .

2. 如果不是，检查多边形的一个顶点是否在矩形内部(非常简单的测试)

3. 如果不是，检查矩形的一个顶点是否在多边形内部(使用您的函数)