Problem Description

Given a list of points in the 2D plane represented by their coordinates points, determine if these points form a convex polygon when connected in order. The polygon is considered convex if all its interior angles are less than 180 degrees, or equivalently, if the polygon always turns in the same direction as you traverse its vertices in order.

• The input is an array points where points[i] = [xi, yi] represents the coordinates of the ith point.
• There are at least 3 points.
• Points are given in order, i.e., connecting them in sequence forms the polygon.
• You must return True if the polygon is convex, otherwise False.
• Do not reorder or reuse points.

Thought Process

To determine if a polygon is convex, we need to check that as we move around the polygon, the turns between consecutive edges are always in the same direction (either all left or all right). If at any point the direction of the turn changes, the polygon is not convex.

A brute-force approach would be to check the angle at every vertex, but calculating angles is unnecessary. Instead, we can use the cross product of vectors formed by consecutive triplets of points. The sign of the cross product tells us the direction of the turn:

• If the cross product is positive, the turn is counterclockwise (left turn).
• If the cross product is negative, the turn is clockwise (right turn).
• If the cross product is zero, the points are colinear.

The key insight is that for a convex polygon, the sign of the cross product should not change as we move from one vertex to the next. This leads us away from brute force and toward a simple, efficient check using cross products.

Solution Approach

Let's break down the solution step-by-step:

1. Iterate through each set of three consecutive points:
   • For each triplet (A, B, C), compute the cross product of vectors AB and BC.
   • Since the polygon is closed, use modulo arithmetic to wrap around at the end.
2. Determine the sign of the first non-zero cross product:
   • This establishes the "direction" of the polygon (clockwise or counterclockwise).
3. Check all other cross products:
   • If any cross product has a different sign than the first non-zero one, the polygon is not convex.
4. Return the result:
   • If all cross products (ignoring zeros) have the same sign, return True; otherwise, return False.

We use the cross product because it is simple to compute (just integer arithmetic) and directly tells us about the orientation of the turn at each vertex.

Example Walkthrough

Let's consider the following points forming a polygon:

    points = [[0,0], [0,1], [1,1], [1,0]]
  

• These points form a square, which is convex.
• Let's compute the cross product at each vertex:
• At (0,0):
  • Prev: (1,0), Curr: (0,0), Next: (0,1)
  • Vectors: (0,0)-(1,0) = (-1,0), (0,1)-(0,0) = (0,1)
  • Cross product: (-1,0) x (0,1) = -1*1 - 0*0 = -1
• At (0,1):
  • Prev: (0,0), Curr: (0,1), Next: (1,1)
  • Vectors: (0,1)-(0,0) = (0,1), (1,1)-(0,1) = (1,0)
  • Cross product: (0,1) x (1,0) = 0*0 - 1*1 = -1
• At (1,1):
  • Prev: (0,1), Curr: (1,1), Next: (1,0)
  • Vectors: (1,1)-(0,1) = (1,0), (1,0)-(1,1) = (0,-1)
  • Cross product: (1,0) x (0,-1) = 1*-1 - 0*0 = -1
• At (1,0):
  • Prev: (1,1), Curr: (1,0), Next: (0,0)
  • Vectors: (1,0)-(1,1) = (0,-1), (0,0)-(1,0) = (-1,0)
  • Cross product: (0,-1) x (-1,0) = 0*0 - (-1)*-1 = -1
• All cross products are negative, so the polygon is convex. The function returns True.

Time and Space Complexity

• Brute-force approach:
  • Checking all angles using trigonometry would require O(n) time per angle, for n angles, giving O(n^2) time complexity.
  • Space complexity is O(1) since we only need a few variables.
• Optimized cross-product approach:
  • We iterate through all n vertices once, so the time complexity is O(n).
  • Space complexity remains O(1), as we only use a constant number of variables.

Summary

By leveraging the geometric property that a convex polygon's edges always turn in the same direction, we can efficiently determine convexity using the cross product of vectors. This avoids heavy computations and checks the entire polygon in linear time. The elegance of the solution lies in translating a geometric question into a series of simple arithmetic checks, making it both efficient and easy to implement.

Code Implementation

class Solution:
    def isConvex(self, points):
        def cross(o, a, b):
            return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
        
        n = len(points)
        prev = 0
        for i in range(n):
            o = points[i]
            a = points[(i + 1) % n]
            b = points[(i + 2) % n]
            cp = cross(o, a, b)
            if cp != 0:
                if prev == 0:
                    prev = cp
                elif cp * prev < 0:
                    return False
        return True
      

class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        int n = points.size();
        int prev = 0;
        for (int i = 0; i < n; ++i) {
            vector<int>& o = points[i];
            vector<int>& a = points[(i + 1) % n];
            vector<int>& b = points[(i + 2) % n];
            int cp = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
            if (cp != 0) {
                if (prev == 0)
                    prev = cp;
                else if (cp * prev < 0)
                    return false;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        int n = points.size();
        int prev = 0;
        for (int i = 0; i < n; ++i) {
            List<Integer> o = points.get(i);
            List<Integer> a = points.get((i + 1) % n);
            List<Integer> b = points.get((i + 2) % n);
            int cp = (a.get(0) - o.get(0)) * (b.get(1) - o.get(1)) - (a.get(1) - o.get(1)) * (b.get(0) - o.get(0));
            if (cp != 0) {
                if (prev == 0)
                    prev = cp;
                else if (cp * prev < 0)
                    return false;
            }
        }
        return true;
    }
}
      

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