Vector graphics flood fill algorithms?

Question

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)

EDIT2: a more difficult situation:

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?

Answer 1

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.

Answer 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!