分享一个点集求凸包的算法

LL_Zz

1. #include "stdafx.h"
   
2. #include "MyTuBao.h"
   
3. #include"MathUtil.h"
   
4. MyTuBao::MyTuBao()
   
5. {
   
6. }
   
7. 
   
8. MyTuBao::MyTuBao(AcGePoint3dArray arr)
   
9. {
   
10.   this->ptArr = arr;
    
11. }
    
12. 
    
13. 
    
14. MyTuBao::~MyTuBao()
    
15. {
    
16.   ptArr.removeAll();
    
17. 
    
18. }
    
19. 
    
20. void   MyTuBao::GetTuBao(AcGePoint3dArray &pArray)
    
21. {
    
22.   int nums = 0;
    
23.   optimizePointsArray(ptArr);
    
24.   nums = ptArr.length();
    
25.   if (nums > 3) {
    
26.     selectMinPoint(ptArr);//寻找最小的点
    
27.     quickSort(ptArr, 1, nums - 1);//用来根据极角排序点
    
28.     pArray.append(ptArr[0]);
    
29.     pArray.append(ptArr[1]);
    
30.     pArray.append(ptArr[2]);
    
31.     int top = pArray.length() - 1;
    
32.     for (int i = 3; i < nums; i++)
    
33.     {
    
34.       while (xmul(ptArr, pArray[top], pArray[top - 1]) >= 0)  //是否左转，是继续判断，不是，就入栈  
    
35.       {
    
36.         pArray.removeLast();
    
37.         top = pArray.length() - 1;
    
38.       }
    
39.       pArray.append(ptArr);
    
40. 
    
41.       top = pArray.length() - 1;
    
42.     }
    
43. 
    
44.   }
    
45. }
    
46. 
    
47. void MyTuBao::GetRec(AcGePoint3dArray &pArray){
    
48.   selectMinPoint(ptArr);//寻找最小的点
    
49.   int nums = 0;
    
50.   optimizePointsArray(ptArr);
    
51.   nums = ptArr.length();
    
52.   quickSort(ptArr, 1, nums - 1);//用来根据极角排序点
    
53.   pArray = ptArr;
    
54. 
    
55. }
    
56. void MyTuBao::optimizePointsArray(AcGePoint3dArray &points, double tol /*= 1.0E-7*/) {
    
57.   
    
58.   for (int i = points.length() - 1; i > 0; i--)
    
59.   {
    
60.     for (int j = 0; j < i; j++)
    
61.     {
    
62.       if (CMathUtil::IsEqual(points.x, points[j].x, tol) && CMathUtil::IsEqual(points.y, points[j].y, tol))
    
63.       {
    
64.         points.removeAt(i);
    
65.         break;
    
66.       }
    
67.     }
    
68.   }
    
69. }
    
70. 
    
71. long long  MyTuBao::dist(AcGePoint3d p1, AcGePoint3d p2) //两点距离的平方  
    
72. {
    
73.   return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
    
74. }
    
75. 
    
76. bool MyTuBao::cmp1(AcGePoint3d p1, AcGePoint3d p2)   //找到第一个点，返回 true->p1比较小，false->p2比较小
    
77. {
    
78.   if (p1.y == p2.y)
    
79.     return p1.x<p2.x;
    
80.   else
    
81.     return p1.y<p2.y;
    
82. }
    
83. 
    
84. bool MyTuBao::cmp2(AcGePoint3d p1, AcGePoint3d p2, AcGePoint3d pointMin)   //极角排序的比较函数  
    
85. {
    
86.   if (xmul(p1, p2, pointMin)>0)
    
87.     return true; //证明 p1小 选中p1
    
88.   else if (xmul(p1, p2, pointMin) == 0 && dist(p1, pointMin)<dist(p2, pointMin))  //相等的按距离近的  
    
89.     return true; //证明 p1小 选中p1
    
90.   return false;
    
91. }
    
92. 
    
93. double MyTuBao::xmul(AcGePoint3d p1, AcGePoint3d p2, AcGePoint3d  p0)
    
94. {
    
95.   return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    
96. }
    
97. 
    
98. void MyTuBao::selectMinPoint(AcGePoint3dArray &s) {
    
99.   int nums = s.length();
    
100.   int cur = 0;
     
101.   AcGePoint3d Min = s[0];
     
102.   for (int i = 1; i<nums; i++) {
     
103.     if (cmp1(s, Min)) {
     
104.       Min = s;
     
105.       cur = i;
     
106.     }
     
107.   }
     
108.   s[cur] = s[0];
     
109.   s[0] = Min;
     
110.   acutPrintf(L"\n寻找后最小点为x=%f,y=%f", s[0].x, s[0].y);
     
111. }
     
112. 
     
