确定一个点是否在多边形内部

Question

根据我的需求，我正在谷歌地图上绘制多边形，如下所示的图片。(使用maps v2)

现在我需要在用户进入该特定多边形时显示一个警报。

如何确定我的当前位置是否在多边形内。 (需要优化方式，不会消耗电池)

提前感谢。

- Supriya

---

你在这里使用了地理围栏吗？ - Ranjit

不是的。我只是使用PolygonOptions绘制了那个多边形。正在寻找最佳方法来确定当前位置是否在该多边形内。 - Supriya

你可以使用地理围栏来实现这个功能。http://developer.android.com/training/location/geofencing.html - Ranjit

我认为Geofence是指如果我们可以有一个位置并给定一个特定的半径，当用户进入该位置时它会发出警报。在我的情况下，我正在使用多个位置绘制一个多边形。 - Supriya

当您为位置提供半径时，地理围栏会将被半径所包围的区域内的每个点存储下来。您的问题与此有关，您可以在地理围栏中绘制多边形而不是圆形。 - Ranjit

尝试使用此链接 https://github.com/sromku/polygon-contains-point - M.Hefny

Answer 1

我刚试过射线投射算法，这个算法可以准确地识别多边形中的点。

详细内容请参考http://en.wikipedia.org/wiki/Point_in_polygon上关于射线投射算法的论文。

private boolean isPointInPolygon(LatLng tap, 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); // odd = inside, even = outside;
    }

    private boolean rayCastIntersect(LatLng tap, LatLng vertA, LatLng vertB) {

        double aY = vertA.latitude;
        double bY = vertB.latitude;
        double aX = vertA.longitude;
        double bX = vertB.longitude;
        double pY = tap.latitude;
        double pX = tap.longitude;

        if ((aY > pY && bY > pY) || (aY < pY && bY < pY)
                || (aX < pX && bX < pX)) {
            return false; // a and b can't both be above or below pt.y, and a or
                            // b must be east of pt.x
        }

        double m = (aY - bY) / (aX - bX); // Rise over run
        double bee = (-aX) * m + aY; // y = mx + b
        double x = (pY - bee) / m; // algebra is neat!

        return x > pX;
    }

- Supriya

---

你的算法为什么总是返回 false？ - ofskyMohsen

@Supriya，工作得很好。谢谢你。如果可能的话，我请求您解释一下交集是如何工作的。 - Arnold Brown

如果 m = (aX - bX) / (aY - bY) = 0，则此实现将无法工作。 - user1581432

亲爱的Supriya，这只有在用户当前位置坐标与多边形坐标之一完全匹配时才能正常工作。如果稍有不同，它将无法正常工作。如果我错了，请告诉我。 - Jaimin Modi

Answer 2

我发现射线投射方法不可靠，但最终我使用了来自谷歌地图的PolyUtil。

你需要依赖compile 'com.google.maps.android:android-maps-utils:0.5'

然后这个方法看起来像这样

PolyUtil.containsLocation(userLocation, polyPointsList, false);

编辑

这是在源代码中找到的该方法的描述。

计算给定点是否位于指定多边形内部。无论最后一个点是否等于第一个点，该多边形始终被视为闭合。内部定义为不包含南极 -- 南极始终在外部。如果geodesic为true，则多边形由大圆段组成，否则由rhumb（loxodromic）段组成。

- DoruChidean

---

为什么最后一个参数是false？那个参数是什么？ - Virat18

我已经添加了该方法的描述，因为我在他们的源代码中找到了它。 - DoruChidean

谢谢！非常棒的答案！ - Virat18

这两个都一直有效。我把它们都加上了，并将地图触摸监听器作为调用。没有问题。但这显然是更干净的实现方式。 - StarWind0

Answer 3

请查看以下链接：

Polygon Touch detection Google Map API V2

这是RayCasting算法，它可能对你有帮助 :)

该算法的简要描述如下:

从你的点向右绘制一条水平线，如果它与多边形的边相交的次数是奇数，则该点在多边形内部，否则在外部 :)

这些维基链接将为您提供完整的想法:

http://en.wikipedia.org/wiki/Point_in_polygon

http://rosettacode.org/wiki/Ray-casting_algorithm

- Revathi

---

尝试一下这个。谢谢 :) - Supriya

在我的几个测试中工作正常。正在检查它的论文。 :) 谢谢 - Supriya

Answer 4

以下是使用Dart编写的代码，取自于： https://github.com/KohlsAdrian/google_maps_utils/blob/master/lib/poly_utils.dart

  /// Checks if [point] is inside [polygon]
  static bool containsLocationPoly(Point point, List<Point> polygon) {
    num ax = 0;
    num ay = 0;
    num bx = polygon[polygon.length - 1].x - point.x;
    num by = polygon[polygon.length - 1].y - point.y;
    int depth = 0;

    for (int i = 0; i < polygon.length; i++) {
      ax = bx;
      ay = by;
      bx = polygon[i].x - point.x;
      by = polygon[i].y - point.y;

      if (ay < 0 && by < 0) continue; // both "up" or both "down"
      if (ay > 0 && by > 0) continue; // both "up" or both "down"
      if (ax < 0 && bx < 0) continue; // both points on left

      num lx = ax - ay * (bx - ax) / (by - ay);

      if (lx == 0) return true; // point on edge
      if (lx > 0) depth++;
    }

    return (depth & 1) == 1;
  }

- Hashem Aboonajmi