Processing 1.0 - Processing Discourse - Vector based Flood-fill?

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Programs › Vector based Flood-fill

‹ Previous Topic | Next Topic ›

Pages: 1

Vector based Flood-fill? (Read 808 times)

Vector based Flood-fill?
Oct 5^th, 2007, 2:17pm

I was hoping someone might have some ideas on how to approach coding a vector based floodfill. That is given a set of intersecting lines such as:
http://img266.imageshack.us/my.php?image=vectorfloodfillbg7.png

You can then click inside one of the enclosed shapes and fill it with colour.

I found a bitmap way of approaching this here:
http://processing.org/discourse/yabb/YaBB.cgi?board=Syntax;action=display;num=1112372959

However I want to do it by tracing around the points accurately to form a shape that can then be exported to PDF as vector.

My initial thought is to work out the closest point to the mouse click and then use some sort of path finding algorithm to trace around the line something akin to this:
http://wiki.gamegardens.com/Path_Finding_Tutorial

Or would it be better to use the flood fill to find the edges, then strip out the uneccessary points based on comparison with the list of line points?

Any and all ideas on how to approach this very much appreciated!
Thanks in advance.

ewjordan

Re: Vector based Flood-fill?
Reply #1 - Oct 7^th, 2007, 1:40pm

If you are dealing with regions without holes and without single lines cutting into your polygon, then this is fairly straightforward.

1) Find one of the lines on the edge of your region.
2) Keep track of which side is the interior.
3) Walk along the edge of the polygon, say counterclockwise. You find the next edge to move to by calculating the angle (relative to the current edge's direction) of each edge connected to the "end" vertex on the current edge (you actually calculate the z component of the cross product, which serves as a good proxy for the angle for ordering purposes over the range -pi to pi), and you pick the one with the most negative cross product.
4) Go back to step 2 and repeat until you hit the first edge again, then you're done.

There are some subtleties, like the fact that you need to find the first edge, you need to trim all single lines, you need to decompose all line crossings into edges and nodes, you need to handle failure properly (when you're not in a connected region), you need to figure out what to do about holes, etc. But I think the basic idea is clear, at least.

You might want to Google this, I suspect it's a pretty well researched computational geometry problem, and there might be better algorithms that do it faster.

ewjordan Ex Member	Re: Vector based Flood-fill? Reply #2 - Oct 7^th, 2007, 1:42pm Just one thing: when you calculate the cross product, you have to make sure to normalize the edges first. In other words, you're not taking a cross product of one edge with another, you're taking a cross of one edge's direction with the other edge's direction.

Re: Vector based Flood-fill?
Reply #3 - Oct 7^th, 2007, 4:17pm

Thanks for your considered reply ewjordan.

I probably should have mentioned that the lines will be user-created and thus full of holes and single lines cutting into the polygons Sad

So this is unfortunately what complicates the problem.

I have however found a useful looking library called the 'JTS Topology Suite':
http://www.vividsolutions.com/jts/JTSHome.htm

Which has a function to 'Polygonize' a set of non-intersecting lines. It can even node the lines for you with a union function. More info here if you are interested:
http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Thanks again for your help!

ewjordan

Re: Vector based Flood-fill?
Reply #4 - Oct 8^th, 2007, 2:22am

Yeah, I would definitely suggest going with a package that someone else has already debugged and all that, at least if it has the right functionality (the one you mentioned is LGPL, too, which is good). There's always the temptation to reinvent the wheel, but if this functionality isn't the main purpose of your program, then it's easier and safer to leave it up to someone that _did_ concentrate on that one piece.

Pages: 1

‹ Previous Topic | Next Topic ›