如何从格点凸多边形提取顶点附近四方向内部点？

嘿，这个问题我之前在处理格点几何项目时碰过，咱们一步步拆解来搞定它～

核心思路纠正：别用斜率，用向量叉乘判断内部方向 #

你的斜率判断思路其实有局限性——比如遇到垂直边（斜率无穷大）或者水平边（斜率为0）时很容易出错，而且凸多边形的内部方向是统一的（所有边的内侧都朝向多边形中心），用向量叉乘能更准确、通用地判断每个顶点附近的内部方向。

具体实现步骤 #

• 第一步：确认顶点顺序
  首先必须保证你的顶点是按顺时针或逆时针严格有序排列的（凸多边形只有有序才能准确判断内部）。如果不确定顺序，可以通过计算多边形面积的正负来验证：逆时针排列的凸多边形面积为正，顺时针为负，调整顺序即可。

• 第二步：计算当前顶点的相邻边向量
  假设当前顶点是 ( V_i = (x_i, y_i) )：

  • 前一个顶点是 ( V_{i-1} )（注意第一个顶点的前一个是最后一个顶点，循环处理）
  • 后一个顶点是 ( V_{i+1} )（最后一个顶点的后一个是第一个顶点，循环处理）
  • 计算入边向量：( \vec{in} = (x_i - x_{i-1}, y_i - y_{i-1}) )
  • 计算出边向量：( \vec{out} = (x_{i+1} - x_i, y_{i+1} - y_i) )

• 第三步：筛选四方向候选点并判断内部
  先列出当前顶点的四个四方向单位点：( (x_i±1,y_i) )、( (x_i,y_i±1) )，然后按两个规则筛选：

  1. 排除边上的点：如果候选点在当前顶点的入边或出边上，直接跳过（因为我们要的是内部点，不是边界点）
  2. 判断是否在多边形内部：对于凸多边形，若顶点是逆时针排列，内部点会在所有边的左侧（用向量叉乘判断，叉乘结果≥0）；若顺时针排列，内部点会在所有边的右侧（叉乘结果≤0）

示例伪代码（Python风格） #

def get_internal_4dir_points(polygon_vertices):
    n = len(polygon_vertices)
    internal_points = []
    
    # 先确认顶点是逆时针顺序（可选，若已知顺序可跳过）
    def is_counter_clockwise(verts):
        area = 0
        for i in range(n):
            x1, y1 = verts[i]
            x2, y2 = verts[(i+1)%n]
            area += (x2 - x1)*(y2 + y1)
        return area > 0
    
    if not is_counter_clockwise(polygon_vertices):
        polygon_vertices = polygon_vertices[::-1]  # 转为逆时针
    
    for i in range(n):
        x_i, y_i = polygon_vertices[i]
        prev_x, prev_y = polygon_vertices[(i-1)%n]
        next_x, next_y = polygon_vertices[(i+1)%n]
        
        # 四方向候选点
        candidates = [
            (x_i + 1, y_i),
            (x_i - 1, y_i),
            (x_i, y_i + 1),
            (x_i, y_i - 1)
        ]
        
        # 辅助函数：判断点是否在线段上
        def is_on_segment(a, b, c):
            # 先判断三点共线
            cross = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
            if cross != 0:
                return False
            # 再判断点在线段的 bounding box 内
            min_x = min(a[0], b[0])
            max_x = max(a[0], b[0])
            min_y = min(a[1], b[1])
            max_y = max(a[1], b[1])
            return (min_x <= c[0] <= max_x) and (min_y <= c[1] <= max_y)
        
        for p in candidates:
            px, py = p
            # 跳过边上的点
            if is_on_segment((prev_x, prev_y), (x_i, y_i), p) or is_on_segment((x_i, y_i), (next_x, next_y), p):
                continue
            
            # 判断是否在凸多边形内部（逆时针顺序下，所有边的叉乘≥0）
            inside = True
            for j in range(n):
                ax, ay = polygon_vertices[j]
                bx, by = polygon_vertices[(j+1)%n]
                cross = (bx - ax)*(py - ay) - (by - ay)*(px - ax)
                if cross < 0:
                    inside = False
                    break
            if inside:
                internal_points.append(p)
    
    return internal_points

额外提示 #

• 向量叉乘是格点几何判断方向的核心工具，比斜率更稳定，完全避开了除法和无穷大的问题
• 如果你的顶点已经是有序的，可以跳过代码里的逆时针校验部分，提升效率

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