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.