实现计算凸包的函数c++-ok
为了实现计算凸包的函数，我们需要确保 cross 函数和比较函数 cmp 都已经定义好。这里我们使用 AcGePoint2d 类型，它是 AutoCAD ObjectARX 库中的一个点类，包含 x 和 y 坐标。
首先，我们需要定义 cross 函数来计算两个向量的叉积。然后，我们需要一个比较函数 cmp 来按照字典序对点进行排序（即先按 x 坐标升序排列，如果 x 相同，则按 y 坐标升序排列）。
#include <vector>
#include <algorithm>
#include <acge.h> // 包含 AcGePoint2d 的头文件
// 比较函数，用于按字典序排序
bool cmp(const AcGePoint2d& p1, const AcGePoint2d& p2) {
return (p1.x() < p2.x()) || (p1.x() == p2.x() && p1.y() < p2.y());
}
// 计算两个向量的叉积
double cross(const AcGePoint2d& O, const AcGePoint2d& A, const AcGePoint2d& B) {
return (A.x() - O.x()) * (B.y() - O.y()) - (A.y() - O.y()) * (B.x() - O.x());
}
// 计算凸包
std::vector<AcGePoint2d> convexhull(const std::vector<AcGePoint2d>& points) {
std::vector<AcGePoint2d> result;
if (points.size() < 3)
return result;
std::vector<AcGePoint2d> tmp_points = points;
// 首先将所有点按照字典序排序
std::sort(tmp_points.begin(), tmp_points.end(), cmp);
// 上凸包
for (const auto& point : tmp_points) {
while (result.size() > 1 && cross(result, result.back(), point) <= 0) {
result.pop_back();
}
result.push_back(point);
}
// 下凸包
int t = result.size() + 1; // 注意这里的+1是为了区分上下凸包
for (int i = tmp_points.size() - 2; i >= 0; --i) {
while (result.size() > t && cross(result, result.back(), tmp_points) <= 0) {
result.pop_back();
}
result.push_back(tmp_points);
}
// 删除最后一个重复点
result.pop_back();
return result;
}
页:
[1]