I am starting with a grid of numbers of a similar format to this:
4,4,4,4,4,4,4,2,9,9,9,1,1,1,1,
4,4,4,4,4,2,2,1,9,9,9,1,1,1,1,
4,4,2,4,4,2,1,1,9,1,9,1,1,9,1,
2,1,2,1,1,1,2,1,1,1,1,1,9,1,1,
9,9,9,1,1,1,1,9,9,9,9,9,2,1,1,
Each horizontally or vertically contiguous grouping of digits corresponds to a particular polygon. For instance, the 9s form 5 distinct polygons, while the 4s form a single one.
I am attempting to programatically determine the vertices of these shapes. A pseudocode version of my algorithm would be:
foreach cell in the input
if the cell has been visited
continue
else
recursively add all neighbors that match the cell's digit to a list of cells
when all neighbors have been added to the list,
find the top-most and then left-most cell. (I believe this is guaranteed to be a vertex)
starting from the top-left corner of the cell, trace the polygon clockwise
endwhen
set all cells in the list to "visited"'
endforeach
I have used this method successfully for simple polygons, both convex and concave, but there is one major flaw in this method -- it will never find holes in complex polygons.
I think I have determined an algorithm that will find the holes post-facto, but I thought I would take a step back and see if there wasn't a better, more-robust way of determining both vertices and holes simultaneously.
Any critiques / suggestions? Or am I on the right track, here?
It can be much simpler than that, actually.
Add four boolean attributes for each cell, corresponding to the left, right, top, and bottom edges (borders). If the value in a cell differs from the value in a neighboring cell, then the border exists in the current cell.
If we visualize OP's data using this scheme, we get something like
If you implement a simple destructive walker, that can start at any given cell with one to four borders, consumes the borders it walks, and walks the region boundary in counterclockwise (or clockwise) order, you get exactly the polygons you want. Note that holes in polygons will then be drawn in the opposite order.
Note that you can use a double loop to examine each cell whether a walk should be started or not. The walker itself is a simple loop: if you walk the borders keeping the border on the right side (as if you kept your right hand on it), you are guaranteed to walk the boundary counterclockwise, and arrive at the point you started from. So, other than the edge information (4 bits per cell), no extra memory is needed.
Note the "rounded" corners. If you walk the regions counterclockwise, keeping the border on the right side, these occur when you arrive in a cell with no borders at all, and need to turn right (with respect to the direction you just walked). If you cannot turn right, the walk is complete.
(I used a small C program with wide-character output to draw the above Unicode diagram, just to verify the details, so this does work.)
Here is an example program, that reads a grid (of up to 252×252 cells) from standard input, accepting only decimal digits (0 to 9), and outputs an SVG image to standard output describing the grid, grid edges, and the polygons generated:
Using OP's example input, the resulting SVG image looks like this:
If you open the SVG image in e.g. Inkscape, you can select and examine each individual polygon. The polygon outlines are thicker, with 50% opacity.
It is not difficult to see or prove that if there are $N$ cells, the above uses $O(N)$ space complexity (the
cell[][]array; $4 N$ bits for the edge data), and $O(N)$ time complexity. (For the time complexity, note that in thewhileloop, each cell can be visited at most $4 N$ times, because each visit eliminates one edge.)