Intro

You have a bunch of points, and you want to know the line that connects the hull around those points. Eg. you want to calculate the minimum length of the wire fence to fence off a field with a number of objects (static sheep? garden gnomes? stuffed cows?) on it.

Solution: this is a convex hull problem (decide which points make up the hull), for which Sedgewick presented the Graham Scan in the MOOC 'Algorithms I' (and the corresponding text books).

For more detail watch Sedgewick's lecture, the Graham scan algorithm explanation starts at around 4m30s: www.youtube.com/watch?v=aSjaCvJ8lzM

Additional information, algs4.cs.princeton.edu/99hull

Briefly explained the algorithm works as follows:

• choose a starting point: the point with the lowest y coordinate
• for all the other points calculate the angle they make with the starting point (to be exact: the angle between the lines through these two points and the horizontal line)
• order the points by angle (ascending)
• iterate over the points:
  • if the motion from point 1 to 2 to 3 is a clockwise motion, discard point 2, and take a step back
  • otherwise move to the next set of 3 points