RE: tracing

[Svanberg Liss <lisss ydab se>]

> Does anybody know of a good algorithm to "trace" an arbitrarily
> shaped pixmap, and turn it into a set of coordinates that are
> suitable for reproducing the shape using a Polygon item?
>
> Fortunately the area I am tracing is a solid color, so I don't
> have to get too fancy.

If you have got one solid colored polygon on a pixmap, you could perhaps do
something like this;

Find the first pixel of the solid color ( scan for it ).
 -------- ( pixmap with a solid, one colored polygon )
 -----*--
 ----***-
 ----***-
Begin to scan around this pixel for the searched color, just scan the
closerst pixels around it ( +/- one pixel in various directions ).
 --------
 -----*< this is probably the first pixel you encounter
 ----***-
 ----***-

 ----234-
 ----1*5< scan clockvise around the pixel
 ----876-
 ----***-
begin scan at the previous pixel ( that hadn't got the color you was
searching for )

when you hit the color

 --------
 -----< if we begin here
 ----***< here is the first color change
 ----***-

note the coordinates down, move to this pixel, and repeat the procedure as
before, but start the new scan on the previous pixel (that belongs to the
polygon) , then scan for the first colorchange clockvise.

 --------
 -----*< this was the previous pixel
 ----***< this is now the current pixel
 ----***-

 --------
 -----123
 ----*8*4 first scan will look like this
 ----*765

 --------
 -----*o< first scan will stop here
 ----***< this is now the current pixel
 ----***-

You will now have found a pixel that is not part of the poygon.
Start a new scan from here, again scan clockvise until you find a pixel with
the color you are searching.
 --------
 -----*o< begin new scan here
 ----***< still the current pixel
 ----***-

 --------
 -----812
 ----*7*3< this is now the current pixel, redo scan.
 ----*654

When you come back to the orginal point, you should have a list of
coordinates describing the area.

I'm not sure if this was what you asked for, and if it can be adopted to
your problem.

NOTE: This algorithm is not taken from a book, so it has not been tested.
Ever. At least not by me. At least not with a computer, I've only been
fiddling with it on a paper... but to me, it seems to work with concave
polygons. It wont work with polygons with holes inside them, because it wont
recognize the holes.

// Liss
--- while( 1 ) fork();