113. void  MyTuBao::quickSort(AcGePoint3dArray &s, int l, int r) {
     
114.   if (l< r)
     
115.   {
     
116.     int i = l, j = r;
     
117.     AcGePoint3d x = s[l];
     
118.     while (i < j)
     
119.     {
     
120.       while (i < j && cmp2(x, s[j], s[0])) // 从右向左找第一个小于x的数
     
121.         j--;
     
122.       if (i < j)
     
123.         s[i++] = s[j];
     
124.       while (i < j && cmp2(s, x, s[0])) // 从左向右找第一个大于等于x的数
     
125.         i++;
     
126.       if (i < j)
     
127.         s[j--] = s;
     
128.     }
     
129.     s = x;
     
130.     quickSort(s, l, i - 1); // 递归调用
     
131.     quickSort(s, i + 1, r);
     
132.   }
     
133. }

#include "stdafx.h"<br /> #include "MyTuBao.h"<br /> #include"MathUtil.h"<br /> MyTuBao::MyTuBao()<br /> {<br /> }<br /> <br /> MyTuBao::MyTuBao(AcGePoint3dArray arr)<br /> {<br />   this->ptArr = arr;<br /> }<br /> <br /> <br /> MyTuBao::~MyTuBao()<br /> {<br />   ptArr.removeAll();<br /> <br /> }<br /> <br /> void   MyTuBao::GetTuBao(AcGePoint3dArray &pArray)<br /> {<br />   int nums = 0;<br />   optimizePointsArray(ptArr);<br />   nums = ptArr.length();<br />   if (nums > 3) {<br />     selectMinPoint(ptArr);//寻找最小的点<br />     quickSort(ptArr, 1, nums - 1);//用来根据极角排序点<br />     pArray.append(ptArr[0]);<br />     pArray.append(ptArr[1]);<br />     pArray.append(ptArr[2]);<br />     int top = pArray.length() - 1;<br />     for (int i = 3; i < nums; i++)<br />     {<br />       while (xmul(ptArr<i>, pArray[top], pArray[top - 1]) >= 0)  //是否左转，是继续判断，不是，就入栈  <br />       {<br />         pArray.removeLast();<br />         top = pArray.length() - 1;<br />       }<br />       pArray.append(ptArr<i>);<br /> <br />       top = pArray.length() - 1;<br />     }<br /> <br />   }<br /> }<br /> <br /> void MyTuBao::GetRec(AcGePoint3dArray &pArray){<br />   selectMinPoint(ptArr);//寻找最小的点<br />   int nums = 0;<br />   optimizePointsArray(ptArr);<br />   nums = ptArr.length();<br />   quickSort(ptArr, 1, nums - 1);//用来根据极角排序点<br />   pArray = ptArr;<br /> <br /> }<br /> void MyTuBao::optimizePointsArray(AcGePoint3dArray &points, double tol /*= 1.0E-7*/) {<br />   <br />   for (int i = points.length() - 1; i > 0; i--)<br />   {<br />     for (int j = 0; j < i; j++)<br />     {<br />       if (CMathUtil::IsEqual(points<i>.x, points[j].x, tol) && CMathUtil::IsEqual(points<i>.y, points[j].y, tol))<br />       {<br />         points.removeAt(i);<br />         break;<br />       }<br />     }<br />   }<br /> }<br /> <br /> long long  MyTuBao::dist(AcGePoint3d p1, AcGePoint3d p2) //两点距离的平方  <br /> {<br />   return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);<br /> }<br /> <br /> bool MyTuBao::cmp1(AcGePoint3d p1, AcGePoint3d p2)   //找到第一个点，返回 true->p1比较小，false->p2比较小<br /> {<br />   if (p1.y == p2.y)<br />     return p1.x<p2.x;<br />   else<br />     return p1.y<p2.y;<br /> }<br /> <br /> bool MyTuBao::cmp2(AcGePoint3d p1, AcGePoint3d p2, AcGePoint3d pointMin)   //极角排序的比较函数  <br /> {<br />   if (xmul(p1, p2, pointMin)>0)<br />     return true; //证明 p1小 选中p1<br />   else if (xmul(p1, p2, pointMin) == 0 && dist(p1, pointMin)<dist(p2, pointMin))  //相等的按距离近的  <br />     return true; //证明 p1小 选中p1<br />   return false;<br /> }<br /> <br /> double MyTuBao::xmul(AcGePoint3d p1, AcGePoint3d p2, AcGePoint3d  p0)<br /> {<br />   return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);<br /> }<br /> <br /> void MyTuBao::selectMinPoint(AcGePoint3dArray &s) {<br />   int nums = s.length();<br />   int cur = 0;<br />   AcGePoint3d Min = s[0];<br />   for (int i = 1; i<nums; i++) {<br />     if (cmp1(s<i>, Min)) {<br />       Min = s<i>;<br />       cur = i;<br />     }<br />   }<br />   s[cur] = s[0];<br />   s[0] = Min;<br />   acutPrintf(L"\n寻找后最小点为x=%f,y=%f", s[0].x, s[0].y);<br /> }<br /> <br /> void  MyTuBao::quickSort(AcGePoint3dArray &s, int l, int r) {<br />   if (l< r)<br />   {<br />     int i = l, j = r;<br />     AcGePoint3d x = s[l];<br />     while (i < j)<br />     {<br />       while (i < j && cmp2(x, s[j], s[0])) // 从右向左找第一个小于x的数<br />         j--;<br />       if (i < j)<br />         s[i++] = s[j];<br />       while (i < j && cmp2(s<i>, x, s[0])) // 从左向右找第一个大于等于x的数<br />         i++;<br />       if (i < j)<br />         s[j--] = s<i>;<br />     }<br />     s<i> = x;<br />     quickSort(s, l, i - 1); // 递归调用<br />     quickSort(s, i + 1, r);<br />   }<br /> }

