寻求凸多边形内整数坐标点的高效算法（原方法时间复杂度不达标）

嘿，刚好我之前做过类似的凸多边形整数点求解优化，之前那种逐行扫交点的方法确实在多边形规模大的时候效率拉胯，给你分享几个针对性的优化方案，尤其是利用凸多边形特性的高效解法：

这是最快的方法，完全不用枚举点，直接用数学公式计算内部整数点的总数。Pick定理的公式是：

A = I + B/2 - 1
其中：

• A是多边形的面积（用** shoelace公式 **计算，O(n)时间）
• B是多边形边界上的整数点总数（每条边上的整数点数量是gcd(|x2-x1|, |y2-y1|)，把所有边的这个值加起来，再减去n，因为每个顶点被两条边重复计算了，O(n)时间）
• I就是我们要的内部整数点数量，变形一下得：I = A - B/2 + 1

举个例子：比如一个正方形顶点(0,0),(0,2),(2,2),(2,0)，面积A=4，边界点B=8（每条边有3个点，4*3-4=8），所以I=4 -8/2 +1=4-4+1=1，也就是(1,1)，完全正确。

这个方法适合只需要数量的场景，速度快到离谱，完全碾压扫描线。

如果必须列出所有点，那优化扫描线是最优选择，核心是利用凸多边形的特性减少不必要的计算：

优化点对比（vs 你之前的方法） #

之前的方法可能是对每个y值，遍历所有边找交点，时间复杂度是O(n*H)（H是多边形的高度），优化后：

1. 预处理边并排序：先把所有边按起始y坐标排序，避免重复遍历
2. 维护活跃边列表：只保留当前y值范围内的边，每次更新时只处理新增/移除的边，用排序保证交点顺序
3. 整数运算避免浮点误差：用分数表示交点的x坐标，不用浮点数，避免精度丢失
4. 跳跃式处理y层：不用逐行遍历所有y，直接跳转到有边变化的y层，大幅减少循环次数

具体实现步骤 #

• 预处理边：把凸多边形的每条边转换为(y_start, y_end, x_start, dx, dy)的形式，其中dx=x_end-x_start，dy=y_end-y_start，确保y_start < y_end（水平边单独处理）
• 按y_start排序边：这样我们可以按y从低到高处理，依次把边加入活跃列表
• 处理每个y层：
  • 把所有y_start等于当前y的边加入活跃列表
  • 移除所有y_end等于当前y的边
  • 计算活跃边在当前y的x交点，排序后两两配对（凸多边形的活跃边一定是偶数个，左右交替）
  • 取每对交点之间的整数x，加入结果列表
• 跳转到下一个y层：下一个y要么是下一条待加入边的y_start，要么是活跃边中最小的y_end，跳过无变化的y层

伪代码示例（核心部分） #

import math

def get_convex_integer_points(vertices):
    # 预处理非水平边
    edges = []
    n = len(vertices)
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i+1)%n]
        if y1 == y2:
            continue  # 水平边后续单独处理边界点
        # 确保边是从低y到高y
        if y1 > y2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        edges.append( (y1, y2, x1, x2 - x1, y2 - y1) )
    
    # 按起始y排序边
    edges.sort()
    active_edges = []
    current_y = edges[0][0] if edges else 0
    edge_ptr = 0
    result = []

    while edge_ptr < len(edges) or active_edges:
        # 加入当前y开始的边
        while edge_ptr < len(edges) and edges[edge_ptr][0] == current_y:
            active_edges.append(edges[edge_ptr])
            edge_ptr += 1
        
        # 移除当前y结束的边
        active_edges = [e for e in active_edges if e[1] > current_y]
        
        # 计算每条活跃边在当前y的x值（用分数避免浮点误差）
        x_intersections = []
        for (y1, y2, x1, dx, dy) in active_edges:
            delta_y = current_y - y1
            # x = x1 + dx * delta_y / dy → 用分子分母计算避免浮点
            x_num = x1 * dy + dx * delta_y
            x_val = x_num / dy
            x_intersections.append(x_val)
        
        # 排序交点，凸多边形保证是左右交替的，两两配对
        x_intersections.sort()
        for i in range(0, len(x_intersections), 2):
            left = x_intersections[i]
            right = x_intersections[i+1]
            # 取中间的整数x
            start_x = math.ceil(left)
            end_x = math.floor(right)
            if start_x > end_x:
                continue
            for x in range(start_x, end_x + 1):
                result.append( (x, current_y) )
        
        # 找下一个要处理的y，跳过无变化的y层
        next_y = float('inf')
        if edge_ptr < len(edges):
            next_y = min(next_y, edges[edge_ptr][0])
        for e in active_edges:
            next_y = min(next_y, e[1])
        current_y = next_y if next_y != float('inf') else current_y + 1
    
    # 如果需要包含边界点，这里可以加上水平边的点和其他边界点的计算（用GCD）
    return result

• 浮点误差是大忌：一定要用整数运算或者分数来计算交点，不然会出现比如交点算成2.0000000001或者1.9999999999，导致整数点漏算或多算
• 凸多边形的特性要抓牢：凸多边形的活跃边列表始终是偶数个，排序后直接两两配对，不用处理凹多边形那种复杂的交点嵌套情况，这能省很多代码和时间
• 按需选择方案：如果只需要计数，Pick定理是最优解；如果要枚举点，优化扫描线是首选

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