Re: tracing

[Matt Herbert <mherbert bit-net com>]

"Daniel M. German" wrote:
> 
> I am not a computational graphics expert, so take my advice with a
> grain of salt.
> 
> If the poligon you want to trace is convex, then it is not too
> difficult. You need to find a big enough sample of the edges of the
> area (since it is solid, you can do a scan from left to right, top to
> bottom). Then you compute the convex hull. The Graham Scan alg.  will
> be fine.
> 

Yeah, the convex hull was the first thing I though of as well, but
it won't cut the mustard in this situation.

> On the other hand, all the sample points that you have are in the
> periphery of the polygon (the convex hull alg. has to deal with points
> inside). So, this is my suggestion. Assume you scan from left to
> right, from top to bottom. Assign a vector to each point in the
> opposite direction to where the "inside" is. Except for points in
> horizontal lines, this will always give you a vector with a component
> in the direction of the normal to the tangent in that direction. Since
> you know how many points are there in each scanning horizontal line,
> you know which ones are the neighbors to each point. Since you know
> the direction of the "outside" you can determine which points link to
> which points in which order. I hope I was not too confusing :) Look at
> the Graham Scan alg. for an idea of how the scanning process would
> work.
> 
> the complexity of this alg. will depend on how many lines you want to
> scan and the number of points on each line that you want to scan. It
> can be fairly expensive :) although you can make it better by using
> search algorithms (binary search, for instance).
> 

Hmm, I'll have to consider this. (actually I've read it 4 times,
and I still can't make complete sense of it ... I just need some
time to absorb and reflect I guess :)

I have "Algorithms In Perl" at work.  It has a pretty good
section on the Graham Scanning alg. I'll have to dig into that.

On a related note, does anybody know how the "Fuzzy Select" tool of
the gimp is done?  I'd imagine it has to do something similar...

Thanks
-Matt