Find polygon with smallest perimeter that encompasses all points

Question

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:

Answer 1

This problem can be solved using the Graham scan. How does it work?

1. Take a pivot point, let's say the point with the smallest y-coordinate. If there are two or more eligible candidates, take the one with smallest x-coordinate.
2. Sort the remaining points by comparing the angle that they form with the horizontal line passing through the pivot point.
3. Scan the sorted points: if you obtain a left turn, add the point to the temporarily solution, else remove the point from the collection and check backward until you obtain a left turn.

This is how the Graham scan works - my explanation is really simplified, but you'll find the detailed mechanism explanation on the Wikipedia page.

Answer 2

A convex hull has the property that every inner point is contained in some triangle from the hull, and no point on the hull is. So we need to cycle through the available triangles looking for inner points and remove them. This can be done by considering triangles two sides at a time. We can find the angles using the dot product rule, and note there are 3 cases, two for outside the angle and 1 for inside. If a point passes this test for all 3 cases, the point is inside the triangle. Alternatively draw a line from every point to every other point, and use some system of fills (if you only want a graphical solution). Note that finding a bounding rectangle is trivial.