I have a one-bit image (each pixel is either black or white) of a polygon or polygons - the edges of the image are always black. I would like to convert this to a set of one or more polygon vectors, where each vector is simply an ordered list of points (one list per polygon) describing the corners or approximating curves.
Attached is an example input image with red dots overlayed to show what the output points should be. It should be two lists of points of course. The threshold for placing points around a curve is arbitrary and not important.
The input polygons will never have holes.
Speed is irrelevant; this is not being done at realtime and is just precomputed.
The actual scenario, if you're wondering, is that I have airspace regions defined as simple polygonal regions (one list of coordinates per polygon) which are either unioned or subtracted. The sample image illustrates an example of this (not actual airspace, just a simple test). I started with a hexagon, then subtracted from it a quadrilateral (which splits the hexagon in two), then I added (unioned) a circle. Trying to directly generate vector polygons from these input polygon vectors would be maddening; I figure it's simpler to render them as raster polygons temporarily (additive is drawn in white, subtractive in black) and then convert that.
Step one, edge detection, becomes trivial obviously; it's any white pixel adjacent to a black pixel.
Step two is to create huge unsimplified ordered lists of edge points. My plan is to create a bucket of all edge pixels, then (sloppy pseudocode):
point = bucket.pop()
isDone = false
while !isDone
{
isDone = true
for all edge pixels in bucket
{
if this edge pixel is adjacent to point
{
append edge pixel to polygon points
point = edge pixel
isDone = false
break;
}
}
}
Then if there is anything remaining in the bucket, repeat the process for the next new polygon.
The third and final step, and one that I definitely can't seem to figure out, is to simplify these lists of every edge into just the ones that mark the corners (or that approximate to some threshold the curves).
Can anyone help?