Convex Polygon - Leetcode Solution

The Convex Polygon problem on LeetCode involves determining whether a given polygon is convex or not. A polygon is convex if all its interior angles are less than or equal to 180 degrees.

Given a list of points representing the vertices of a polygon, the problem asks for a function that returns true if the polygon is convex, and false otherwise. The input is guaranteed to contain at least three points, and the vertices are given in clockwise order.

To approach this problem, we can use the concept of cross products. Recall that for two vectors a and b, the cross product a x b is a vector perpendicular to both a and b, and its magnitude equals the area of the parallelogram formed by the two vectors. Moreover, the direction of the cross product follows the right-hand rule: if you curl the fingers of your right hand from a towards b, then your thumb points in the direction of a x b.

We can use this property to determine the orientation of adjacent edges in the polygon. Specifically, given three consecutive vertices a, b, and c, we can compute the cross product of the vectors (b - a) and (c - b). If this cross product points out of the plane of the polygon (i.e., its z-coordinate is positive), then the polygon bends to the right at the vertex b; if it points into the plane (i.e., its z-coordinate is negative), then the polygon bends to the left at b. If the cross product is zero, then the edges a-b and b-c are collinear.

If we find any consecutive set of three vertices that bends to the left (i.e., has a negative cross product), then we know the polygon is non-convex. Otherwise, if all cross products are non-negative, then the polygon must be convex.

Here's the code implementation for this approach:

def isConvex(points):
    n = len(points)
    prev = 0
    curr = 0
    for i in range(n):
        # compute cross product of consecutive edges
        dx1 = points[(i+1)%n][0] - points[i][0]
        dy1 = points[(i+1)%n][1] - points[i][1]
        dx2 = points[(i+2)%n][0] - points[(i+1)%n][0]
        dy2 = points[(i+2)%n][1] - points[(i+1)%n][1]
        cross = dx1*dy2 - dx2*dy1
        # determine orientation and update
        if cross < 0:
            curr = -1
        elif cross > 0:
            curr = 1
        else:
            continue
        # check if orientation changed
        if curr*prev == -1:
            return False
        prev = curr
    return True

The function takes a list of (x, y) coordinate pairs as input, and returns True if the polygon is convex, and False otherwise. It first computes the cross product of the first three vertices to initialize the orientation variable. Then, for every consecutive set of three vertices, it computes the cross product and updates the orientation accordingly. If the orientation changes from clockwise to counterclockwise or vice versa, then the polygon is non-convex and the function returns False. Otherwise, if the loop completes without finding any negative cross products, then the polygon is convex and the function returns True.

In terms of time complexity, the function performs a constant number of operations per vertex, so its runtime is O(n) where n is the number of vertices in the polygon.

1