Convex Polygon

medium math geometry

Problem

Given the vertices of a polygon in order, return whether it is convex (no internal angle > 180°).

Inputpoints = [[0,0],[0,1],[1,1],[1,0]]

Outputtrue

All cross products have the same sign — convex.

points (x,y ;)

def is_convex(points):
    n = len(points)
    prev = 0
    for i in range(n):
        a, b, c = points[i], points[(i+1) % n], points[(i+2) % n]
        cross = (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
        if cross:
            if cross * prev < 0: return False
            prev = cross
    return True

function isConvex(points) {
  const n = points.length;
  let prev = 0;
  for (let i = 0; i < n; i++) {
    const a = points[i], b = points[(i+1) % n], c = points[(i+2) % n];
    const cross = (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);
    if (cross) {
      if (cross * prev < 0) return false;
      prev = cross;
    }
  }
  return true;
}

class Solution {
    public boolean isConvex(List> points) {
        int n = points.size();
        long prev = 0;
        for (int i = 0; i < n; i++) {
            int[] a = { points.get(i).get(0), points.get(i).get(1) };
            int[] b = { points.get((i+1)%n).get(0), points.get((i+1)%n).get(1) };
            int[] c = { points.get((i+2)%n).get(0), points.get((i+2)%n).get(1) };
            long cross = (long)(b[0]-a[0]) * (c[1]-b[1]) - (long)(b[1]-a[1]) * (c[0]-b[0]);
            if (cross != 0) {
                if (cross * prev < 0) return false;
                prev = cross;
            }
        }
        return true;
    }
}

bool isConvex(vector>& points) {
    int n = points.size();
    long long prev = 0;
    for (int i = 0; i < n; i++) {
        auto& a = points[i];
        auto& b = points[(i+1)%n];
        auto& c = points[(i+2)%n];
        long long cross = (long long)(b[0]-a[0]) * (c[1]-b[1]) - (long long)(b[1]-a[1]) * (c[0]-b[0]);
        if (cross != 0) {
            if (cross * prev < 0) return false;
            prev = cross;
        }
    }
    return true;
}

Explanation

A polygon is convex if it always turns the same way as you walk around its edges. We detect that by checking the sign of the cross product at every corner.

At each vertex we take three consecutive points a, b, c and compute the cross product of edge a→b with edge b→c. A positive value means a left turn, negative means a right turn, and zero means the points are straight (no turn).

We remember the sign of the last non-zero turn in prev. If a new turn has the opposite sign (so cross * prev < 0), the shape bends both ways and is concave, so we return false.

The modulo indexing (i+1) % n and (i+2) % n lets us wrap around the last vertices back to the start, so every corner is checked.

Example: a unit square [[0,0],[0,1],[1,1],[1,0]] turns the same direction at all four corners, so no sign flip ever happens and the answer is true.

Time: O(n) Space: O(1)