Leetcode 469. Convex Polygon

Problem Explanation

This problem is about checking whether a given simple polygon is convex or not. A simple polygon is a polygon in which no two edges intersect each other except at their endpoints (vertices). A convex polygon is a simple polygon in which no line segment between two points on the boundary ever goes outside the polygon.

The list of points given in the problem forms a polygon when joined sequentially. The task is to check whether this polygon is convex or not.

For example, consider the list of points [[0,0],[0,1],[1,1],[1,0]]. When these points are joined sequentially, they form a square which is a convex polygon. Therefore, the function should return True.

On the other hand, if the points are [[0,0],[0,10],[10,10],[10,0],[5,5]], they form a polygon with a inward dent at the point [5,5]. This is not a convex polygon hence the function should return False.

Solution Approach

The problem can be solved by calculating the cross product of vectors. For each three consecutive points, we calculate the cross product of the vectors joining these points. If the cross product for all three consecutive points has the same sign (i.e., all positive or all negative), then the polygon is convex, else it is not.

A cross product of two vectors is a vector that is perpendicular to the plane of the original vectors. Its direction is according to the right-hand rule (curling from the first vector to the second vector) and its magnitude is equal to the area of parallelogram spanned by the original vectors. The sign of the cross product can be used to determine the relative orientation of the original vectors.

In this solution, we start with the first three points and calculate the cross product. We continue this for all sets of such three consecutive points. If we find a set where the sign of the cross product differs from the initial one, we return False. If we go through all the points without finding a different sign, we return True.

The solution implements this logic in a function isConvex which takes a list of points as input and returns a boolean indicating whether the polygon is convex or not.

Code Explanation

The getCross function calculates the cross product of vectors. For each set of three consecutive points, we calculate the cross product using this function. Initially, sign is set to 0. The first time we get a cross product that is not zero, we set that as our sign. From then on, we check whether all subsequent cross products have the same sign or not. If they do, we continue. If not, we return False. If we reach the end without finding conflicting signs, we return True.

This way of checking the cross product ensures that we are checking the orientation of each set of three points, whether they turn right or left. In a convex polygon, all turns should be in the same direction.

Python Solution

1
2python
3import numpy as np
4
5class Solution:
6    def isConvex(self, points: list[list[int]]) -> bool:
7        n = len(points)
8        sign = 0
9
10        for i in range(n):
11            p0, p1, p2 = points[i], points[(i + 1) % n], points[(i + 2) % n]
12            dx1, dy1 = p1[0] - p0[0], p1[1] - p0[1]
13            dx2, dy2 = p2[0] - p1[0], p2[1] - p1[1]
14            cross = np.sign(dx1 * dy2 - dx2 * dy1)
15
16            if cross == 0:
17                continue
18
19            if sign == 0:
20                sign = cross
21            elif sign != cross:
22                return False
23
24        return True

Java Solution

1
2java
3import java.util.List;
4
5public class Solution {
6    public boolean isConvex(List < List < Integer >> points) {
7        int len = points.size(), prev = 0, cur;
8
9        for (int i = 0; i < len; i++) {
10            cur = crossProduct(points.get((i + 2) % len) - points.get((i + 1) % len),
11                    points.get((i + 1) % len) - points.get(i));
12            if (cur == 0)
13                continue;
14            if (cur > 0 && prev < 0 || cur < 0 && prev > 0)
15                return false;
16            else if (prev == 0)
17                prev = cur;
18        }
19        return true;
20    }
21
22    public int crossProduct(List < Integer > A, List < Integer > B) {
23        return A.get(0) * B.get(1) - A.get(1) * B.get(0);
24    }
25}

JavaScript Solution

1
2javascript
3class Solution {
4  isConvex(points) {
5    let sign = 0;
6    const len = points.length;
7
8    for(let i = 0; i < len; i++){
9      let p0 = points[i],
10      p1 = points[(i+1)%len], 
11      p2 = points[(i+2)%len];
12      
13      let dx1 = p1[0] - p0[0];
14      let dy1 = p1[1] - p0[1];
15      let dx2 = p2[0] - p1[0];
16      let dy2 = p2[1] - p1[1];
17      
18      let cross = Math.sign(dx1 * dy2 - dx2 * dy1);
19      
20      if(cross===0) continue;
21      
22      if(sign === 0){
23        sign = cross;
24      } else if (sign !== cross){
25        return false;
26      }
27    }
28    return true;
29  }
30}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isConvex(vector<vector<int>>& points) {
6        long long n = points.size(), prev = 0, cur;
7
8        for (int i = 0; i < n; i++) {
9            cur = crossProduct(subtract(points[(i+2)%n], points[(i+1)%n]),
10                               subtract(points[(i+1)%n], points[i]));
11
12            if (cur == 0) continue;
13            if (cur > 0 && prev < 0 || cur < 0 && prev > 0) return false;
14            else if (prev == 0) prev = cur;
15        }
16
17        return true;
18    }
19
20    vector<int> subtract(vector<int>& A, vector<int>& B) {
21        return {A[0] - B[0], A[1] - B[1]};
22    }
23
24    long long crossProduct(vector<int>& A, vector<int>& B) {
25        return (long long)A[0] * B[1] - (long long)A[1] * B[0];
26    }
27};

C# Solution

1
2c#
3using System.Collections.Generic;
4
5public class Solution {
6    public bool IsConvex(List<IList<int>> points) {
7        var length = points.Count;
8        long prev = 0;
9        for (var i = 0; i < length; i++) {
10            var dp = new long[] { points[(i+1) % length][0] - points[i][0], points[(i+1) % length][1] - points[i][1] };
11            var dn = new long[] { points[(i+2) % length][0] - points[(i+1) % length][0], points[(i+2) % length][1] - points[(i+1) % length][1] };
12            long cur = dp[0]*dn[1] - dp[1]*dn[0];
13            if (cur == 0) continue;
14            if (cur > 0 && prev < 0 || cur < 0 && prev > 0) return false;
15            else if (prev == 0) prev = cur;
16        }
17        return true;
18    }
19}

Conclusion

In this article, we explained how to determine whether a given simple polygon is convex, using a function that takes a list of points as input and returns a boolean indicating whether the polygon is convex or not.

This was done by calculating the cross product of vectors, for each three consecutive points, and checking whether all such cross products have the same sign (i.e., all positive or all negative). If the cross product for all three consecutive points has the same sign, then the polygon is considered convex. If there's a deviation in the sign of the cross product, it means the polygon is not convex.

We provided code solutions in six different programming languages: Python, Java, JavaScript, C++, and C#. These solutions can be integrated into larger projects, or used as standalone solutions to determine whether a polygon is convex.