# 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

| Item | Meaning |
|---|---|
| Input | `points`, a list of `[x, y]` coordinates |
| Output | `True` if the polygon is convex, otherwise `False` |
| Given order | Points are connected sequentially |
| Assumption | The polygon is simple |
| Constraint | `3 <= points.length <= 10^4` |

Function shape:

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

## Examples

Example 1:

```python
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:

```python
True
```

Example 2:

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

The last point creates an inward dent.

The polygon changes turn direction.

Answer:

```python
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:

```python
a, b, c
```

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

The 2D cross product tells us the turn direction:

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

Interpretation:

| Cross value | Meaning |
|---:|---|
| Positive | Left turn |
| Negative | Right turn |
| Zero | Collinear points |

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:

```python
sign = 0
```

This stores the first non-zero turn direction.

Loop through every index `i`.

Take three consecutive points:

```python
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:

```python
points = [[0, 0], [0, 5], [5, 5], [5, 0]]
```

Check consecutive triples.

For:

```python
[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:

```python
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:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We inspect each vertex once |
| Space | `O(1)` | Only a few variables are stored |

## Implementation

```python
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:

```python
def cross(a, b, c):
```

It builds the two edge vectors:

```python
ab = b - a
bc = c - b
```

Then returns:

```python
ab_x * bc_y - ab_y * bc_x
```

The variable:

```python
sign = 0
```

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

The modulo indices:

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

make the check wrap around the end of the polygon.

If the cross product is zero:

```python
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:

```python
if sign == 0:
    sign = value
```

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

```python
elif sign * value < 0:
    return False
```

If no contradiction appears, the polygon is convex.

## Testing

```python
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:

| Test | Why |
|---|---|
| Square | Basic convex polygon |
| Inward point | Concave polygon |
| Triangle | Minimum polygon size |
| Collinear points on boundary | Zero cross products should be ignored |
| Dent in rectangle | Detects sign change |