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([:-1], point) + eq[-1]) < tol) for eq in hull.equations)
                hull = ConvexHull([(p.x, p.y) for p in points])
                return [p for p in points if isHull((p.x, p.y), hull)]
                return points

  • 1

    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]
                hull = spatial.ConvexHull([(p.x, p.y) for p in points], qhull_options='Qc')
                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.