矢量图形洪水填充算法? [英] Vector graphics flood fill algorithms?
问题描述
我正在开发一个简单的绘图应用程序，我需要一种算法来进行洪水填充.
用户工作流程将如下所示(类似于 Flash CS，只是更简单):
I am working on a simple drawing application, and i need an algorithm to make flood fills.
The user workflow will look like this (similar to Flash CS, just more simpler):
- 用户在工作区上绘制直线.它们被视为矢量，可以在绘制后进行选择和移动.
- 用户选择填充工具，然后单击绘图区域.如果该区域在各个方向都被线条包围，则会对该区域应用填充.
- the user draws straight lines on the workspace. These are treated as vectors, and can be selected and moved after they are drawn.
- user selects the fill tool, and clicks on the drawing area. If the area is surrounded by lines in every direction a fill is applied to the area.
如果在应用填充后移动线条，填充区域也会相应改变.
if the lines are moved after the fill is applied, the area of fill is changed accordingly.
任何人都有一个好主意，如何实现这样的算法?主要任务基本上是确定一个点周围的线段.(并以某种方式存储此信息，以防移动行)
Anyone has a nice idea, how to implement such algorithm? The main task is basically to determine the line segments surrounding a point. (and storing this information somehow, incase the lines are moved)
解释图像:(当然画布中可以有其他线条，这对填充算法无关紧要)
an explanation image: (there can be other lines of course in the canvas, that do not matter for the fill algorithm)
更困难的情况:
我找到了一种用孔填充多边形的方法 http://alienryderflex.com/polygon_fill/ ，现在的主要问题是，我如何找到我的多边形?
I have found a way to fill polygons with holes http://alienryderflex.com/polygon_fill/ , now the main question is, how do i find my polygons?
推荐答案
您正在寻找一种点定位算法.这不是太复杂，但也不够简单，无法在这里解释.这本书中有一个很好的章节:http://www.cs.uu.nl/geobook/
You're looking for a point location algorithm. It's not overly complex, but it's not simple enough to explain here. There's a good chapter on it in this book: http://www.cs.uu.nl/geobook/
当我回到家时，我会拿到这本书的副本，看看我是否可以尝试一下.您只需要了解很多细节.这一切都归结为构建输入的 DCEL 并在添加或删除行时维护数据结构.任何使用鼠标坐标的查询都将简单地返回组件的内部半边，特别是那些包含指向所有内部组件的指针，这正是您所要求的.
When I get home I'll get my copy of the book and see if I can try anyway. There's just a lot of details you need to know about. It all boils down to building a DCEL of the input and maintain a datastructure as lines are added or removed. Any query with a mouse coord will simply return an inner halfedge of the component, and those in particular contain pointers to all of the inner components, which is exactly what you're asking for.
不过，有一件事是你需要知道输入中的交点(因为如果你有相交线，你就不能构建梯形图)，如果你能摆脱它(即输入是足够少的段)我强烈建议您只使用简单的 O(n²) 算法(简单、可编码且可在不到 1 小时内测试).O(n log n) 算法需要几天时间来编写代码并使用一种巧妙且非常重要的数据结构来处理状态.然而，书中也提到了它，所以如果你觉得能胜任这项任务，你有两个理由购买它.总的来说，这是一本关于几何问题的好书，因此仅此原因，任何对算法和数据结构感兴趣的程序员都应该拥有一本.
One thing though, is that you need to know the intersections in the input (because you cannot build the trapezoidal map if you have intersecting lines) , and if you can get away with it (i.e. input is few enough segments) I strongly suggest that you just use the naive O(n²) algorithm (simple, codeable and testable in less than 1 hour). The O(n log n) algorithm takes a few days to code and use a clever and very non-trivial data structure for the status. It is however also mentioned in the book, so if you feel up to the task you have 2 reasons to buy it. It is a really good book on geometric problems in general, so for that reason alone any programmer with interest in algorithms and datastructures should have a copy.
这篇关于矢量图形洪水填充算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
