[FIXED] How to find corner points of a polygon composed of squares?

Issue

A group of adjacent squares compose a polygon, all coordinates of 4 vertexes of the squares are known, but order of squares is unknown.

In the example image, I highlight all corner points by red dots. If connect them in correct order, a full shape can be restored like place squares at correct positions.

So the question is, how to find the red dots, and their order?

And maybe a further question is what if the shape has some holes?

Solution

1. Count how many times each vertex occurs in your input. The ones that occur an odd number of times are your "corners". Mark these vertices as "corners".

2. Count how many times each edge occurs in your input. Edges that occur only once are your "outer-edges", mark these as outer (the edges that occur twice are inner-edges, we don't care about them).

3. Pick a "corner" with one or more unused outer-edges at random, follow one of it's outer-edges in a straight line (i.e., keeping the same direction) through the "even" vertices until you reach another corner (odd vertex).

4. Continue out from the new corner, using only previously unused straight-edges. When you return to your starting corner, you have completed a list of corners in-order for that (semi?-)connected shape.

5. If there are still corners with unused outer-edges then pick one of them at random and go to step #3. Repeat this step until all corners' outer-edges are accounted for.

Answered By - RBarryYoung

Answer Checked By - Cary Denson (PHPFixing Admin)