欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python 判断一个点(坐标)是否在一个多边形内利用射线法

程序员文章站 2022-04-02 21:24:38
...

看了一篇博客写的用射线法判断一个经纬度点是否在一个多边形的内部的方法 经验证可行所以拿来用作备份:

class Point:

    lng = ''

    lat = ''

    def __init__(self, lng, lat):

        self.lng = lng

        self.lat = lat

求外包矩形

def get_polygon_bounds(points):

    length = len(points)

    top = down = left = right = points[0]

    for i in range(1, length):

        if points[i].lng > top.lng:

            top = points[i]

        elif points[i].lng < down.lng:

            down = points[i]

        else:

            pass

        if points[i].lat > right.lat:

            right = points[i]

        elif points[i].lat < left.lat:

            left = points[i]

        else:

            pass

    top_left = Point(top.lng, left.lat)

    top_right = Point(top.lng, right.lat)

    down_right = Point(down.lng, right.lat)

    down_left = Point(down.lng, left.lat)

    return [top_left, top_right, down_right, down_left]

判断点是否在外包矩形外 如果不在外包矩形内部那肯定不在多边形内部

def is_point_in_rect(point, polygon_bounds):

    top_left = polygon_bounds[0]

    top_right = polygon_bounds[1]

    down_right = polygon_bounds[2]

    down_left = polygon_bounds[3]

    return (down_left.lng <= point.lng <= top_right.lng

            and top_left.lat <= point.lat <= down_right.lat)

def is_point_in_polygon(point, points):

    polygon_bounds = get_polygon_bounds(points)

    if not is_point_in_rect(point, polygon_bounds):

        return False

    length = len(points)

    point_start = points[0]

    flag = False

    for i in range(1, length):

        point_end = points[i]

        # 点与多边形顶点重合

        if (point.lng == point_start.lng and point.lat == point_start.lat) or (

                point.lng == point_end.lng and point.lat == point_end.lat):

            return True

        # 判断线段两端点是否在射线两侧

        if (point_end.lat < point.lat <= point_start.lat) or (

                point_end.lat >= point.lat > point_start.lat):

            # 线段上与射线 Y 坐标相同的点的 X 坐标

            if point_end.lat == point_start.lat:

                x = (point_start.lng + point_end.lng) / 2

            else:

                x = point_end.lng - (point_end.lat - point.lat) * (

                        point_end.lng - point_start.lng) / (

                        point_end.lat - point_start.lat)

            # 点在多边形的边上

            if x == point.lng:

                return True

            # 射线穿过多边形的边界

            if x > point.lng:

                flag = not flag

            else:

                pass

        else:

            pass

        point_start = point_end

    return flag

def test(input_lng=116.732617, input_lat=39.722676):

    # polyline 是多个坐标点,形如

    # ['116.732617,39.722676', '116.732617,39.722676', '116.732617,39.722676',

    # '116.732617,39.722676', '116.732617,39.722676']

    polyline = []

    points = []

    for line in polyline:

        if line:

            try:

                lng, lat = line.split(',')

                points.append(Point(float(lng), float(lat)))

            except ValueError:

                pass

    if points:

        return is_point_in_polygon(Point(float(input_lng), float(input_lat)), points)

判断一个点是否在多边形内部有多种写法,比如利用面积计算但是利用面积计算有一个缺点就是计算结果不是很准确,因为利用经纬度计算出来的距离本身就有偏差,所以将多边形分成多个小三角形相加后就会有误差导致最后不能作为判断的依据,我看大多数都是用的射线方法计算.