Problem Description

You are given an array of points representing vertices of a polygon in the X-Y coordinate plane. Each point is given as points[i] = [xi, yi], and when you connect these points in the order they appear in the array, they form a polygon.

Your task is to determine whether this polygon is convex or not. Return true if the polygon is convex, and false otherwise.

A convex polygon is one where all interior angles are less than 180 degrees. In other words, if you walk along the boundary of the polygon, you always turn in the same direction (either always left or always right) at each vertex. No portion of the polygon "caves inward."

The problem guarantees that:

• The given points form a simple polygon (no self-intersections)
• Exactly two edges meet at each vertex
• Edges don't intersect each other except at vertices

The solution uses the cross product method to check convexity. For each set of three consecutive vertices, it calculates the cross product of the vectors formed by these points. The sign of the cross product indicates the direction of the turn:

• Positive cross product = left turn
• Negative cross product = right turn
• Zero cross product = collinear points (straight line)

The polygon is convex if and only if all turns are in the same direction (all cross products have the same sign, ignoring zeros). The code iterates through all vertices, computing (P[i+1] - P[i]) × (P[i+2] - P[i]) for each vertex P[i]. If it ever finds two non-zero cross products with opposite signs, the polygon is not convex.

Intuition

To understand if a polygon is convex, imagine walking along its perimeter. If you're always turning in the same direction at each corner (either always turning left or always turning right), then the polygon is convex. If you sometimes turn left and sometimes turn right, the polygon is concave.

How can we mathematically determine the direction of a turn? This is where the cross product comes in. When we have three consecutive points A, B, and C, we can form two vectors: vector AB (from A to B) and vector AC (from A to C). The cross product of these vectors tells us about the orientation:

• If AB × AC > 0: We're making a counter-clockwise (left) turn at point B
• If AB × AC < 0: We're making a clockwise (right) turn at point B
• If AB × AC = 0: The three points are collinear (on the same line)

The key insight is that for a convex polygon, all turns must be in the same direction. So we need to check every set of three consecutive vertices and ensure their cross products all have the same sign.

The cross product in 2D is calculated as: (x1 * y2 - x2 * y1), where (x1, y1) and (x2, y2) are our two vectors. This gives us a scalar value whose sign indicates the turn direction.

Why does this work? Because in a convex polygon, the interior angles are all less than 180°, meaning we never "flip" our turning direction. The moment we detect a sign change in our cross products (one positive and one negative), we know the polygon must have at least one reflex angle (greater than 180°), making it concave.

The algorithm cleverly uses modulo arithmetic (i + 1) % n and (i + 2) % n to wrap around the polygon, ensuring we check the turn at every vertex, including the turns involving the last and first points.

Solution Approach

The implementation follows a systematic approach to check the convexity of the polygon by examining the cross product at each vertex:

1. Initialize tracking variables:

• n stores the number of points in the polygon
• pre keeps track of the previous non-zero cross product (initialized to 0)
• cur stores the current cross product being calculated

2. Iterate through each vertex: The algorithm loops through all n vertices using index i. For each vertex at position i, we need to examine three consecutive points:

• Current point: points[i]
• Next point: points[(i + 1) % n]
• Point after next: points[(i + 2) % n]

The modulo operator % ensures we wrap around to the beginning when we reach the end of the array.

3. Calculate vectors from current point: For each vertex i, we compute two vectors:

• Vector 1: From points[i] to points[(i + 1) % n]
  • x1 = points[(i + 1) % n][0] - points[i][0]
  • y1 = points[(i + 1) % n][1] - points[i][1]
• Vector 2: From points[i] to points[(i + 2) % n]
  • x2 = points[(i + 2) % n][0] - points[i][0]
  • y2 = points[(i + 2) % n][1] - points[i][1]

4. Compute the cross product: The 2D cross product is calculated as: cur = x1 * y2 - x2 * y1

This value tells us the turn direction at the middle point of our three consecutive vertices.

5. Check consistency of turn direction:

• If cur != 0 (non-collinear points):
  • Compare cur * pre to check if both have the same sign
  • If cur * pre < 0, it means we have opposite turn directions (one positive, one negative), so the polygon is not convex - return False
  • Otherwise, update pre = cur to remember this non-zero cross product for future comparisons

6. Return the result: If we complete the loop without finding conflicting turn directions, the polygon is convex - return True.

The elegance of this solution lies in using the sign of cross products to detect turn direction changes. By multiplying cur * pre, we get a negative result only when the signs differ, immediately identifying a concave polygon without needing to track the actual turn direction explicitly.

Example Walkthrough

Let's walk through the algorithm with a simple square polygon with vertices at points = [[0,0], [2,0], [2,2], [0,2]].

Initial Setup:

• n = 4 (number of vertices)
• pre = 0 (no previous cross product yet)

Iteration 1 (i=0): Examining turn at vertex [2,0]

• Three points: [0,0], [2,0], [2,2]
• Vector 1: [2,0] - [0,0] = (2, 0)
• Vector 2: [2,2] - [0,0] = (2, 2)
• Cross product: cur = 2*2 - 0*2 = 4
• Since cur ≠ 0 and pre = 0, we set pre = 4

Iteration 2 (i=1): Examining turn at vertex [2,2]

