4
$\begingroup$

Given a random set of points in 2D space such as:

Random points

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:

Corrected points with polygon

$\endgroup$
  • $\begingroup$ Are you looking for a theoretical solution or a practical one that you can apply? $\endgroup$ – N. Owad Feb 11 '15 at 18:08
  • $\begingroup$ A practical one ideally. $\endgroup$ – terminex9 Feb 11 '15 at 18:09
  • 3
    $\begingroup$ For what it's worth, it looks like your bottom line could just go from the bottom-left point to the bottom-right point and you'd get a smaller perimeter. Isn't this the same as the convex hull of the points? $\endgroup$ – 211792 Feb 11 '15 at 18:10
  • 1
    $\begingroup$ @AustinC is right. If you have a non-convex solution, then replacing a concave part with a direct connection shortens the perimeter. Hence tha optimal solution is th eocnvex hull. $\endgroup$ – Hagen von Eitzen Feb 11 '15 at 18:13
  • 1
    $\begingroup$ Yes, AustinC and Hagen are correct. Here is a good page about it. $\endgroup$ – N. Owad Feb 11 '15 at 18:16
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For your first point did you mean to say "smallest y-coordinate" twice? It seems like there could still be ties that way. $\endgroup$ – terminex9 Feb 11 '15 at 18:23
  • $\begingroup$ It was a typo. It was x-coordinate. Thank you. :-) $\endgroup$ – Filippo De Bortoli Feb 11 '15 at 18:23
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.