1

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?

4

1 回答 1

2

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

你必须：

  1. 查找多边形的任何边是否与轴对齐的矩形（屏幕）相交。在这里尝试金属答案。

  2. 如果不是，检查多边形的一个顶点是否在矩形内（很简单的测试）

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

于 2013-05-24T13:56:55.190 回答