Python: Detailed & easy to understand solution

  • 0

    Solution with discussion

    Convex Polygon

    Linear Scan using orientation concept: O(N)

    Determining orientation between three points

    • Given three points p0, p1, p2, what can we say about their orientation? Say we have two vectors v1:p0->p1 and v2:p1->p2. The turn from v1 to v2 could be clockwise, anti-clockwise or v1 and v2 could be collinear.
    • Now the cross product between v1 and v2 is another vector which is perpendicular to the plane covering v1 and v2. If the turn is ant-clockwise, the cross-product is positive, otherwise it is negative. If the points are collinear, the cross product is zero.
    • v1 = (x1-x0)i + (y1-y0)j and v2 = (x2-x1)i + (y2-y1)j. Cross product rules tell us i cross i and j cross j = 0. i cross j = k and j cross i = - i cross j.
    • direction = sign(v1 X v2) = sign([(x1-x0) * (y2-y1) - (x2-x1) * (y1-y0)])

    Property of a convex polygon

    • Convex property tells us that if we take any two points on the polygon and skecth a striaght line between them, the line will lie within the polygon.
    • If we order the points of the polygon as p0, p1, p2, p3, p4,, and the turns implied by the vectors implied by each three consecutive points should be in the same direction. This means that [p0, p1, p2] would imply two vectors p0->p1 and p1->p2 and [p1,p2,p3] would imply two vectors p1->p2 and p2->p3. If the turn from p0->p1 to p1->p2 is clockwise, then the turn from p1->p2 to p2->p3 is also clockwise.
    • The code must take care of the special condition that three points might be collinear. We save the first non zero direction in a variable called prev_direction. Then any other direction must be same as prev_direction

    Useful references


    class Solution(object):
        def get_direction(self, p0, p1, p2):
            x0, x1, x2 = p0[0], p1[0], p2[0]
            y0, y1, y2 = p0[1], p1[1], p2[1]
            direction = (x1-x0)*(y2-y1) - (x2-x1)*(y1-y0)
            if direction == 0:
                return 0
            return 1 if (direction > 0) else -1
        def isConvex(self, points):
            :type points: List[List[int]]
            :rtype: bool
            if len(points) < 3:
                return False
            prev_direction = 0
            for i in range(len(points)):
                p0, p1, p2 = i%len(points), (i+1)%len(points), (i+2)%len(points)
                curr_direction = self.get_direction(points[p0], points[p1], points[p2])
                if curr_direction:
                    if curr_direction * prev_direction < 0:
                        return False
                    # Save the first non zero direction. All other directions are
                    # should be the same as this direction.
                    if not prev_direction and curr_direction:
                        prev_direction = curr_direction
            return True

Log in to reply

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