3
$\begingroup$

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:
(This is a diagram of what I need and have)

  • 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:
Getting the center of the points and walking around with the angles lowest angle to highest

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
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
Using A tree and the 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.

$\endgroup$
3
  • $\begingroup$ I would have added the images as an embed but for SOME reason, you need 10 rep points to add embeded images. Thanks stack overflow. $\endgroup$ Oct 19, 2021 at 23:59
  • $\begingroup$ Have you considered using Marching Squares? $\endgroup$ Oct 20, 2021 at 2:05
  • $\begingroup$ @shawn_halayka I forgot about that algorithm and it would have worked but I needed the order to be clockwise. Good answer though $\endgroup$ Oct 20, 2021 at 2:13

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Sounds like it would work, i'm going to need to draw it out though to fully understand each thing I need to do but the explaination should be fine. Thank you! $\endgroup$ Oct 20, 2021 at 0:16
  • $\begingroup$ @OwenTheProgrammer : A diagram that might get you started is this one. (It's oriented anticlockwise, instead of your preferred clockwise.) $\endgroup$ Oct 20, 2021 at 0:19
  • $\begingroup$ Yeah that looks like what I had in my mind reading through $\endgroup$ Oct 20, 2021 at 0:31
  • $\begingroup$ +1 but this algorithm can fail if you have a vertex shared by two non-adjacent squares (eg. only the squares at NE and SW with respect to a vertex are occupied). In the case of two outgoing edges, one need to have a rule to decide which edge to follow. $\endgroup$ Oct 20, 2021 at 0:38
  • 1
    $\begingroup$ @achillehui : This is a valid concern. I may have taken the example's strong connectedness too literally. The best rule I know for addressing this is to track the two squares (inside and outside) separated by "this edge". When there is ambiguity, select the new edge that also borders the outside square. $\endgroup$ Oct 20, 2021 at 12:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .