矢量图形颜色填充算法？ [英] 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)
EDIT2：更加困难的境地：
a more difficult situation:
EDIT3：我已经找到一种方法，以填补多边形孔 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.
但有一件事是，你需要知道在输入的交叉点（因为你不能建立梯形地图，如果你有相交线），如果你能摆脱它（即输入很少，足段）I强烈建议你只用天真的O（N²）算法（简单，$ C $线和检验的，在不到1小时）。在为O（n log n）的算法，需要几天的时间来code和使用一个聪明而且非常不平凡的数据结构的状态。然而，也提到了这本书，所以如果你觉得能够胜任工作，你有2个理由来购买它。这是一个非常好的书，一般的几何问题，所以对于这个原因单独与算法和数据结构感兴趣的任何程序员都应该有一个副本。
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屋！
