scipy.spatial.ConvexHull(points) returns all points that form the hull.
It helps a lot already. However, in this question, we need to return all points on the hull.
I write a funciton
isHull(point, hull) to check if a point is on the hull.
When ConvexHull throws a exception, it means the points can not form a hull.
In this case, I return all points.
def outerTrees(self, points): from scipy.spatial import ConvexHull import numpy as np def isHull(point, hull, tol=1e-12): return any((abs(np.dot(eq[:-1], point) + eq[-1]) < tol) for eq in hull.equations) try: hull = ConvexHull([(p.x, p.y) for p in points]) return [p for p in points if isHull((p.x, p.y), hull)] except: return points
By default, qhull, which powers
scipy.spatial.ConvexHull, returns a hull without any colinear points. However, there is an option you can pass to return them, which I think makes the solution cleaner:
from scipy import spatial from itertools import chain class Solution(object): def outerTrees(self, points): """ :type points: List[Point] :rtype: List[Point] """ try: hull = spatial.ConvexHull([(p.x, p.y) for p in points], qhull_options='Qc') except: return points points = [hull.points[i] for i in chain(hull.vertices, hull.coplanar[:,0])] return [Point(int(x), int(y)) for x,y in points]