convex_hull.py

"""
2D Convex Hull Code from Wikibooks
https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
"""

class hull2D:

    def convex_hull(self,points):
        """Computes the convex hull of a set of 2D points.

        Input: an iterable sequence of (x, y) pairs representing the points.
        Output: a list of vertices of the convex hull in counter-clockwise order,
          starting from the vertex with the lexicographically smallest coordinates.
        Implements Andrew's monotone chain algorithm. O(n log n) complexity.
        """

        # Sort the points lexicographically (tuples are compared lexicographically).
        # Remove duplicates to detect the case we have just one unique point.
        points = sorted(set(points))

        # Boring case: no points or a single point, possibly repeated multiple times.
        if len(points) <= 1:
            return points

        # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
        # Returns a positive value, if OAB makes a counter-clockwise turn,
        # negative for clockwise turn, and zero if the points are collinear.
        def cross(o, a, b):
            return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

        # Build lower hull 
        lower = []
        for p in points:
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
                lower.pop()
            lower.append(p)

        # Build upper hull
        upper = []
        for p in reversed(points):
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
                upper.pop()
            upper.append(p)

        # Concatenation of the lower and upper hulls gives the convex hull.
        # Last point of each list is omitted because it is repeated at the beginning of the other list. 
        return lower[:-1] + upper[:-1]


    def convexHullecoords(self,ecoords):
        p=[]
        for line in ecoords:
            p.append((line[0],line[1]))
            
        hull_data = self.convex_hull(p)
        ecoords=[]
        for i in range(0,len(hull_data)):
            ecoords.append([hull_data[i][0],hull_data[i][1],1])
        ecoords.append(ecoords[0])
        return ecoords

    ######################################################################

    
if __name__ == '__main__':
    my_hull=hull2D()
    p = [(1,1),(0,3),(0,0),(4,5),(10,10)]
    c = my_hull.convex_hull(p)
    print(p)
    print(c)