LeetCode 469: Convex Polygon

Problem Restatement

We are given a list of points in the 2D plane.

The points are already ordered around the polygon. Connecting them sequentially forms a simple polygon. That means the edges do not cross each other except at shared vertices.

We need to return whether the polygon is convex. A polygon is convex if it always turns in the same direction as we walk around its boundary. The problem guarantees at least 3 points and at most 10^4 points. Coordinates are in the range -10^4 to 10^4.

Input and Output

Function shape:

def isConvex(points: list[list[int]]) -> bool:
    ...

Examples

Example 1:

points = [[0, 0], [0, 5], [5, 5], [5, 0]]

This is a square.

As we walk around the polygon, every turn has the same direction.

Answer:

True

Example 2:

points = [[0, 0], [0, 10], [10, 10], [10, 0], [5, 5]]

The last point creates an inward dent.

The polygon changes turn direction.

Answer:

False

First Thought: Check Every Interior Angle

A convex polygon has every interior angle less than or equal to 180 degrees, depending on whether collinear boundary points are allowed.

So one direct idea is to compute every angle between adjacent edges.

But angle computation needs floating-point arithmetic, inverse cosine, and careful precision handling.

Geometry problems usually avoid angles when possible.

A better tool is the cross product.

Key Insight

For three consecutive points:

a, b, c

look at the turn from edge a -> b to edge b -> c.

The 2D cross product tells us the turn direction:

cross = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x)

Interpretation:

For a convex polygon, all non-zero turns must have the same sign.

If we ever see both a positive cross product and a negative cross product, the polygon is concave.

Algorithm

Initialize:

sign = 0

This stores the first non-zero turn direction.

Loop through every index i.

Take three consecutive points:

points[i]
points[(i + 1) % n]
points[(i + 2) % n]

The modulo wraps around the polygon so the last vertices are also checked.

Compute the cross product.

If the cross product is 0, continue.

If sign == 0, set sign to this cross product.

Otherwise, if the current cross product has the opposite sign from sign, return False.

If the loop finishes, return True.

Walkthrough

Use the square:

points = [[0, 0], [0, 5], [5, 5], [5, 0]]

Check consecutive triples.

For:

[0, 0], [0, 5], [5, 5]

Vector a -> b is upward.

Vector b -> c is rightward.

The cross product is negative, so this is one turn direction.

The remaining corners also give negative cross products.

Since every non-zero turn has the same sign, the polygon is convex.

Now use:

points = [[0, 0], [0, 10], [10, 10], [10, 0], [5, 5]]

Most outer corners turn in one direction, but the point [5, 5] creates an inward turn.

At some consecutive triple, the cross product sign changes.

So the algorithm returns:

False

Correctness

For a simple polygon whose vertices are listed in boundary order, convexity is equivalent to never changing turn direction while walking around the boundary.

The cross product of two consecutive edge vectors gives the direction of that turn.

A positive value means one orientation, and a negative value means the opposite orientation.

The algorithm records the first non-zero turn direction. It then checks every other non-zero turn.

If any turn has the opposite sign, the boundary turns both left and right, so the polygon has an inward angle and is not convex.

If no opposite sign is found, all non-zero turns are consistent. Since the polygon is guaranteed to be simple, consistent turn direction around the boundary means the polygon is convex.

Therefore, the algorithm returns the correct result.

Complexity

Let n = len(points).

Implementation

class Solution:
    def isConvex(self, points: list[list[int]]) -> bool:
        def cross(a: list[int], b: list[int], c: list[int]) -> int:
            ab_x = b[0] - a[0]
            ab_y = b[1] - a[1]
            bc_x = c[0] - b[0]
            bc_y = c[1] - b[1]

            return ab_x * bc_y - ab_y * bc_x

        n = len(points)
        sign = 0

        for i in range(n):
            value = cross(
                points[i],
                points[(i + 1) % n],
                points[(i + 2) % n],
            )

            if value == 0:
                continue

            if sign == 0:
                sign = value
            elif sign * value < 0:
                return False

        return True

Code Explanation

The helper computes the cross product for three consecutive points:

def cross(a, b, c):

It builds the two edge vectors:

ab = b - a
bc = c - b

Then returns:

ab_x * bc_y - ab_y * bc_x

The variable:

sign = 0

means we have not found a non-collinear turn yet.

The modulo indices:

(i + 1) % n
(i + 2) % n

make the check wrap around the end of the polygon.

If the cross product is zero:

if value == 0:
    continue

the three points are collinear, so they do not determine a left or right turn.

The first non-zero value sets the expected sign:

if sign == 0:
    sign = value

A later opposite sign means the polygon turns in both directions:

elif sign * value < 0:
    return False

If no contradiction appears, the polygon is convex.

Testing

def run_tests():
    s = Solution()

    assert s.isConvex([[0, 0], [0, 5], [5, 5], [5, 0]]) is True

    assert s.isConvex([
        [0, 0],
        [0, 10],
        [10, 10],
        [10, 0],
        [5, 5],
    ]) is False

    assert s.isConvex([[0, 0], [1, 1], [2, 0]]) is True

    assert s.isConvex([
        [0, 0],
        [2, 0],
        [4, 0],
        [4, 2],
        [0, 2],
    ]) is True

    assert s.isConvex([
        [0, 0],
        [4, 0],
        [4, 4],
        [2, 2],
        [0, 4],
    ]) is False

    print("all tests passed")

run_tests()

Test meaning: