位图与扫描线种子填充算法

这周攻克了一个项目上困扰了我小半年的技术难点,在此做一下总结。
项目的需求是做一个这样的填色功能。

效果图

在网上找到的资料非常少,期间尝试过:

  1. 导出SVG图片再转成UIBezierPath的路径去填色
  2. 导出SVG图片再使用PaintCode 转成UIBezierPath路劲代码

都以失败告终。
在走了大量的弯路之后,深入学习了图形学的算法,了解到有一种高效率的多边形填充算法:扫描线种子填充算法。

扫描线种子填充算法是一种避免递归,提高效率的思想。可以通过多边形区域内的一个种子点开始,到边界为止,延伸成一条等Y线划过屏幕当多边形上的点与扫描线重合时,这些点被填充。

在项目实现算法之前我们还需要了解一下位图(bitmap)。

A bitmap image (or sampled image) is an array of pixels (or samples). Each pixel represents a single point in the image. JPEG, TIFF, and PNG graphics files are examples of bitmap images

这段话可以这么理解,位图其实是一个像素的数组,每个像素代表着图片中的一个点. 所以,填色实际上是将某个数组内的点的颜色属性赋值的一个过程