多边形扫描线奇偶填充算法中水平边的处理方案咨询

不用放弃奇偶规则，只需要通过顶点相邻边的y坐标判定来调整计数逻辑，就能解决你遇到的五角星填充问题，具体实现步骤如下：

• 先过滤掉多边形中完全水平的边（这类边不参与扫描线交点的计数，避免重复计算）
• 对每条扫描线，收集所有非水平边与扫描线的交点：
  • 若交点是多边形的顶点，同时记录该顶点的两条相邻边的y坐标
• 对每个顶点类型做判定，调整计数：
  • 当顶点的两条相邻边y值都大于或都小于顶点自身y值（即相邻边在顶点同侧）：该顶点按1次计数
  • 当顶点的两条相邻边y值一大于一小于顶点自身y值（即相邻边在顶点异侧）：该顶点按2次计数
• 将所有交点按x坐标排序，然后严格按照奇偶规则，交替填充交点之间的区间

五角星场景的验证 #

你提到的正立五角星顶部扫描线，四个顶点的处理逻辑：

• 两个外部顶点：相邻边分别在顶点的上下两侧（异侧），所以各计数2次
• 两个内部顶点：相邻边都在顶点的下方（同侧），所以各计数1次
  总计数为2+2+1+1=6，排序后按奇偶规则处理，会正确填充整条扫描线的所有区域。

关键实现细节 #

• 相邻边的判定：多边形的顶点是按顺序存储的，所以顶点V[i]的相邻边是V[i-1]-V[i]和V[i]-V[i+1]（注意首尾顶点的循环处理）
• 扫描线交点的计算：对于非水平边，用线性插值计算与扫描线的x坐标，顶点直接取自身x值
• 排序时，若多个交点x坐标相同，按计数次数的逻辑依次排列（比如计数2次的顶点相当于两个相同x的交点）

这种方法完全基于奇偶规则，没有额外的复杂逻辑，实现成本低，能覆盖所有多边形的扫描线填充场景。

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