469. Convex Polygon
Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 37.6%
Problem Breakdown
We are given a list of vertices representing a simple polygon in order. Our goal is to determine if this shape is convex. A polygon is convex if all its interior angles are less than or equal to 180 degrees, meaning no “indentations” exist where the boundary turns inward relative to the traversal direction.
Inputs:
points: List of[x, y]coordinate pairs (integers).- Constraints: , coordinates between -10,000 and 10,000. The polygon is guaranteed to be simple (no self-intersections), so we don’t need to validate topology or sort points; the input order defines the perimeter traversal.
Outputs:
Trueif convex,Falseotherwise.
Implicit Constraints & Edge Cases:
- Wrap-around: Since it’s a polygon, the last point connects back to the first. We must handle index as index 0.
- Collinear Points: Three consecutive points lying on a straight line result in a cross product of zero. Geometrically, this is still considered convex (an angle of exactly 180 degrees). However, we only care if signs flip from positive to negative or vice versa; zeros are neutral and do not break convexity unless they sandwich non-zero turns with different directions.
- Overflow: With coordinates up to , the cross product can reach roughly . This fits comfortably within a standard 32-bit integer, and Python handles arbitrary precision integers automatically anyway.
Intuition
A brute-force approach might try to calculate every interior angle using trigonometry (atan2) or check if the diagonal between non-adjacent vertices lies inside the polygon. Calculating angles is computationally expensive ( with potential floating-point errors), and checking diagonals for all pairs becomes , which is too slow given .
The key insight relies on vector geometry: When traversing a convex polygon boundary in order (clockwise or counter-clockwise), the “turn” at every vertex must be consistent. You either always turn left or always turn right. If you ever switch from turning left to turning right (or vice versa) without passing through 180 degrees, there is an indentation (concavity).
We can determine the direction of a turn using the 2D Cross Product of two consecutive edge vectors:
- Let and .
- The cross product .
- If , it’s a left turn.
- If , it’s a right turn.
- If , points are collinear (straight line).
For the polygon to be convex, all non-zero cross products must share the same sign. We iterate through every vertex and check this condition.
Approach
- Initialize a variable
signto track the direction of turns encountered so far. Since we don’t know if it’s clockwise or counter-clockwise yet, we can set an initial state based on the first valid turn (or handle zeros carefully). A robust way is to iterate and updateprev_sign. - Iterate through each vertex from 0 to . We need three consecutive points: current (), next (), and after-next (). Since the polygon wraps around, indices are calculated modulo .
- Compute vectors and .
- Calculate cross product:
cp = u_x * v_y - u_y * v_x. - Determine the sign of this cross product (positive, negative, or zero).
- If we encounter a non-zero value and it differs from our previously recorded turn direction (
prev_sign), returnFalse. - Update
prev_signto match current if valid. Handle zeros by ignoring them for sign comparison but updating the state only when a definitive left/right turn occurs (or simply track that all previous were 0). A simpler logic: store the first non-zero cross product’s sign as reference, then compare subsequent ones against it. - If loop completes without returning
False, returnTrue.
Complexity Analysis
- Time Complexity: where is the number of points. We iterate through the list exactly once performing constant-time arithmetic operations per vertex.
- Space Complexity: . We only store a few variables for coordinates and cross product results; we do not need extra data structures proportional to input size (no sorting or recursion).
Solution
def isConvexPolygon(points):
n = len(points)
# Helper lambda to get vector components between two points
def vec(p1, p2):
return [p2[0] - p1[0], p2[1] - p1[1]]
prev_sign = 0
for i in range(n):
# Indices wrap around using modulo n
curr_idx = (i + 1) % n
next_idx = (i + 2) % n
u_x, u_y = points[curr_idx][0] - points[i][0], \
points[curr_idx][1] - points[i][1]
v_x, v_y = points[next_idx][0] - points[curr_idx][0], \
points[next_idx][1] - points[curr_idx][1]
# Cross product of vectors u and v: (u x v) in 2D is scalar z-component
cross_product = u_x * v_y - u_y * v_x
current_sign = cross_product if cross_product != 0 else 0
# If we have a definitive turn direction established, check consistency.
# Note: We must ensure prev_sign isn't still the initial 'neutral' state
# before comparing against zeros to avoid false negatives on straight edges.
if current_sign == 0:
continue
if prev_sign != 0 and (current_sign > 0) != (prev_sign > 0):
return False
prev_sign = current_sign
return True
Edge Cases Handled
- Collinear Vertices: If three consecutive points are collinear, the cross product is zero. The code skips updating
prev_signor comparing signs when it’s zero, effectively treating straight edges as valid convex continuations rather than concavities. - Wrap-around Logic: Using
(i + 1) % nand(i + 2) % nensures the last vertex connects correctly to the first two vertices in a circular buffer manner without needing explicit boundary checks inside the loop logic. - Negative Coordinates: The cross product formula relies on differences, so negative coordinates are handled naturally by standard integer arithmetic (Python handles large integers automatically).
- Minimum Points (): The loop runs correctly for . With exactly 3 points forming a triangle, the logic holds as long as they don’t overlap or form a straight line.