用c++实现已知直角坐标系中的n个点,返回这些点的边界点连线的多边形
时间: 2023-11-28 18:51:01 浏览: 210
这个问题可以使用凸包算法来解决。凸包是一个用线段连接边界点的多边形,这个算法可以在几何学和计算几何中广泛应用。
以下是使用 C++ 实现的 Graham 扫描算法的伪代码,该算法可以在 O(nlogn) 的时间内解决问题:
struct Point {
int x, y;
};
bool cmp(Point a, Point b) {
if (a.x != b.x) {
return a.x < b.x;
} else {
return a.y < b.y;
}
}
bool ccw(Point a, Point b, Point c) {
return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x);
}
vector<Point> convex_hull(vector<Point>& points) {
int n = points.size();
sort(points.begin(), points.end(), cmp);
vector<Point> hull;
for (int i = 0; i < n; i++) {
while (hull.size() >= 2 && !ccw(hull[hull.size() - 2], hull[hull.size() - 1], points[i])) {
hull.pop_back();
}
hull.push_back(points[i]);
}
int t = hull.size() + 1;
for (int i = n - 2; i >= 0; i--) {
while (hull.size() >= t && !ccw(hull[hull.size() - 2], hull[hull.size() - 1], points[i])) {
hull.pop_back();
}
hull.push_back(points[i]);
}
hull.pop_back();
return hull;
}
该算法首先按照 x 坐标进行排序,然后将点插入到凸包中。在每个新点插入后,检查是否需要删除凸包中的点以保持凸包的性质。这是通过检查新点是否在当前凸包的右侧来完成的。在最后,我们还需要删除重复的点。
使用该函数,您可以将点存储在一个 std::vector<Point> 中,并将返回的凸包存储在另一个 std::vector<Point> 中。
相关推荐












