Method for combining tiled squares defined as points into vectors

Question

If I tile squares, and the squares can be defined by their coordinates, how can I simplify shapes made of multiple squares into vectors that define each edge of the entire shape? Pseudo-code or general terms are fine.

Answer 1

The first thing I can think of is (probably not the most efficient way) :

1) Get the bounding box of your entire tiling - which is min(x), min(y) to max(x), max(y) for all x and y of your tiles

2) For every row, start with STATE==EMPTY, iterate over each column : STATE changes to FULL when you hit a square, and EMPTY when you find a hole. Every time STATE goes from EMPTY to FULL, save the left hand line segment of that square and every time STATE goes from FULL to EMPTY, save the right hand line segment of that square.

3) Repeat above in the Y axis

Now you have a set containing only the outermost line segments, you can combine those that are co-linear etc and get the overall shape.

This will work for non-convex shapes and also if you have holes in your tiling.