← Back to challenges

Find the Outer Points

PythonHardmathtrigonometryalgebra

Instructions

In this challenge, you will be given a set of points in the plane, which we can visualize as on the left below:

By connecting the points, one obtains a convex polygon containing all points, as on the right.

Write a function that, given a set of points, returns only the outer points (i.e. the vertices of the polygon (in the illustration, these are points circled in red)).

Examples

outer_points({(0,0), (2,0), (2,2), (0,2), (1,1)})
 ➞ {(0,0), (2,0), (2,2), (0,2)}

outer_points({(0,0), (1,0), (2,0), (0,1)})
 ➞ {(0,0), (2,0), (0,1)}

outer_points({(0,0), (0,1), (0,3), (2,1), (2,2), (3,0)})
 ➞ {(0,0), (0,3), (2,2), (3,0)}

Notes

  • The points will be given in no particular order.
  • As in the illustration, some points may be on an edge of the polygon, but not be vertices of the polygon. Such points do not count as outer points.
  • The polygon described above is also called the convex hull of the set.
python3
Loading editor…
to run
Walks through the solution with reasoning and edge cases.