Finding perimeter with a grid based polygon

Question

I have been banging my head against this question for a while trying to come up with an answer that isn't going to be either weird to implement, not give me what I want all the time or just take too much time to get right. I have A grid of squares and I need to make a polygon out of the perimeter of them. I know:

• The centers of the squares that are inside the polygon (Those are the blue circles)
• The vertices of the squares (Those are the White dots)
• The edge vertices (if they are needed since I have that as well) Since I am making a polygon out of this grid, I need the vertex order to be either clockwise or counter-clockwise since I can just reverse the list. Starting at the top right was only a choice I made since it's probably going to make my life the simplest starting from the outside most point then working around but it can be changed if need be.

I have thought about getting angles from the center like this:

but the problem was there was no way I could see about getting around intersections between the perimeter and the middle since they could be closer and wouldn't work.

Then I thought about Taking the closest point and weighting the distance from the point we are on to each point left, with the distance from the middle to the points while still making the distance from point to point the closest it could be.

The Minimum Weight approach

Then I thought about making A tree and getting each connection but I would have to know the connections by walking the perimeter anyways.

Using a tree and connecting triangles but that would require re-writing a lot of code

Then I thought about some version of the postman problem, but it wouldn't guarantee going around, only going through the closest points and all of them ruling out maps with equal distances from each point to the neighboring centers like one in the form of an H

Since it can go inside itself I can't use any convex hull methods, alpha hull is parameterized and could give me something I don't want, and a step by step walk around with signed fields deciding which way is the best in A situation where going two different directions are both good was too convoluted to work with. Any ideas would be gratefully appreciated; I have been working on this for a little too long and I'm probably overthinking something.

Answer 1

The following is based on a common proof method for Green's theorem.

I assume you already have a coordinate system or a labelling system for the white points in your diagram. When I say "label", I mean this set of coordinates or this label.

We are going to make a bag of directed edges between pairs of white points that lie on a side of a square. Directed edges are pairs, where the pair $(a,b)$ means the edge from the vertex labelled "$a$" to the vertex labelled "$b$". For each square, add its four edges to the bag:

• (northeast label, southeast label),
• (southeast label, southwest label),
• (southwest label, northwest label),
• (northwest label, northeast label).

This ensures that each boundary edge is included exactly once in the bag and each interior edge is included twice, once as $(a,b)$ and once as $(b,a)$. So we need to scan through the bag deleting interior edges.

For each edge, $e = (a,b)$, determine whether $(b,a)$ is also in the bag. If so delete both of them, otherwise, proceed to the next edge. (Notice that we fetch the edges from the bag in whatever order an iterator of the bag hands us the edges -- we have made no attempt to string the perimeter together into a path yet.)

Now, use min and max functions to find the right-most occupied column of squares (coordinate of right-most blue circle) and of those, the upper-most member of the column. Take the northeast corner of that square and call it $a$. (There is no square more north or more east than this square, so this vertex is on the perimeter.)

Search the bag for the edge (and there is only one) having $a$ as its first member. That edge is $(a,b)$, for some $b$, and is the first edge in the perimeter. Now search for the edge with first member $b$, obtaining the edge $(b,c)$, the second edge of the perimeter. Continue stepping along the alternating path of edge, vertex, edge, vertex, ..., until the search turns up an edge with $a$ as its second member, $(z,a)$. This is the last edge of the perimeter and closes up the perimeter.