实现计算凸包的函数c++-ok

admin

为了实现计算凸包的函数，我们需要确保 cross 函数和比较函数 cmp 都已经定义好。这里我们使用 AcGePoint2d 类型，它是 AutoCAD ObjectARX 库中的一个点类，包含 x 和 y 坐标。

首先，我们需要定义 cross 函数来计算两个向量的叉积。然后，我们需要一个比较函数 cmp 来按照字典序对点进行排序（即先按 x 坐标升序排列，如果 x 相同，则按 y 坐标升序排列）。

1. #include <vector>
2. #include <algorithm>
3. #include <acge.h> // 包含 AcGePoint2d 的头文件
5. // 比较函数，用于按字典序排序
6. bool cmp(const AcGePoint2d& p1, const AcGePoint2d& p2) {
7.     return (p1.x() < p2.x()) || (p1.x() == p2.x() && p1.y() < p2.y());
8. }
10. // 计算两个向量的叉积
11. double cross(const AcGePoint2d& O, const AcGePoint2d& A, const AcGePoint2d& B) {
12.     return (A.x() - O.x()) * (B.y() - O.y()) - (A.y() - O.y()) * (B.x() - O.x());
13. }
15. // 计算凸包
16. std::vector<AcGePoint2d> convexhull(const std::vector<AcGePoint2d>& points) {
17.     std::vector<AcGePoint2d> result;
18.    
19.     if (points.size() < 3)
20.         return result;
21.    
22.     std::vector<AcGePoint2d> tmp_points = points;
23.     // 首先将所有点按照字典序排序
24.     std::sort(tmp_points.begin(), tmp_points.end(), cmp);
25.    
26.     // 上凸包
27.     for (const auto& point : tmp_points) {
28.         while (result.size() > 1 && cross(result[result.size()-2], result.back(), point) <= 0) {
29.             result.pop_back();
30.         }
31.         result.push_back(point);
32.     }
33.    
34.     // 下凸包
35.     int t = result.size() + 1; // 注意这里的+1是为了区分上下凸包
36.     for (int i = tmp_points.size() - 2; i >= 0; --i) {
37.         while (result.size() > t && cross(result[result.size()-2], result.back(), tmp_points[i]) <= 0) {
38.             result.pop_back();
39.         }
40.         result.push_back(tmp_points[i]);
41.     }
42.    
43.     // 删除最后一个重复点
44.     result.pop_back();
45.    
46.     return result;
47. }

复制代码