Python, AM Chain with Explanation


  • 8

    Based on the formula for the signed area of a triangle, we can find whether a triangle PQR has vertices which are counter-clockwise (sign 1), collinear (sign 0), or clockwise (sign -1).

    We will now perform the AM-Chain algorithm for finding the lower and upper hulls which together form the convex hull of these points.

    To find the lower hull of points, we process the points in sorted order. Focus on the function drive. Our loop invariant is that we started the function drive with a lower hull, and we return a lower hull. This answer must include the new right-most point r as it cannot be contained by some points below it. During the while loop, whenever our last turn XYZ was clockwise, the middle point Y cannot be part of the lower hull, as it is contained by WXZ (where W is the point in the hull before X.)

    We can do this process again with the points sorted in reverse to find the upper hull. Both hulls combined is the total convex hull as desired.

    def outerTrees(self, A):
        def sign(p, q, r):
            return cmp((p.x - r.x)*(q.y - r.y), (p.y - r.y)*(q.x - r.x))
        
        def drive(hull, r):
            hull.append(r)
            while len(hull) >= 3 and sign(*hull[-3:]) < 0:
                hull.pop(-2)
            return hull
        
        A.sort(key = lambda p: (p.x, p.y))
        lower = reduce(drive, A, [])
        upper = reduce(drive, A[::-1], [])
        return list(set(lower + upper))
    

  • 0

    What's "AM-Chain"?


  • 2

    I believe AM Chain means Andrew's Monotone Chain


  • 0

    why do you use cmp when calculating cross product?


  • 0

    @jedihy cmp(x, y) is 1 when x > y, 0 when x == y, and -1 when x < y. We wanted the sign of the area of triangle PQR, ie. to know if area PQR is positive (sign 1), zero (sign 0), or negative (sign -1).


  • 0

    @awice Yeah but it seems (p.x - r.x)*(q.y - r.y) - (p.y - r.y)*(q.x - r.x) still works in my solution.


Log in to reply
 

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