Original Post
I'm running into a few hurdles trying to generate inner and outer outlines for a series of 2D shapes, and I was wondering if anyone had some good approaches. The image below is a visual representation of what I have (the black boundary), and what I want (the other color outlines). You'll probably have to zoom in to see the individual pixels. 
Basically, I have a list of points with integer coordinates on a 2D grid that define the boundary of a polygon. Between each pair of adjacent points I rasterize a line onto this grid. Essentially, I turn the boundary into a 2D collection of cells that enclose the polygon's area. The shapes can be convex or concave, however we can assume that they aren't self-intersecting. What I need to be able to do is find the inner and outer outlines of these boundary cells as shown in the image. I've tried a few approaches thus far, with varying results: 1) Incremental flood-fill: Flood-fill the shape. Any cells in the flood-fill that touch the original boundary (black) become part of the inner outline (red). Flood-fill again, this time within the new inner outline (red). Any new flood-fill cells that touch this outline become part of a second outline (orange). Recurse to create as many contour "rings" as needed. The problems I had with this approach were that a) detecting where the flood-fill should begin wasn't very robust and often took a few tries to find, b) it wouldn't work when trying to create the outer outline (green), lest I flood-fill everything outside the shape(!), c) the flood-fills were very slow, especially for large areas, and d) in the case of the shape in the lower-right, if I chose the flood-fill to start in the thin part of the shape in an orange cell, it would only flood-fill a single cell (since it doesn't flood-fill in the diagonal directions). There really wasn't a way to detect this as an "invalid" fill since it technically worked (i.e. didn't leak into the world). 2) Marching squares: Start at a border cell and march to generate the inner and outer outlines. This is the approach I'm currently using, and it works very well for most shapes. The problems occur once we start generating multiple outlines. Take for instance the shape in the lower-left. The red outline is generated just fine. But when we go to generate the orange outline, we get this long "tail" that is a single cell in width. This is a valid outline, however if I were to try and generate yet another outline, this tail would completely confuse the marching algorithm since we essentially have a self-intersecting polygon. How would it know where the inner outline should be (in blue)? In the worst case it would detect the tail and do another outer outline. Would I have to try and scan for the inside first? Hopefully I've explained my problem clearly enough for someone to understand :) My biggest problem in general is that generating multiple contours eventually produces shapes that the algorithms I've tried can't handle. Ideally I'd like to stick with an adapted marching squares algorithm since it's very fast and makes a lot more sense since I only care about contours. Perhaps one march for finding contours and another march for finding interiors? EDIT: Just thinking outside the box, perhaps since this is an image-based problem, a GPU solution would be appropriate? Blurring perhaps? I'd like to stick with the CPU if I can however since I'll be performing these tasks in an area of code that doesn't have... easy access to the GPU :) But above all else I need a robust solution that works 100% of the time.
Basically, I have a list of points with integer coordinates on a 2D grid that define the boundary of a polygon. Between each pair of adjacent points I rasterize a line onto this grid. Essentially, I turn the boundary into a 2D collection of cells that enclose the polygon's area. The shapes can be convex or concave, however we can assume that they aren't self-intersecting. What I need to be able to do is find the inner and outer outlines of these boundary cells as shown in the image. I've tried a few approaches thus far, with varying results: 1) Incremental flood-fill: Flood-fill the shape. Any cells in the flood-fill that touch the original boundary (black) become part of the inner outline (red). Flood-fill again, this time within the new inner outline (red). Any new flood-fill cells that touch this outline become part of a second outline (orange). Recurse to create as many contour "rings" as needed. The problems I had with this approach were that a) detecting where the flood-fill should begin wasn't very robust and often took a few tries to find, b) it wouldn't work when trying to create the outer outline (green), lest I flood-fill everything outside the shape(!), c) the flood-fills were very slow, especially for large areas, and d) in the case of the shape in the lower-right, if I chose the flood-fill to start in the thin part of the shape in an orange cell, it would only flood-fill a single cell (since it doesn't flood-fill in the diagonal directions). There really wasn't a way to detect this as an "invalid" fill since it technically worked (i.e. didn't leak into the world). 2) Marching squares: Start at a border cell and march to generate the inner and outer outlines. This is the approach I'm currently using, and it works very well for most shapes. The problems occur once we start generating multiple outlines. Take for instance the shape in the lower-left. The red outline is generated just fine. But when we go to generate the orange outline, we get this long "tail" that is a single cell in width. This is a valid outline, however if I were to try and generate yet another outline, this tail would completely confuse the marching algorithm since we essentially have a self-intersecting polygon. How would it know where the inner outline should be (in blue)? In the worst case it would detect the tail and do another outer outline. Would I have to try and scan for the inside first? Hopefully I've explained my problem clearly enough for someone to understand :) My biggest problem in general is that generating multiple contours eventually produces shapes that the algorithms I've tried can't handle. Ideally I'd like to stick with an adapted marching squares algorithm since it's very fast and makes a lot more sense since I only care about contours. Perhaps one march for finding contours and another march for finding interiors? EDIT: Just thinking outside the box, perhaps since this is an image-based problem, a GPU solution would be appropriate? Blurring perhaps? I'd like to stick with the CPU if I can however since I'll be performing these tasks in an area of code that doesn't have... easy access to the GPU :) But above all else I need a robust solution that works 100% of the time.
