Find convex hull using scipy with explanation


  • 4

    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

  • 1
    D

    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]
    

Log in to reply
 

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