14

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

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

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

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

编辑：解释图像：（画布中当然可以有其他线条，这与填充算法无关）

在此处输入图像描述

EDIT2：更困难的情况：

在此处输入图像描述

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

4

3 回答 3

5

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

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

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

于 2011-05-05T06:41:32.470 回答
2

尝试这个：

http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/

该函数返回 ActionScript 中两行之间的交点（如果有）。您需要循环遍历所有行以获取所有行。

当然，如果您打算填写积分，积分的顺序将很重要——这可能会更难！

于 2011-05-03T18:07:48.800 回答
0

使用 ActionScript，您可以使用beginFilland 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

如果您想疯狂并编写自己的洪水填充代码，那么维基百科有一个不错的入门书，但我认为这将是为了这些目的而重新发明原子。

于 2011-05-03T14:23:23.543 回答