Re:tracing

["Daniel M. German" <dmg csg uwaterloo ca>]

 Matt Herbert twisted the bytes to say:

 Matt> Hello all,

 Matt> Does anybody know of a good algorithm to "trace" an arbitrarily
 Matt> shaped pixmap, and turn it into a set of coordinates that are
 Matt> suitable for reproducing the shape using a Polygon item?

 Matt> Fortunately the area I am tracing is a solid color, so I don't
 Matt> have to get too fancy.

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.

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

 Matt> Thanks for any advice

 Matt> -Matt


 Matt> -- 
 Matt> To unsubscribe: mail gnome-devel-list-request@gnome.org with "unsubscribe"
 Matt> as the Subject.


--
Daniel M. German                  "And the world, to each individual,
                                   means the part of it with which
   John Stuart Mill ->             he comes in contact."
http://csgwww.uwaterloo.ca/~dmg/home.html
dmg@csg.uwaterloo.ca