LL_Zz

#include "stdafx.h"
#include "MyTuBao.h"
#include"MathUtil.h"
MyTuBao::MyTuBao()
{
}

MyTuBao::MyTuBao(AcGePoint3dArray arr)
{
        this->ptArr = arr;
}


MyTuBao::~MyTuBao()
{
        ptArr.removeAll();

}

void   MyTuBao::GetTuBao(AcGePoint3dArray &pArray)
{
        int nums = 0;
        optimizePointsArray(ptArr);
        nums = ptArr.length();
        if (nums > 3) {
                selectMinPoint(ptArr);//寻找最小的点
                quickSort(ptArr, 1, nums - 1);//用来根据极角排序点
                pArray.append(ptArr[0]);
                pArray.append(ptArr[1]);
                pArray.append(ptArr[2]);
                int top = pArray.length() - 1;
                for (int i = 3; i < nums; i++)
                {
                        while (xmul(ptArr[i], pArray[top], pArray[top - 1]) >= 0)  //是否左转，是继续判断，不是，就入栈  
                        {
                                pArray.removeLast();
                                top = pArray.length() - 1;
                        }
                        pArray.append(ptArr[i]);

                        top = pArray.length() - 1;
                }

        }
}

void MyTuBao::GetRec(AcGePoint3dArray &pArray){
        selectMinPoint(ptArr);//寻找最小的点
        int nums = 0;
        optimizePointsArray(ptArr);
        nums = ptArr.length();
        quickSort(ptArr, 1, nums - 1);//用来根据极角排序点
        pArray = ptArr;

}
void MyTuBao::optimizePointsArray(AcGePoint3dArray &points, double tol /*= 1.0E-7*/) {
       
        for (int i = points.length() - 1; i > 0; i--)
        {
                for (int j = 0; j < i; j++)
                {
                        if (CMathUtil::IsEqual(points[i].x, points[j].x, tol) && CMathUtil::IsEqual(points[i].y, points[j].y, tol))
                        {
                                points.removeAt(i);
                                break;
                        }
                }
        }
}

long long  MyTuBao::dist(AcGePoint3d p1, AcGePoint3d p2) //两点距离的平方  
{
        return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

bool MyTuBao::cmp1(AcGePoint3d p1, AcGePoint3d p2)   //找到第一个点，返回 true->p1比较小，false->p2比较小
{
        if (p1.y == p2.y)
                return p1.x<p2.x;
        else
                return p1.y<p2.y;
}

bool MyTuBao::cmp2(AcGePoint3d p1, AcGePoint3d p2, AcGePoint3d pointMin)   //极角排序的比较函数  
{
        if (xmul(p1, p2, pointMin)>0)
                return true; //证明 p1小 选中p1
        else if (xmul(p1, p2, pointMin) == 0 && dist(p1, pointMin)<dist(p2, pointMin))  //相等的按距离近的  
                return true; //证明 p1小 选中p1
        return false;
}

double MyTuBao::xmul(AcGePoint3d p1, AcGePoint3d p2, AcGePoint3d  p0)
{
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

void MyTuBao::selectMinPoint(AcGePoint3dArray &s) {
        int nums = s.length();
        int cur = 0;
        AcGePoint3d Min = s[0];
        for (int i = 1; i<nums; i++) {
                if (cmp1(s[i], Min)) {
                        Min = s[i];
                        cur = i;
                }
        }
        s[cur] = s[0];
        s[0] = Min;
        acutPrintf(L"\n寻找后最小点为x=%f,y=%f", s[0].x, s[0].y);
}

void  MyTuBao::quickSort(AcGePoint3dArray &s, int l, int r) {
        if (l< r)
        {
                int i = l, j = r;
                AcGePoint3d x = s[l];
                while (i < j)
                {
                        while (i < j && cmp2(x, s[j], s[0])) // 从右向左找第一个小于x的数
                                j--;
                        if (i < j)
                                s[i++] = s[j];
                        while (i < j && cmp2(s[i], x, s[0])) // 从左向右找第一个大于等于x的数
                                i++;
                        if (i < j)
                                s[j--] = s[i];
                }
                s[i] = x;
                quickSort(s, l, i - 1); // 递归调用
                quickSort(s, i + 1, r);
        }
}

satan421

MyTuBao 哈哈
论坛搞arx开发的太少了
业余的也就搞搞lisp