Description

You could draw a polygon around the cloud, where the corners are made up of points from the cloud. There is one shape which has the lowest number of corners and still contains all the other points; this is the convex hull. This is demonstrated in the figure below

The cloud consists of point 1 to 12. The convex hull consists of 6 points:

xj , yj with j ∈ [8, 10, 12, 5, 6, 7]

The order of the points matters, the shape is drawn from one point to the next. The starting point of the set does not matter, so the convex hull set can be offset:

xj , yj with j ∈ [10, 12, 5, 6, 7, 8]

Write a function getConvexHull(x,y) that returns the indices of the points that lay on the convex hull of the cloud, defined by a list of x- and y-coordinates x and y. Both input arrays have length n, with n ≥ 3. Make sure the indices of the points on the hull are sorted to go around the cloud counter-clockwise.