如何找到不规则多边形内的一个点

Question

我有一个函数，它接受纬度和经度坐标，并返回与包含这些坐标的多边形相关的信息。换句话说：

def coords_to_info(lat, lng):
    #check in which polygon the point lies
    return polyName

为了检查点是否在多边形内部，我尝试了两个不同的函数：

def point_in_poly(x,y,poly):
    """
    function to check if a point is in a 2D polygon
    """
    n = len(poly)
    inside = False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xints:
                        inside = not inside
        p1x,p1y = p2x,p2y

    return inside

print point_in_poly(lat, lng, lBoundary)

和

from shapely.geometry import Point
from shapely.geometry.polygon import Polygon

coordPoint = Point(lat, lng)
coordPolygon = Polygon(lBoundary)

print coordPolygon.contains(coordPoint)

lBoundary是一个由元组组成的列表，它是封闭的（第一个和最后一个点相等）：[(a,b), (c,d), (e,f), (a,b)]

这两种方法在测试数据和小凸多边形上都能完美运行，但对大多数真实数据多边形返回错误。

我已经使用模拟数据广泛测试了这两个函数（我测试了所有这些类型的多边形），但当我将其应用于我的大多数真实数据时，这些函数就停止工作了。

是否有任何因素会影响这些函数产生假阴性，例如多边形大小、坐标的小数位数或其他类似的琐事？

- Roman

---

你的真正多边形是谁？是否存在零长度线段、重复点、交叉线等问题？ - Daniel

在我看来，最简单的方法是手动将多边形分成三角形 - 你可以编写一个算法来完成这个任务：然后你可以检测你定义的三角形中哪个包含了你的经纬度 - 我认为这相当容易。 - Tony Suffolk 66

我只想说问题已经解决了。数据中有一个我忽略的小问题。我还是保留这个问题，因为我很喜欢那两个函数。 - Roman

Answer 1

判断一个点是否在多边形内的最常见方法之一是测试从该点开始并沿任意方向前进的线穿过多边形边界的次数。请查看stackoverflow上的这个问题以获取更多信息和具体示例。

顺便说一下，Shapely是一个经过充分测试的库。我认为它不会出现错误，可能存在您的多边形或使用方式的问题。

- Francisco Puga

Answer 2

这里是我成功使用过的算法。

找到一个在多边形外的点 - 只需选择一个比您的最大值更大的 x 或 y。

在您的头脑中，从您的点到多边形外部的点画一条线。

计算此线与组成多边形周长的线段的交点数。如果是奇数，则该点在内部。如果是偶数，则在外部。

另一种方法是使用图形多边形填充函数，在白色背景上填充红色多边形，然后查看您的点的颜色...

- Mark Setchell

Answer 3

你也可以使用QHull。Python实现与Scipy一起提供（http://docs.scipy.org/doc/scipy-0.13.0/reference/generated/scipy.spatial.ConvexHull.html#scipy.spatial.ConvexHull）

你只需提供多边形的坐标和你所查找的点给ConvexHull，它将返回形成所有点外部边界的顶点集合。如果你的点是这些顶点之一，那么你就知道你的点在外面。否则，它在里面。尽管如此，scipy.spatial有很多适用于你正在做的事情的函数，你可能想看看它们。

- ssm