如何基于多边形与横竖线坐标获取其外部的相交矩形网格？

步骤1：生成所有候选网格矩形 #

要从已有的水平线、竖直线交点定义矩形，核心是先对坐标做有序化处理：

• 提取所有水平线的y坐标，去重后按从小到大排序，得到序列 Y = [y₀, y₁, ..., yₙ]
• 提取所有竖直线的x坐标，去重后按从小到大排序，得到序列 X = [x₀, x₁, ..., xₘ]
• 遍历每一组相邻的x值和y值：对于任意 i ∈ [0, m-1] 和 j ∈ [0, n-1]，对应的矩形四个顶点为：
  (Xᵢ, Yⱼ), (Xᵢ₊₁, Yⱼ), (Xᵢ₊₁, Yⱼ₊₁), (Xᵢ, Yⱼ₊₁)
  这样就能生成所有由水平线、竖直线分割出来的网格矩形。

步骤2：筛选出多边形外部的矩形 #

对每个生成的候选矩形，通过点-in-多边形算法判断其是否属于外部网格：

• 取矩形的中心坐标作为参考点：((Xᵢ + Xᵢ₊₁)/2, (Yⱼ + Yⱼ₊₁)/2)
• 使用射线法判断参考点位置：从参考点向右发射一条水平射线，统计射线与多边形边的交点数量：
  • 交点数为奇数：参考点在多边形内部，该矩形属于内部网格，排除
  • 交点数为偶数：参考点在多边形外部，该矩形即为目标网格
• 特殊情况处理：如果矩形边与多边形边重合，可根据需求调整判定规则——比如只要矩形存在部分区域在多边形外部，即可判定为目标网格，此时可检查矩形的四个顶点是否至少有一个在外部，或计算矩形与多边形的交集面积是否小于矩形总面积。

关键注意事项 #

• 坐标排序前必须去重，避免生成零面积的无效矩形
• 实现射线法时，要处理射线恰好经过多边形顶点、与多边形边共线的特殊场景，避免计数错误

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