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

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)]

这两种方法在测试数据和小的凸多边形上都能完美工作，但在大多数真实数据的多边形上却返回错误的结果。

我用模拟数据对这两个函数进行了相当广泛的测试（我测试了所有这些类型的多边形），但是当我把它们应用到大多数真实数据时，这些函数就不再有效了。

有没有什么因素会影响这些函数导致它们出现错误，比如多边形的大小、坐标的小数位数，或者其他类似的小问题？

Answer 1

你也可以使用QHull。Python的实现可以通过Scipy来使用，具体信息可以查看这个链接：http://docs.scipy.org/doc/scipy-0.13.0/reference/generated/scipy.spatial.ConvexHull.html#scipy.spatial.ConvexHull

你只需要把多边形的坐标和你关注的点一起提供给ConvexHull，它就会返回一个包含所有点外边界的vertices集合。如果你的点是这些顶点之一，那就说明这个点在外面。否则，它就在里面。不过，scipy.spatial还有很多其他功能，适合你正在做的事情，你可以去看看。

Answer 2

判断一个点是否在多边形内部，最常用的方法之一就是从这个点出发，向任意方向画一条线，然后看看这条线穿过多边形边界的次数。如果这条线穿过边界的次数是奇数，那么这个点就在多边形内部；如果是偶数，那它就在外面。想了解更多具体的例子，可以看看这个StackOverflow的问题。

顺便提一下，Shapely是一个经过充分测试的库。我觉得它应该不会出错，可能是你的多边形有问题，或者是你使用的方式不对。

Answer 3

这里有一个我成功使用过的算法。

首先，找一个在你多边形外面的点——可以随便选一个x或y，只要它比你多边形的最大值大就行。

然后，想象一下从这个点画一条线，延伸到多边形外面的某个点。

接着，数一下这条线和你多边形边界上的线段交叉的次数。如果交叉的次数是奇数，说明这个点在多边形内部；如果是偶数，那就说明它在外面。

还有一种方法是使用图形中的填充功能，在白色背景上填充一个红色的多边形，然后看看你选的点是什么颜色……