RE: tracing

> 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

 ----1*5< scan clockvise around the pixel
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

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

 -----*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

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

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();

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]