Given a random set of points in 2D space such as:
How would one go about finding the smallest perimeter polygon that encompasses all points and has a point as each one of its vertices? For the above diagram the polygon would be:
[Math] Find polygon with smallest perimeter that encompasses all points
computational geometrygeneral-topologygeometry
Related Solutions
Assuming you know the point's coordinates and which line segment (or segments, if it's a vertex) the point is located on, you just need to calculate the minimum distance from the point to each remaining line segment. You can see how to calculate this minimum distance here. The minimum of these minimums will then be the closest point.
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.
Best Answer
This problem can be solved using the Graham scan. How does it work?
This is how the Graham scan works - my explanation is really simplified, but you'll find the detailed mechanism explanation on the Wikipedia page.