Convex Polygon
A polygon is convex iff all consecutive edge cross products have the same sign.
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#
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; }};func isConvex(points [][]int) bool { n := len(points) sign := 0 for i := 0; i < n; i++ { dx1 := int64(points[(i+1)%n][0] - points[i][0]) dy1 := int64(points[(i+1)%n][1] - points[i][1]) dx2 := int64(points[(i+2)%n][0] - points[(i+1)%n][0]) dy2 := int64(points[(i+2)%n][1] - points[(i+1)%n][1]) c := dx1*dy2 - dy1*dx2 if c != 0 { s := 1 if c < 0 { s = -1 } if sign == 0 { sign = s } else if sign != s { return false } } } return true}from typing import List
class Solution: def isConvex(self, points: List[List[int]]) -> bool: n = len(points) sign = 0 for i in range(n): x0, y0 = points[i] x1, y1 = points[(i + 1) % n] x2, y2 = points[(i + 2) % n] dx1, dy1 = x1 - x0, y1 - y0 dx2, dy2 = x2 - x1, y2 - y1 c = dx1 * dy2 - dy1 * dx2 if c != 0: s = 1 if c > 0 else -1 if sign == 0: sign = s elif sign != s: return False return Truefunction isConvex(points) { const n = points.length; let sign = 0; for (let i = 0; i < n; i++) { const [x0, y0] = points[i]; const [x1, y1] = points[(i + 1) % n]; const [x2, y2] = points[(i + 2) % n]; const dx1 = x1 - x0, dy1 = y1 - y0; const dx2 = x2 - x1, dy2 = y2 - y1; const c = dx1 * dy2 - dy1 * dx2; if (c !== 0) { const s = c > 0 ? 1 : -1; if (sign === 0) sign = s; else if (sign !== s) return false; } } return true;}class Solution { public boolean isConvex(List<List<Integer>> points) { int n = points.size(), sign = 0; for (int i = 0; i < n; i++) { long dx1 = points.get((i + 1) % n).get(0) - points.get(i).get(0); long dy1 = points.get((i + 1) % n).get(1) - points.get(i).get(1); long dx2 = points.get((i + 2) % n).get(0) - points.get((i + 1) % n).get(0); long dy2 = points.get((i + 2) % n).get(1) - points.get((i + 1) % n).get(1); 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; }}function isConvex(points: number[][]): boolean { const n = points.length; let sign = 0; for (let i = 0; i < n; i++) { const [x0, y0] = points[i]; const [x1, y1] = points[(i + 1) % n]; const [x2, y2] = points[(i + 2) % n]; const dx1 = x1 - x0, dy1 = y1 - y0; const dx2 = x2 - x1, dy2 = y2 - y1; const c = dx1 * dy2 - dy1 * dx2; if (c !== 0) { const 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#
Related#