矢量图形填充算法是什么？

Question

我正在开发一个简单的绘图应用程序，需要一个算法来实现泛洪填充。

用户工作流程如下（类似于Flash CS，只是更简单）：

1. 用户在工作区上画出直线。 这些被视为向量，可以在绘制后选择和移动。
2. 用户选择填充工具，并单击绘图区域。 如果该区域在每个方向都被线包围，则应用填充。

如果在应用填充后移动线，则填充区域会相应更改。

有人有好的想法，如何实现这样的算法？ 主要任务基本上是确定环绕点的线段（并以某种方式存储此信息，以防线条移动）。

编辑：说明图像（画布中可能还有其他线条，但不影响填充算法）

编辑2：更困难的情况：

编辑3：我已经找到了一种方法来填充孔多边形，请参考http://alienryderflex.com/polygon_fill/，现在主要问题是如何找到我的多边形？

- sydd

---

抱歉，我倾向于在这里逐字阅读人们的评论。这往往会产生反效果。 - elekwent

@sydd 最终的填充需要是矢量图还是位图？ - Sean Fujiwara

@sydd：你好，我遇到了类似的情况，请问你能指导我如何解决吗？谢谢。 - Nitesh

@Nitesh 我已经拿到了 hvidgaard 所提到的书，并实现了其中描述的点定位算法。请注意，图形表示（DCEL）和用于存储点的数据结构与算法本身一样重要。据我所知，Actionscript 中没有开源实现，但我可能会在某个时候公开我的实现。 - sydd

@Nitesh 点位置算法仅适用于直线。我倾向于认为，如果您需要它适用于样条曲线，那么您可能以错误的方式表达了问题，除非您进行类似于博士研究的工作。 - sydd

Answer 1

你正在寻找一个点定位算法。它并不是过于复杂，但在此处解释起来也不简单。这本书中有一章介绍得很好: http://www.cs.uu.nl/geobook/。

当我回家后，我会拿出这本书来看看是否能够尝试。你需要了解许多细节。归根结底，就是构建输入的DCEL，并在添加或删除线时维护数据结构。任何带有鼠标坐标的查询只需返回组件的内部半边，特别是那些包含指向所有内部组件的指针，这正是你所要求的。

然而，需要注意的是，在输入中需要知道相交的部分（因为如果有相交的线，则无法构建梯形图），如果可以（即输入的段数足够少），我强烈建议您只使用朴素的O(n²)算法（简单、可编码，并且在不到1小时内可测试）。O(n log n)算法需要几天时间才能编写并使用一个聪明且非常复杂的数据结构来处理状态。然而，它也在书中提到，因此如果你感觉自己能胜任这项任务，买这本书就有两个理由了。这是一本关于几何问题的真正好书，因此任何对算法和数据结构有兴趣的程序员都应该拥有一本副本。

- hvidgaard

---

非常感谢，这似乎是个好的解决方案。代码行数不会很多，所以我认为朴素算法可以工作。 - sydd

DCEL：双连通边列表？ - Maxence

Answer 2

尝试这个： http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/ 该函数返回ActionScript中两条线段之间的交点（如果有）。您需要循环遍历所有线段以获取它们之间的所有交点。

当然，如果您计划填充这些点，则点的顺序将非常重要 - 这可能更难！

- Oliver Emberton

---

@oliver-emberton 我认为这种方法行不通，你如何找到要填充的区域内的封闭形状？（我为此添加了一个示例） - sydd

@sydd - 你说得对，我提交的代码只是找到线段之间的交点。要确定其中的形状更为复杂 - 我目前没有立即解决方案。 - Oliver Emberton

Answer 3

使用ActionScript，您可以使用beginFill和endFill，例如：

pen_mc.beginFill(0x000000,100);
pen_mc.lineTo(400,100);
pen_mc.lineTo(400,200);
pen_mc.lineTo(300,200);
pen_mc.lineTo(300,100);
pen_mc.endFill();

http://www.actionscript.org/resources/articles/212/1/Dynamic-Drawing-Using-ActionScript/Page1.html

Flash CS4 还引入了路径支持：

http://www.flashandmath.com/basic/drawpathCS4/index.html

如果你想疯狂地编写自己的泛洪填充算法，那么维基百科有一个不错的入门指南decent primer，但我认为这对于这些目的来说是重复造轮子。

- Oliver Emberton

---

我的问题不在于填充，而在于如何确定要填充的区域边界。我会制作一个示例图像。 - sydd

@sydd - 所以你想找到线相交的地方，然后填充里面吗？有一张图片会很有帮助，谢谢。 - Oliver Emberton