扫描线填充算法粗略剖析

文章目录
  1. 1. 介绍
  2. 2. 效果演示
  3. 3. 分析算法
    1. 3.1. 大致算法
  4. 4. 填充方式
  5. 5. PainterPath 与 个人扫描线填充算法

扫描线算法在公司作为图像无效区域的选取工作,是图像处理中的一种。

介绍

扫描线算法把几何图形在计算机中的顶点表示法转换成点阵表示法。需要注意的是转换成点阵表示法后其实是对多边形进行了填充,而不是只有轮廓。

效果演示

分析算法

所有的边界都可以看成点组成。
下图为一个简单的轮廓模型,用于演示。

蓝色的为顶点,红色的为边界

在上图中,存在着四种模型。

  • 上拱
  • 左凹
  • 右凹
  • 平行线

放大上图
观察看可以得到

大致算法

  1. 计算每一个顶点被计算的次数
  2. 计算水平线中交点个数
  3. 计算普通交点的个数
  4. 同一高度的交点奇偶连线

1. 顶点计算方法

  • ① 点的下一个点是② ,上一个点是 -1号点为⑨号点。①.y > ②.y && ①.y > ⑨.y。此处为最高点,在此水平线上,不会有常规交点构成奇数点。而一旦①号点被认定为只有1个点,将会导致在填充时有一个结束点不存在,就会形成该Y值内,X最大的交点与x的一个负值相连,造成填充错误。所以此点需要判定为2次。
  • ②点的下一个点是③,上一个点是①。①.y > ②.y && ②.y > ③.y。②点处于中间位置(同规律可用于③、④、⑧、⑨),同一水平线上,必定还会出现奇数个交点(此点可以多画几个图进行求证)。所以此点计算为1次。
  • ⑤点的位置与⑥点的位置处于同一Y轴上面。可以忽略他们之间的点,直接进行连接。当然也可以把⑤、⑥之间的点重复计算,假设⑤⑥两个点之间还有两个点:AB。那么他们的连线就是⑤-AA-BB-⑥。可以看到AB可以被double计算。⑤、⑥的连线就可以计算为,⑤,AABB,⑥ ⑥、⑦也是处于水平线,同上计算方式。

2. 普通交点计算方法

由于特殊点顶点,水平线点都已经被计算了,所以可以直接计算顶点之间的线段与水平线的交点。只需求出线性方程的lambda(λ)值,直接将水平线Y值代入,就可以求出交点的X值。扫描线按顺序求出交点就全部OK了

填充方式

获取交点后就直接存入迭代器,根据Y轴的大小进行排序,然后通过X的大小进行排序,奇偶连接同一Y轴上的交点,就能出现上图的效果了。

PainterPath 与 个人扫描线填充算法

PainterPath的强大的图像填充能力是毋庸置疑的,但是在强大的背后,都没有找到填充后返回出填充区域的接口。真是无奈,只能自己写算法进行处理。所幸速度并不慢。

推荐文章