C++ 中的凸多边形
c++server side programmingprogramming
假设我们有一个点列表，这些点按顺序连接后会形成一个多边形，我们必须确定这个多边形是否是凸多边形(凸多边形定义)。我们必须记住，至少有 3 个点，最多有 10,000 个点。坐标范围在 -10,000 到 10,000 之间。
我们可以假设由给定点形成的多边形始终是一个简单的多边形，换句话说，我们确保每个顶点处恰好有两条边相交，否则边不会相互相交。因此，如果输入如下:[[0,0],[0,1],[1,1],[1,0]]，则它是凸的，因此返回值将为 true。
为了解决这个问题，我们将遵循以下步骤 −
定义一个方法 calc()，它将采用 ax、ay、bx、by、cx、cy，它将按如下方式工作 −
BAx := ax – bx, BAy := ay – by, BCx := cx – bx, BCy := cy - by
从主要方法执行以下操作
neg := false 和 pos := false，n := 点数组的大小
对于 i 在 0 到 n – 1 范围内
a := i，b := (i + 1) mod n 和 c := (i + 2) mod n
cross_prod := calc(p[a, 0], p[a, 1], p[b, 0], p[b, 1], p[c, 0], p[c, 1])
if cross_prod < 0，则 neg := true，否则当 cross_prod > 0 时，则 pos := true
如果 neg 和 pos 为真，则返回 false
return true
示例 (C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isConvex(vector<vector<int>>& points) {
bool neg = false;
bool pos = false;
int n = points.size();
for(int i = 0; i < n; i++){
int a = i;
int b = (i + 1) % n;
int c = (i + 2) % n;
int crossProduct = calc(points[a][0], points[a][1], points[b][0], points[b][1], points[c][0], points[c][1]);
if(crossProduct < 0) neg = true;
else if(crossProduct > 0) pos = true;
if(neg && pos) return false;
}
return true;
}
int calc(int ax, int ay, int bx, int by, int cx, int cy){
int BAx = ax - bx;
int BAy = ay - by;
int BCx = cx - bx;
int BCy = cy - by;
return (BAx * BCy - BAy * BCx);
}
};
main(){
vector<vector<int>> v = {{0,0},{0,1},{1,1},{1,0}};
Solution ob;
cout << (ob.isConvex(v));
}
输入
[[0,0],[0,1],[1,1],[1,0]]
输出
1
