实现计算凸包的函数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 的头文件
   
4. 
   
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. }
   
9. 
   
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. }
    
14. 
    
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. }

复制代码