Python: Detailed & easy to understand solution


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/72999/python-detailed-easy-to-understand-solution

    Convex Polygon https://leetcode.com/problems/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, ...pn-1, 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

    Code

    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.