# Find convex hull using scipy with explanation

• `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]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.