如何基于至少两个坐标点在栅格上生成形状并判断点是否在范围内

核心功能说明 #

• 支持点选≥2个地图坐标点，仅选2个点时默认生成轴对齐矩形
• 基于选中点自动生成闭合多边形
• 可快速判断任意给定点是否落在形状内部/边界上

核心数据结构定义 #

// 坐标点结构体
Struct Point:
    Float x  // 经度/横轴坐标
    Float y  // 纬度/纵轴坐标

// 闭合形状结构体
Struct ClosedShape:
    Enum type: RECTANGLE, POLYGON  // 形状类型
    List<Point> vertices  // 按顺序存储的形状顶点
    BoundingBox bound  // 外接矩形，用于快速过滤判断

步骤1：闭合形状生成算法 #

Function generateClosedShape(selectedPoints: List<Point>) -> ClosedShape:
    // 输入校验
    If length(selectedPoints) < 2:
        Throw Error("至少需要选择2个坐标点")
    
    // 2个点默认生成矩形
    If length(selectedPoints) == 2:
        p1 = selectedPoints[0]
        p2 = selectedPoints[1]
        // 计算矩形四个顶点：左上、右上、右下、左下
        minX = min(p1.x, p2.x)
        maxX = max(p1.x, p2.x)
        minY = min(p1.y, p2.y)
        maxY = max(p1.y, p2.y)
        rectVertices = [
            Point(minX, maxY),
            Point(maxX, maxY),
            Point(maxX, minY),
            Point(minX, minY)
        ]
        // 生成形状对象
        shape = ClosedShape(
            type = RECTANGLE,
            vertices = rectVertices,
            bound = BoundingBox(minX, maxX, minY, maxY)
        )
        Return shape
    
    // 大于2个点生成多边形，可选择凸包排序/保留用户点选顺序
    Else:
        // 若要生成凸多边形则调用凸包排序，若支持凹多边形直接保留用户点选顺序即可
        sortedVertices = convexHullSort(selectedPoints)
        // 补全闭合规则：最后一个顶点连回第一个顶点
        sortedVertices.append(sortedVertices[0])
        // 计算外接矩形
        minX = min(p.x for p in sortedVertices)
        maxX = max(p.x for p in sortedVertices)
        minY = min(p.y for p in sortedVertices)
        maxY = max(p.y for p in sortedVertices)
        shape = ClosedShape(
            type = POLYGON,
            vertices = sortedVertices,
            bound = BoundingBox(minX, maxX, minY, maxY)
        )
        Return shape

步骤2：点包含判断算法（射线法） #

Function isPointInShape(point: Point, shape: ClosedShape) -> Bool:
    // 外接矩形快速过滤：不在外接矩形内的点直接返回false
    If point.x < shape.bound.minX OR point.x > shape.bound.maxX OR point.y < shape.bound.minY OR point.y > shape.bound.maxY:
        Return False
    
    // 矩形形状直接返回结果
    If shape.type == RECTANGLE:
        Return True
    
    // 多边形用射线法判断
    vertices = shape.vertices
    n = length(vertices)
    inside = False
    For i from 0 to n-1:
        j = (i + 1) % n
        // 判断点是否在当前边的Y轴范围内
        intersect = ((vertices[i].y > point.y) != (vertices[j].y > point.y))
        If intersect:
            // 计算水平射线和边的交点X坐标
            xIntersect = ( (point.y - vertices[i].y) * (vertices[j].x - vertices[i].x) ) / (vertices[j].y - vertices[i].y) + vertices[i].x
            If point.x < xIntersect:
                inside = !inside
    Return inside

补充说明 #

• 批量标记地图内部区域时，遍历地图网格的每个点调用isPointInShape接口，符合条件的做标记即可
• 边界点判断可额外增加逻辑：先判断点是否落在任意一条边的距离阈值范围内，是则直接判定为在边界内
• 若要支持带洞的多边形，可在射线法判断时增加洞内点的二次校验逻辑

内容的提问来源于stack exchange，提问作者H B