Convex Polygon

A polygon is convex iff all consecutive edge cross products have the same sign.

Medium
Time O(n) Space O(1)
LeetCode
4 min read
geometry math cross-product

Problem#

Given the vertices of a simple polygon in order, return true iff the polygon is convex.

Examples#

  • [[0,0],[0,5],[5,5],[5,0]]true (square).
  • [[0,0],[0,10],[10,10],[10,0],[5,5]]false.

Constraints#

  • 3 <= points.length <= 10^4.

Approach#

For each triple of consecutive vertices, compute the cross product of the two edges meeting at the middle vertex. The polygon is convex iff all non-zero cross products share a sign (no left/right turn mixing).

Solution#

Convex Polygon
class Solution {
public:
bool isConvex(vector<vector<int>>& points) {
int n = points.size(), sign = 0;
for (int i = 0; i < n; ++i) {
long long dx1 = points[(i + 1) % n][0] - points[i][0];
long long dy1 = points[(i + 1) % n][1] - points[i][1];
long long dx2 = points[(i + 2) % n][0] - points[(i + 1) % n][0];
long long dy2 = points[(i + 2) % n][1] - points[(i + 1) % n][1];
long long c = dx1 * dy2 - dy1 * dx2;
if (c != 0) {
int s = (c > 0) ? 1 : -1;
if (sign == 0) sign = s;
else if (sign != s) return false;
}
}
return true;
}
};

Editorial#

Cross product sign equals turn direction: positive = counterclockwise, negative = clockwise. A convex polygon has a single turn direction at every vertex (collinear triples are tolerated). Use long long to avoid overflow when coords approach 10^4.

Complexity#

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

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.