15

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?

sydd
  • 1,824
  • 2
  • 30
  • 54
  • I'm thinking some kind of recursive brute force algorithm. Start with a nearby line and recurse into the lines it overlaps, until you are back at the first line. – Bart van Heukelom May 01 '11 at 21:54
  • What do you mean by "recurse into the lines it overlaps"? what does the recursive function do? – sydd May 01 '11 at 22:02
  • A recursive function calls itself over and over again until some condition is met. – elekwent May 01 '11 at 22:09
  • @elekwent Well i know that. I was asking Bart about the details of the algorithm he was thinking of, because his description was way too vague. – sydd May 01 '11 at 22:27
  • 1
    Sorry, I tend to read people's comments literally on here. It backfires quite often. – elekwent May 01 '11 at 22:42
  • My description was vague because the idea is. If I knew exactly what to do, I would've posted it as answer instead of comment :p – Bart van Heukelom May 02 '11 at 11:22
  • 2
    @sydd The resulting fill needs to be vector or a bitmap? – Sean Fujiwara May 05 '11 at 00:33
  • @sean good question :) i would prefer a vector (coordinates of the polygon to fill), i dont want to draw, then rasterize my image, fill the bitmap, and copy the solution back. But this might be the only way to do it.. – sydd May 05 '11 at 01:30
  • @sydd : Hi, I am having similar scenario, could you please guide me how did you solve it ? Thanks. – Nitesh Nov 22 '13 at 04:23
  • 1
    @Nitesh I got the book that hvidgaard was talking about and implemented the point locator algorithm described there. Note, that the graph representation (DCEL) and the data structure used to store the points is as vital as the algorithm itself. There is no opensource implementation in Actionscript afaik, but I might opensource mine sometime. – sydd Nov 22 '13 at 23:10
  • @sydd: Thank you. Yes I am also ordering the book. It seems a good book. I am implementing it in C#. One thing I wanted to ask, will the algorithm work for all shapes like Arcs, Splines or just for Lines ? – Nitesh Nov 23 '13 at 04:26
  • @Nitesh The point location algorithm only works with straight lines. Im inclined to think that you are phrasing the problem in a wrong way if you need it work for splines unless you do something like research for PHD.. – sydd Nov 23 '13 at 12:51
  • My idea for this is to go from the fill point x,y of the mouse, and then go up until you find a line. Then, for each other line, find all the neighbors of that line. Then, find all the neighbors of the next line, etc, until you have some complete loops that go all the way around. After that, you fill each loop on a seperate canvas, and see if any points in the loop are actually inside of the different fill. Then, the correct answer is the loop that doesn't contain any points in it. Pre-req is that every intersection is a point to start. – dansch Feb 16 '15 at 00:40
  • [Inkscape](http://inkscape.org/) can do this. May be you can find how it is implemented in the source. – Maxence Feb 27 '15 at 08:31

3 Answers3

6

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/

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.

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.

hvidgaard
  • 495
  • 2
  • 13
1

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!

Oliver Emberton
  • 951
  • 4
  • 14
  • @oliver-emberton I dont think this approach will work, how do you find the closed shapes inside the area to be filled? (i added an example for it) – sydd May 04 '11 at 10:09
  • @sydd - You're correct, all the code I submitted does is find the intersecting co-ordinates between the lines. To determine the shape(s) within is more involved - I don't have an immediate solution off-hand. – Oliver Emberton May 04 '11 at 10:39
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.

Oliver Emberton
  • 951
  • 4
  • 14
  • My problem is not the filling, but how to determine the boundaries of the area to fill. I will make an example image – sydd May 03 '11 at 16:15
  • @sydd - So you're looking to find where the lines intersect, and then fill inside that? An image would help, thanks. – Oliver Emberton May 03 '11 at 16:16