unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 469. Convex Polygon

link

For a not-convex polygon, the direction of travel changes: say, clockwise to counter-clockwise.

If we have three consecutive points p_i, p_{i+1}, p_{i+2}, the sign of the cross product between the two consecutive vectors: (p_i, p_{i+1}) and (p_{i+1}, p_{i+2}) gives us the direction of travel. If the direction changes, we declare the polygon to be not-convex.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        n = len(points)
        prev_dir = 0
        for i in range(n):
            p0, p1, p2 = points[i], points[(i+1)%n], points[(i+2)%n]
            x1, y1 = (p1[0]-p0[0]), (p1[1]-p0[1])
            x2, y2 = (p2[0]-p0[0]), (p2[1]-p0[1])
            curr_dir = x1*y2 - x2*y1

            if prev_dir * curr_dir < 0:
                return False
            
            prev_dir = prev_dir or curr_dir

        return True

tanvirdotzaman

,

Leave a comment