Convex Polygon Problem

Problem

Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).

Note:

  1. There are at least 3 and at most 10,000 points.
  2. Coordinates are in the range -10,000 to 10,000.
  3. You may assume the polygon formed by given points is always a simple polygon (Simple polygon definition). In other words, we ensure that exactly two edges intersect at each vertex, and that edges otherwise don’t intersect each other.

Examples

Example 1:

1
2
3

[[0,0],[0,1],[1,1],[1,0]]

Answer: True

Explanation:

Example 2:

1
2
3

[[0,0],[0,10],[10,10],[10,0],[5,5]]

Answer: False

Explanation:

Solution

Method 1 – Cross Product Sign Consistency

Intuition

A polygon is convex if all its internal angles are less than 180 degrees. This is equivalent to saying that as we walk along the edges, the cross product of each pair of consecutive edges should have the same sign (all left turns or all right turns).

Approach

  1. For each triplet of consecutive points, compute the cross product of the vectors formed by these points.
  2. Track the sign of the first non-zero cross product.
  3. If any subsequent non-zero cross product has a different sign, the polygon is not convex.
  4. If all non-zero cross products have the same sign, the polygon is convex.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool isConvex(vector<vector<int>>& p) {
        int n = p.size(), sign = 0;
        for (int i = 0; i < n; ++i) {
            int dx1 = p[(i+1)%n][0] - p[i][0];
            int dy1 = p[(i+1)%n][1] - p[i][1];
            int dx2 = p[(i+2)%n][0] - p[(i+1)%n][0];
            int dy2 = p[(i+2)%n][1] - p[(i+1)%n][1];
            int cross = dx1 * dy2 - dy1 * dx2;
            if (cross != 0) {
                if (sign == 0) sign = cross > 0 ? 1 : -1;
                else if ((cross > 0 ? 1 : -1) != sign) return false;
            }
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func isConvex(p [][]int) bool {
    n, sign := len(p), 0
    for i := 0; i < n; i++ {
        dx1 := p[(i+1)%n][0] - p[i][0]
        dy1 := p[(i+1)%n][1] - p[i][1]
        dx2 := p[(i+2)%n][0] - p[(i+1)%n][0]
        dy2 := p[(i+2)%n][1] - p[(i+1)%n][1]
        cross := dx1*dy2 - dy1*dx2
        if cross != 0 {
            if sign == 0 {
                if cross > 0 { sign = 1 } else { sign = -1 }
            } else if (cross > 0 && sign < 0) || (cross < 0 && sign > 0) {
                return false
            }
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public boolean isConvex(int[][] p) {
        int n = p.length, sign = 0;
        for (int i = 0; i < n; i++) {
            int dx1 = p[(i+1)%n][0] - p[i][0];
            int dy1 = p[(i+1)%n][1] - p[i][1];
            int dx2 = p[(i+2)%n][0] - p[(i+1)%n][0];
            int dy2 = p[(i+2)%n][1] - p[(i+1)%n][1];
            int cross = dx1 * dy2 - dy1 * dx2;
            if (cross != 0) {
                if (sign == 0) sign = cross > 0 ? 1 : -1;
                else if ((cross > 0 ? 1 : -1) != sign) return false;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun isConvex(p: Array<IntArray>): Boolean {
        val n = p.size
        var sign = 0
        for (i in 0 until n) {
            val dx1 = p[(i+1)%n][0] - p[i][0]
            val dy1 = p[(i+1)%n][1] - p[i][1]
            val dx2 = p[(i+2)%n][0] - p[(i+1)%n][0]
            val dy2 = p[(i+2)%n][1] - p[(i+1)%n][1]
            val cross = dx1 * dy2 - dy1 * dx2
            if (cross != 0) {
                if (sign == 0) sign = if (cross > 0) 1 else -1
                else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) return false
            }
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def isConvex(self, p: list[list[int]]) -> bool:
        n, sign = len(p), 0
        for i in range(n):
            dx1 = p[(i+1)%n][0] - p[i][0]
            dy1 = p[(i+1)%n][1] - p[i][1]
            dx2 = p[(i+2)%n][0] - p[(i+1)%n][0]
            dy2 = p[(i+2)%n][1] - p[(i+1)%n][1]
            cross = dx1 * dy2 - dy1 * dx2
            if cross != 0:
                if sign == 0:
                    sign = 1 if cross > 0 else -1
                elif (cross > 0 and sign < 0) or (cross < 0 and sign > 0):
                    return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn is_convex(p: Vec<Vec<i32>>) -> bool {
        let n = p.len();
        let mut sign = 0;
        for i in 0..n {
            let dx1 = p[(i+1)%n][0] - p[i][0];
            let dy1 = p[(i+1)%n][1] - p[i][1];
            let dx2 = p[(i+2)%n][0] - p[(i+1)%n][0];
            let dy2 = p[(i+2)%n][1] - p[(i+1)%n][1];
            let cross = dx1 * dy2 - dy1 * dx2;
            if cross != 0 {
                if sign == 0 {
                    sign = if cross > 0 { 1 } else { -1 };
                } else if (cross > 0 && sign < 0) || (cross < 0 && sign > 0) {
                    return false;
                }
            }
        }
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    isConvex(p: number[][]): boolean {
        let n = p.length, sign = 0;
        for (let i = 0; i < n; i++) {
            let dx1 = p[(i+1)%n][0] - p[i][0];
            let dy1 = p[(i+1)%n][1] - p[i][1];
            let dx2 = p[(i+2)%n][0] - p[(i+1)%n][0];
            let dy2 = p[(i+2)%n][1] - p[(i+1)%n][1];
            let cross = dx1 * dy2 - dy1 * dx2;
            if (cross !== 0) {
                if (sign === 0) sign = cross > 0 ? 1 : -1;
                else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) return false;
            }
        }
        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of points.
  • 🧺 Space complexity: O(1), only constant extra space is used.