actionscript-3 - 矢量图形洪水填充算法？

Question

我正在开发一个简单的绘图应用程序，我需要一个算法来制作洪水填充。
用户工作流程将如下所示(类似于 Flash CS，只是更简单):

用户抽奖 直工作区上的线条。它们被视为矢量，可以在绘制后进行选择和移动。

用户选择填充工具，然后单击绘图区域。如果该区域在每个方向都被线包围，则对该区域应用填充。

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

任何人都有一个好主意，如何实现这样的算法？主要任务基本上是确定一个点周围的线段。 (并以某种方式存储此信息，以防移动线条)

编辑:解释图像:(当然在 Canvas 中可以有其他行，这对填充算法无关紧要)



EDIT2:更困难的情况:



EDIT3:我找到了一种用孔填充多边形的方法 http://alienryderflex.com/polygon_fill/ ，现在主要的问题是，我如何找到我的多边形？

Answer 1

您正在寻找一种点定位算法。它并不过分复杂，但也不够简单，无法在这里解释。这本书中有一个很好的章节:http://www.cs.uu.nl/geobook/

当我回到家时，我会拿到这本书的副本，看看我是否可以尝试一下。您只需要了解很多细节。这一切都归结为构建输入的 DCEL 并在添加或删除行时维护数据结构。任何带有鼠标坐标的查询都将简单地返回组件的内部半边，特别是那些包含指向所有内部组件的指针，这正是您所要求的。

不过有一件事，是你需要知道输入中的交点(因为如果你有相交线，你就不能构建梯形图)，如果你能摆脱它(即输入足够少的段)我强烈建议您只需使用简单的 O(n²) 算法(简单、可编码且可在不到 1 小时内测试)。 O(n log n) 算法需要几天时间来编写代码并使用一种巧妙且非常重要的数据结构来处理状态。然而，书中也提到了它，所以如果你觉得能胜任这项任务，你有两个理由购买它。总的来说，这是一本关于几何问题的好书，因此仅出于这个原因，任何对算法和数据结构感兴趣的程序员都应该拥有一本。