python判断平面内一个点是否在多边形内

采用射线法就可以判断一个点是否在多边形内， 只需从点出发向右侧水平做出一条射线，如果跟多边形交点个数为奇数，则点在多边形内，否则在多边形外。看一张图就可以看懂啦

图片来自：https://www.jianshu.com/p/ba03c600a557

输入：P点坐标[px, py]

多边形poly顶点坐标[[x1, y1], [x2, y2], ..., [xn, yn]]

返回：True or False

首先，利用循环对多边形每条边做同样对待。然后，判断是否有跟点P水平右向的射线是否有交点，若有交点，flag就翻转一次。

看程序：

def is_in_poly(p, poly):
    """

    :param p: [x, y]
    :param poly: [[], [], [], [], ...]
    :return:
    """
    px, py = p
    flag = False
    i = 0
    length = len(poly)
    j = length - 1
    while i < length:
        x1, y1 = poly[i]
        x2, y2 = poly[j]
        if (x1 == px and y1 == py) or (x2 == px and y2 == py):
            flag = True
            break
        if y1 < py <= y2 or y2 < py <= y1:
            x = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
            if x == px:
                flag = True
                break
            elif x > px:
                # convert the flag
                flag = not flag
        j = i
        i += 1

    return flag

if __name__ == '__main__':
    point = [3, 3]
    poly = [[0, 0], [7, 3], [8, 8], [5, 5]]
    print(is_in_poly(point, poly))