基于扫描线的多边形填充算法

Scan-Line Polygon Fill

扫描线填充算法是计算机图形学中一种高效的填充多边形内部区域的算法。与逐个像素检测的泛洪填充(Flood Fill)或边界填充(Boundary Fill)算法不同，它利用了图形的连贯性，一次处理一条水平线上的所有像素，效率很高。

关键步骤与数据结构

为了高效地实现这一过程，算法通常使用两个关键的数据结构：

  1. 边表 (Edge Table, ET)：一个数组或链表列表，用于存放多边形的所有边的信息。整个表按边的最小 y 坐标进行索引。每条边信息通常包括：
    • ymax: 该边的最大 y 坐标。
    • x_at_ymin: 该边在最小 y 坐标处的 x 值。
    • 1/m: 斜率的倒数 (dx/dy)，用于在扫描线每向上移动一行时，快速更新边与扫描线的 x 交点。
  2. 活性边表 (Active Edge Table, AET)：一个链表，用于存放当前扫描线正在相交的边。AET 中的边始终按其与当前扫描线交点的 x 坐标从小到大排序。

算法流程如下：

  1. 初始化：遍历多边形的所有顶点，建立边表(ET)。水平的边通常被忽略。
  2. 开始扫描：设置一个 y 值，从多边形的最低扫描线开始。
  3. 处理循环：只要活性边表(AET)不为空，或者边表(ET)中还有未处理的边，就重复以下步骤：
    1. 更新AET：检查边表(ET)，将所有 ymin == y 的边移入活性边表(AET)中。
    2. 排序AET：将 AET 中的所有边按当前的 x 交点坐标进行排序。
    3. 填充像素：将 AET 中的边两两配对（第1条和第2条，第3条和第4条，以此类推），然后填充每对边之间在当前扫描线上的所有像素。
    4. 进入下一行：将 y 值加 1 (y = y + 1)。
    5. 更新AET：
      • 移除 AET 中满足 ymax == y 的边（因为扫描线已经越过了这些边）。
      • 对于 AET 中剩余的每一条边，根据其斜率倒数更新 x 交点的值 (x = x + 1/m)，为下一行做准备。
  4. 结束：循环直到处理完所有扫描线。

实现

OpenCV中的fillPoly实现了扫描线填充算法，基本思想是：用一条水平的扫描线从多边形的底部移动到顶部（或反之），在每一行，计算出扫描线与多边形所有边的交点。然后将这些交点按 x 坐标排序，将成对的交点之间的像素区间进行填充。主要用到两个函数：CollectPolyEdges和FillEdgeCollection，第一个是收集多边形边缘，第二个是填充多边形。值得注意的是fillPoly内部使用专门的整数算法(类似于Bresenham直线算法)来计算边与扫描线的交点，以及在扫描线递增时更新交点x坐标，这比直接使用x=x+dx/dy的浮点运算快得多。

示例图片

halcon实现

gen_region_polygon_filled 是 HALCON 中一个基础但非常重要的区域生成算子。它的核心功能是根据一组给定的顶点坐标，创建一个被完全填充的多边形区域（Region）。算子会自动将最后一个顶点与第一个顶点相连，形成一个闭合的多边形，顶点坐标值可以是整数（integer）也可以是浮点数（float）。如果你提供的顶点顺序导致多边形的边相互交叉（即“自相交”），算子依然能够正确处理。它会使用一种称为“奇偶规则”的算法来确定哪些部分属于多边形内部。根据网上的信息，该算子也是基于扫描线填充算法实现。

示例图片

关于多边形边缘点的确定

不难看出扫描线与边的交点通常为浮点坐标，而区域是基于行程编码(整数坐标)表示的，这就涉及一个问题，如何确定多边形的边缘点坐标？也就是一个行程(1 个Run)的起点和终点该如何确定？向上取整、向下取整、四舍五入还是其它？对此，我将OpenCV的填充结果与HALCON进行对比，如下图所示：

示例图片

示例图片

示例图片

OpenCV的fillPoly函数针对一个Run的起点和终点采取了向上取整和向下取整的策略，这里我修改为了四舍五入，图片中矩形表示run的起点，圆形表示run的终点，洋红色对应HALCON，绿色对应OpenCV，可见两种算法的结果并不完全一致，第一个图中，从顶点开始第三行run的起点，HALCON选取了边缘左边的点，OpenCV选取了边缘右边的点，很显然OpenCV选取的点离边缘更近，第二个图中，run的终点选取也出现了类似的情况，第三个图则是完全吻合的情况， 所以我对HALCON的选取策略充满了疑惑，请知道原因的小伙伴不吝赐教。