• Three points: [2,0], [2,2], [0,2]
• Vector 1: [2,2] - [2,0] = (0, 2)
• Vector 2: [0,2] - [2,0] = (-2, 2)
• Cross product: cur = 0*2 - 2*(-2) = 4
• Check: cur * pre = 4 * 4 = 16 > 0 ✓ (same sign)
• Update pre = 4

Iteration 3 (i=2): Examining turn at vertex [0,2]

• Three points: [2,2], [0,2], [0,0]
• Vector 1: [0,2] - [2,2] = (-2, 0)
• Vector 2: [0,0] - [2,2] = (-2, -2)
• Cross product: cur = (-2)*(-2) - 0*(-2) = 4
• Check: cur * pre = 4 * 4 = 16 > 0 ✓ (same sign)
• Update pre = 4

Iteration 4 (i=3): Examining turn at vertex [0,0]

• Three points: [0,2], [0,0], [2,0] (wraps around)
• Vector 1: [0,0] - [0,2] = (0, -2)
• Vector 2: [2,0] - [0,2] = (2, -2)
• Cross product: cur = 0*(-2) - (-2)*2 = 4
• Check: cur * pre = 4 * 4 = 16 > 0 ✓ (same sign)

All cross products are positive (value 4), indicating consistent left turns. The algorithm returns True - the square is convex.

Counter-example with a concave polygon: points = [[0,0], [2,1], [1,0], [2,-1]]

When we reach the turn at vertex [1,0], we get:

• Cross product: cur = -2 (right turn)
• Previous was positive (left turn)
• Check: cur * pre < 0 → Return False immediately

The algorithm detects the sign change and correctly identifies this as a non-convex polygon.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through all n vertices of the polygon exactly once using a single for loop. Within each iteration, it performs:

• Array indexing operations with modulo: O(1)
• Basic arithmetic operations (subtraction and multiplication): O(1)
• Comparison operations: O(1)

Since all operations inside the loop take constant time and the loop runs n times, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space regardless of the input size:

• Variables n, pre, cur: O(1)
• Loop variable i: O(1)
• Temporary variables x1, y1, x2, y2: O(1)

No additional data structures like arrays, lists, or recursive call stacks are used. The space usage remains constant irrespective of the number of points in the input polygon, resulting in O(1) space complexity.

Common Pitfalls

1. Incorrectly Handling Collinear Points

One of the most common mistakes is mishandling collinear points (when three consecutive vertices lie on the same line, resulting in a cross product of zero). Developers often make these errors:

Pitfall Example:

# INCORRECT: Treating zero cross product as a sign change
def isConvex(self, points):
    n = len(points)
    pre = 0
  
    for i in range(n):
        # ... calculate cur ...
      
        # Wrong: This fails when cur is 0
        if pre != 0 and cur != 0 and pre * cur < 0:
            return False
        pre = cur  # Problem: Setting pre to 0 when points are collinear!
  
    return True

Why it's wrong: When cur = 0 (collinear points), setting pre = cur makes pre = 0. This loses track of the previous turn direction, potentially missing concavity detection later.

Correct Solution:

# Only update pre when we have a non-zero cross product
if cur != 0:
    if cur * pre < 0:
        return False
    pre = cur  # Only update with non-zero values

2. Not Wrapping Around the Polygon Correctly

Pitfall Example:

# INCORRECT: Forgetting to wrap around at the end
def isConvex(self, points):
    n = len(points)
    pre = 0
  
    for i in range(n - 2):  # Wrong: Stops too early!
        x1 = points[i + 1][0] - points[i][0]
        y1 = points[i + 1][1] - points[i][1]
        x2 = points[i + 2][0] - points[i][0]
        y2 = points[i + 2][1] - points[i][1]
        # ...

Why it's wrong: This misses checking the last two vertices where we need to wrap around to the beginning (e.g., checking vertices n-2, n-1, 0 and n-1, 0, 1).

Correct Solution:

for i in range(n):  # Check all n vertices
    point_b = points[(i + 1) % n]  # Use modulo to wrap
    point_c = points[(i + 2) % n]  # Use modulo to wrap

3. Incorrect Cross Product Calculation

Pitfall Example:

# INCORRECT: Wrong vector calculation
def isConvex(self, points):
    for i in range(n):
        # Wrong: Using vectors between consecutive points instead of from same origin
        x1 = points[(i + 1) % n][0] - points[i][0]
        y1 = points[(i + 1) % n][1] - points[i][1]
        x2 = points[(i + 2) % n][0] - points[(i + 1) % n][0]  # Wrong origin!
        y2 = points[(i + 2) % n][1] - points[(i + 1) % n][1]  # Wrong origin!
        cur = x1 * y2 - x2 * y1

Why it's wrong: The cross product needs both vectors to originate from the same point to correctly determine turn direction. Using different origins gives incorrect results.

Correct Solution:

# Both vectors should originate from points[i]
x1 = points[(i + 1) % n][0] - points[i][0]
y1 = points[(i + 1) % n][1] - points[i][1]
x2 = points[(i + 2) % n][0] - points[i][0]  # Same origin as vector 1
y2 = points[(i + 2) % n][1] - points[i][1]  # Same origin as vector 1

4. Edge Case: Polygons with All Collinear Points

Pitfall: Not considering degenerate cases where all points might be collinear (forming a line rather than a polygon).

Solution: The current implementation handles this correctly by returning True if pre never gets updated (remains 0), which is technically correct as a degenerate polygon with all collinear points can be considered convex.