14

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):

  1. the user draws straight lines on the workspace. These are treated as vectors, and can be selected and moved after they are drawn.
  2. 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)

EDIT: an explanation image: (there can be other lines of course in the canvas, that do not matter for the fill algorithm)

enter image description here

EDIT2: a more difficult situation:

enter image description here

EDIT3: 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?

4

3 に答える 3

5

ポイントロケーションアルゴリズムを探しています。それほど複雑ではありませんが、ここで説明するほど単純ではありません。この本には良い章があります：http ：//www.cs.uu.nl/geobook/

家に帰ったら、本のコピーを手に入れて、とにかく試すことができるかどうかを確認します。知っておく必要のある詳細がたくさんあります。つまり、入力のDCELを構築し、行が追加または削除されてもデータ構造を維持することになります。マウス座標を使用したクエリは、コンポーネントの内側のハーフエッジを返すだけで、特にそれらには、すべての内側のコンポーネントへのポインタが含まれています。これはまさにあなたが求めているものです。

ただし、入力の交点を知る必要があること（交差する線がある場合は台形マップを作成できないため）、それを回避できる場合（つまり、入力のセグメントが十分に少ない場合）は、次のことを強くお勧めします。単純なO（n²）アルゴリズムを使用するだけです（シンプルで、コーディング可能で、1時間以内にテスト可能）。O（n log n）アルゴリズムは、ステータスに巧妙で非常に重要なデータ構造をコーディングして使用するのに数日かかります。しかし、それは本にも記載されているので、あなたがその仕事に満足しているなら、それを購入する2つの理由があります。これは、一般的な幾何学的問題に関する非常に優れた本です。そのため、アルゴリズムとデータ構造に関心のあるプログラマーは、コピーを用意する必要があります。

于 2011-05-05T06:41:32.470 に答える
2

Try this:

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

The function returns the intersection (if any) between two lines in ActionScript. You'll need to loop through all your lines against each other to get all of them.

Of course the order of the points will be significant if you're planning on filling them - that could be harder!

于 2011-05-03T18:07:48.800 に答える
0

With ActionScript you can use beginFill and endFill, e.g.

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 also introduces support for paths:

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

If you want to get crazy and code your own flood fill then Wikipedia has a decent primer, but I think that would be reinventing the atom for these purposes.

于 2011-05-03T14:23:23.543 に答える