快速凸包演算法
Ⅰ 離散點外包凸多邊形生成演算法（C#或者C++），要有詳細代碼和說明，最好有可運行的樣常式序好的另外加分，急
find&&find_if
臨時對象——構造函數的調用.根據若干個離散點創建最大外包凸多邊形圖形演算法
//卷包裹法---創建最大外包凸多邊形
//stdafx.h
#define PI 3.1415926
#define NULL 0
#define LEN sizeof(struct XYpoint)
long pointSum;
struct XYpoint
{
double x;
double y;
struct XYpoint *next;
};
XYpoint *creat(void);
struct XYpoint *insert(struct XYpoint *head2,struct XYpoint *p);
struct XYpoint *del(struct XYpoint *head,struct XYpoint *p);
struct XYpoint *miny(struct XYpoint *head);
double angle(struct XYpoint *a,struct XYpoint *b,struct XYpoint *c);
double dis(struct XYpoint *a,struct XYpoint *b);
struct XYpoint *tank( struct XYpoint *head ,struct XYpoint *head2);
struct XYpoint *convexHull( struct XYpoint *head ,struct XYpoint *head2);
void print(struct XYpoint *head2);
//stdafx.cpp
#include "stdafx.h"
#include <math.h>
#include <vector>
//using namespace std;
struct XYpoint *creat(void)
{
struct XYpoint *head;
struct XYpoint *p1,*p2;
FILE *fp;
if((fp=fopen("in_put.txt","r"))==NULL)
{
printf("can not open the file\n");
exit(0);
}
pointSum=0;
p1=p2=(struct XYpoint *)malloc(LEN);
fscanf(fp,"%lf,%lf",&p1->x,&p1->y);
head=NULL;
while(!feof(fp))
{
pointSum=pointSum+1;
if(pointSum==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(struct XYpoint *)malloc(LEN);
fscanf(fp,"%lf,%lf",&p1->x,&p1->y);
}
p2->next=NULL;
fclose(fp);
return(head);
}
struct XYpoint *insert(struct XYpoint *head2,struct XYpoint *p)
{
struct XYpoint *p1,*p0;
p0=p;
p1=head2;
while(p1->next!=NULL)
{
p1=p1->next;
}
p1->next=p0;
p0->next=NULL;
if (head2->next==NULL)
printf("not been insert!\n");
return (head2);
}
struct XYpoint *del(struct XYpoint *head,struct XYpoint *p)
{
struct XYpoint *p0,*p1;
if(head==NULL)
{
printf("\nlist null\n");
goto end;
}
p0=head;
while((p->x!=p0->x||p->y!=p0->y)&&p0->next!=NULL)
{
p1=p0;
p0=p0->next;
}
if(p->x==p0->x&&p->y==p0->y)
{
if(p0==head)
head=p0->next;
else
p1->next=p0->next;
}
else
printf("not been found!\n");
end:
return (head);
}
struct XYpoint *miny(struct XYpoint *head)
{
double min;
struct XYpoint *p,*p1;
p=head;
min=p->y;
p1=p;
p=p->next;
while (p!=NULL)
{
if (min>p->y)
{min=p->y,p1=p;}
else if(min==p->y&&p1->x>p->x)
{min=p->y,p1=p;}
else p=p->next;
}
return(p1);
}
double angle(struct XYpoint *a,struct XYpoint *b,struct XYpoint *c)
{
struct XYpoint *p0,*p1,*p2;
double dsx,dsy,dex,dey,cosfi,norm,fi;
p0=a;
p1=b;
p2=c;
dsx=p1->x-p0->x;
dsy=p1->y-p0->y;
dex=p2->x-p1->x;
dey=p2->y-p1->y;
cosfi=dsx*dex+dsy*dey;
norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey);
cosfi/=sqrt( norm );
fi=acos(cosfi);
if(cosfi<=-1) fi=PI;
if(cosfi>=1) fi=0;
return(fi);
}
double dis(struct XYpoint *a,struct XYpoint *b)
{
struct XYpoint *p1,*p2;
double dsx,dsy,dx;
p1=a;
p2=b;
dsx=p2->x-p1->x;
dsy=p2->y-p1->y;
dx=sqrt(dsx*dsx+dsy*dsy);
return(dx);
}
struct XYpoint *tank( struct XYpoint *head ,struct XYpoint *head2)
{
double minfi,fi;
double dx,dy;
struct XYpoint *p,*p1,*p2;
p2=p=head;
p1=head2;
minfi=PI;
while(p!=NULL)
{
dx=p->x-p1->x;
dy=p->y-p1->y;
if(dx!=0)
{
fi=atan(dy/dx);
if(fi<0)
fi=fi+PI;
}
else if(dx==0&&dy==0) fi=PI;
else fi=PI/2.0;
if(minfi>=fi)
{
minfi=fi;p2=p;
}
p=p->next;
}
return (p2);
}
struct XYpoint *convexHull( struct XYpoint *head ,struct XYpoint *head2)
{
double min;
double tempAngle;
struct XYpoint *lastP,*nowP,*p,*p1,*p2;
p=head;
nowP=p1=head2;
lastP=nowP;
p1=p1->next;
nowP=p1;
while(p1->next!=NULL)
{
p1=p1->next;
lastP=nowP;
nowP=p1;
}
min=angle(lastP,nowP,p);
p2=p;
p=p->next;
while(p!=NULL)
{
tempAngle=angle(lastP,nowP,p);
if (min>tempAngle)
{
min=tempAngle;
p2=p;
p=p->next;
}
else if(min==tempAngle)
{
if(dis(nowP,p2)<dis(nowP,p))
p2=p;
p=p->next;
}
else
{
p=p->next;
}
}
return(p2);
}
void print(struct XYpoint *head2)
{
FILE *fp;
struct XYpoint *p;
p=head2;
if((fp=fopen("out_put.txt","w"))==NULL)
{
printf("can not open the file\n");
exit(0);
}
fprintf(fp,"%ld",pointSum);
fprintf(fp,"\n");
while(p!=NULL)
{
fprintf(fp,"%lf,%lf",p->x,p->y);
fprintf(fp,"\n");
p=p->next;
}
fclose(fp);
}
/*
int _tmain(int argc, _TCHAR* argv[])
{
struct XYpoint *head ,*head2,*pp,*qq;
head=creat();
pp=miny(head);
head2=(struct XYpoint *)malloc(LEN);
head2->x=pp->x;
head2->y=pp->y;
head2->next=NULL;
pp=tank(head,head2);
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
do
{
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
}while(!(head2->x==pp->x&&head2->y==pp->y));
print(head2);
return 0;
}
*/
//view.h
class CCreateHullView : public CView
{
private:
int m_nPtnum;
XYpoint *m_pPtHead;
XYpoint *m_pHullHead;
};
//view.cpp
CCreateHullView::CCreateHullView()
{
// TODO: add construction code here
m_nPtnum = 0;
m_pPtHead = NULL;
m_pHullHead = NULL;
}
CCreateHullView::~CCreateHullView()
{
if (m_nPtnum > 0)
{
XYpoint *p = m_pPtHead;
while (NULL != p)
{
m_pPtHead = p->next;
p->next = NULL;
delete p;
p = m_pPtHead;
}
m_pPtHead = NULL;
m_nPtnum = 0;
p = m_pHullHead;
while (NULL != p)
{
m_pHullHead = p->next;
p->next = NULL;
delete p;
p = m_pHullHead;
}
m_pHullHead = NULL;
}
}
void CCreateHullView::OnLButtonDown(UINT nFlags, CPoint point)
{
// TODO: Add your message handler code here and/or call default
if (0 == m_nPtnum)
{
m_pPtHead = new XYpoint;
m_pPtHead->x = point.x;
m_pPtHead->y = point.y;
m_pPtHead->next = NULL;
m_nPtnum++;
}
XYpoint *p = new XYpoint;
p->x = point.x;
p->y = point.y;
p->next = m_pPtHead;
m_pPtHead = p;
m_nPtnum++;
Invalidate();
CView::OnLButtonDown(nFlags, point);
}
void CCreateHullView::OnCreateHull()
{
// TODO: Add your command handler code here
if (0 < m_nPtnum)
{
struct XYpoint *head ,*head2,*pp,*qq;
head = m_pPtHead;
pp = miny(head);
head2=(struct XYpoint *)malloc(LEN);
head2->x=pp->x;
head2->y=pp->y;
head2->next=NULL;
pp=tank(head,head2);
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
do
{
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
}while(!(head2->x==pp->x&&head2->y==pp->y));
//print(head2);
m_pHullHead = head2;
Invalidate();
}
}
void CCreateHullView::OnDraw(CDC* pDC)
{
CCreateHullDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
XYpoint *p = NULL;
if (0 < m_pHullHead)
{
p = m_pHullHead;
pDC->Rectangle((int)(m_pHullHead->x) - 2, (int)(m_pHullHead->y) - 2, (int)(m_pHullHead->x) + 2, (int)(m_pHullHead->y) + 2);
pDC->MoveTo((int)(m_pHullHead->x), (int)(m_pHullHead->y));
p = m_pHullHead->next;
while (NULL != p)
{
pDC->Rectangle(
(int)(p->x) - 2,
(int)(p->y) - 2,
(int)(p->x) + 2,
(int)(p->y) + 2
);
pDC->LineTo(CPoint((int)p->x, (int)p->y));
p = p->next;
}
p = m_pHullHead;
pDC->LineTo(CPoint((int)p->x, (int)p->y));
}
p = m_pPtHead;
while (NULL != p)
{
pDC->Rectangle(
(int)(p->x) - 2,
(int)(p->y) - 2,
(int)(p->x) + 2,
(int)(p->y) + 2
);
// pDC->FillSolidRect(
// (int)(p->x) - 2,
// (int)(p->y) - 2,
// (int)(p->x) + 2,
// (int)(p->y) + 2,
// RGB(225, 0, 0)
// );
p = p->next;
}
}
不知道可以不，應該可以運行吧，你先試試
Ⅱ 一個關於melkman凸包演算法的問題
Melkman只能用在簡單多邊形上。
Ⅲ 凸包的發展歷史,急需，越詳細越好，謝謝！！！！
⒈對於一個集合D，D中任意有限個點的線性組合的全體稱為D的凸包。 ⒉對於一個集合D，所有包含D的凸集之交稱為D的凸包。 可以證明，上述兩種定義是等價的 概念
1 點集Q的凸包（convex hull）是指一個最小凸多邊形，滿足Q中的點或者在多邊形邊上或者在其內。右圖中由紅色線段表示的多邊形就是點集Q={p0,p1,...p12}的凸包。 2 一組平面上的點，求一個包含所有點的最小的凸多邊形，這就是凸包問題了。這可以形象地想成這樣：在地上放置一些不可移動的木樁，用一根繩子把他們盡量緊地圈起來，並且為凸邊形，這就是凸包了。編輯本段平面凸包求法常見求法
2.0 Graham's Scan法求解凸包問題
概念 凸包（Convex Hull）是一個計算幾何（圖形學）中的概念。用不嚴謹的話來講，給定二維平面上的點集，凸包就是將最外層的點連接起來構成的凸多邊型，它能包含點集中所有點的。嚴謹的定義和相關概念參見維基網路：凸包。 這個演算法是由數學大師葛立恆（Graham）發明的，他曾經是美國數學學會（AMS）主席、AT&T首席科學家以及國際雜技師協會（IJA）主席。（太汗了，這位大牛還會玩雜技~） 問題 給定平面上的二維點集，求解其凸包。 過程 ⒈ 在所有點中選取y坐標最小的一點H，當作基點。如果存在多個點的y坐標都為最小值，則選取x坐標最小的一點。坐標相同的點應排除。然後按照其它各點p和基點構成的向量<H,p>；與x軸的夾角進行排序，夾角由大至小進行順時針掃描，反之則進行逆時針掃描。實現中無需求得夾角，只需根據向量的內積公式求出向量的模即可。以下圖為例，基點為H，根據夾角由小至大排序後依次為H，K，C，D，L，F，G，E，I，B，A，J。下面進行逆時針掃描。 ⒉ 線段<H,K>；一定在凸包上，接著加入C。假設線段<K,C>；也在凸包上，因為就H，K，C三點而言，它們的凸包就是由此三點所組成。但是接下來加入D時會發現，線段<K,D>；才會在凸包上，所以將線段<K,C>；排除，C點不可能是凸包。 ⒊ 即當加入一點時，必須考慮到前面的線段是否會出現在凸包上。從基點開始，凸包上每條相臨的線段的旋轉方向應該一致，並與掃描的方向相反。如果發現新加的點使得新線段與上線段的旋轉方向發生變化，則可判定上一點必然不在凸包上。實現時可用向量叉積進行判斷，設新加入的點為pn + 1，上一點為pn，再上一點為pn - 1。順時針掃描時，如果向量<pn - 1,pn>；與<pn,pn + 1>；的叉積為正（逆時針掃描判斷是否為負），則將上一點刪除。刪除過程需要回溯，將之前所有叉積符號相反的點都刪除，然後將新點加入凸包。 在上圖中，加入K點時，由於線段<H,K>；相對於<H,C>；為順時針旋轉，所以C點不在凸包上，應該刪除，保留K點。接著加入D點，由於線段<K,D>；相對<H,K>；為逆時針旋轉，故D點保留。按照上述步驟進行掃描，直到點集中所有的點都遍例完成，即得到凸包。 復雜度 這個演算法可以直接在原數據上進行運算，因此空間復雜度為O⑴。但如果將凸包的結果存儲到另一數組中，則可能在代碼級別進行優化。由於在掃描凸包前要進行排序，因此時間復雜度至少為快速排序的O(nlgn）。後面的掃描過程復雜度為O(n），因此整個演算法的復雜度為O(nlgn）。 ⒉1凸包最常用的凸包演算法是Graham掃描法和Jarvis步進法。 對於一個有三個或以上點的點集Q，過程如下： 計算點集最右邊的點為凸包的頂點的起點，如上圖的P3點。 Do For i = 0 To 總頂點數 計算有向向量P3->Pi If 其餘頂點全部在有向向量P3->Pi的左側或右側，則Pi點為凸包的下一頂點 Pi點加入凸包列表 GoTo 1 End If Next Exit Do 1: Loop 此過程執行後，點按極角自動順時針或逆時針排序，只需要按任意兩點的次序就可以了。而左側或右側的判斷可以用前述的矢量點積性質實現。
特殊演算法
⒉2求凸包有很多方法，不過最適合OIer和ACMer的估計還是Graham's Scan這個方法了。它的大致方法是這樣的：首先，找到所有點中最左邊的（y坐標最小的），如果y坐標相同，找x坐標最小的；以這個點為基準求所有點的極角（atan2(y-y0,x-x0）），並按照極角對這些點排序，前述基準點在最前面，設這些點為P[0]..P[n-1]；建立一個棧，初始時P[0]、P[1]、P[2]進棧，對於P[3..n-1]的每個點，若棧頂的兩個點與它不構成「向左轉」的關系，則將棧頂的點出棧，直至沒有點需要出棧以後將當前點進棧；所有點處理完之後棧中保存的點就是凸包了。 如何判斷A、B、C構成的關系不是向左轉呢？如果b-a與c-a的叉乘小於0就不是。a與b的叉乘就是a.x*b.y-a.y*b.x。 上面的這個Graham的實現比我原來按照USACO里的課文寫得簡單多了，主要是它通過簡單的預處理保證了P[0]、P[1]以及P[n-1]肯定是凸包里的點，這樣就可以避免在凸包「繞回來」的時候繁雜的處理。
中心法
先構造一個中心點，然後將它與各點連接起來，按斜率遞增的方法，求出凸包上部；再按斜率遞減的方法，求出凸包下部。
水平法
從最左邊的點開始，按斜率遞增的方法，求出凸包上部；再按斜率遞減的方法，求出凸包下部。水平法較中心法減少了斜率無限大的可能，減少了代碼的復雜度。編輯本段代碼例代碼一
（在編輯器中將"_ "(下劃線+空格）替換成兩個空格即可編譯； 注意要去掉開通的雙位元組中文空格，蛋疼的網路。）
Ⅳ 求大神詳細講解c/c++/pascal凸包演算法
實這個演算法是在一年前得某場比賽中臨時雹肆抱佛腳學的，今天重新的來溫習了一遍
如何來理解凸包？一組平面上的點，求一個包含所有點的最小的凸多邊形，這就是凸包問題了。這可以形象地想成這樣：在地上放置一些不可移動的木樁，用一根繩子把他們盡量緊地圈起來，這就是凸包了，網路中的這張圖很生動+活潑+形象，所以你懂的鋒肆族
好說完這個我們首先要來了解下極角排序和左轉判定
極角排序：就是選取一個最左的點，按y最小，其次x最小來定義，接下來所有的點針對該點的射線，
按角度由小到大，若相同按距離由近到遠來排序
左轉判定：這個和叉積有關，對於向量p1(x1,y1),p2(x2,y2)如果x1*y2-x2*y1>0,則從p1到p2左轉
我學的是Graham演算法，那麼接下來來介紹下該演算法
（1）選取最下左的點P0
（2）計算出每個點相對於P0的角度和距離(利用這個來排序)排序
（3）設點數為n，將p[n-1]和p[0]入棧，判斷點集合是否為一條直線（初銀弊始k=2表示當前凸包的大小）
（4）i從1到n-1遍歷，對於p[k-1],p[k-2],p[i]若滿足左轉，將p[i]壓入棧
否則i--，k--
（5）k--,返回k表示凸包的點數
下面是我寫的模板
int Polygon::Graham(Polygon &con){//別用自己做對象
int t=0,i;
Point tmp;
//先y最小再x最小
for(i=1;i<n;i++)if(p[i]<p[t])t=i;
swap(p[t],p[0]);
for(i=0;i<n;i++){
tmp=p[i]-p[0];
p[i].dis=tmp.Len2();
p[i].angle=atan2(tmp.y,tmp.x);
}
sort(p,p+n,_cmp);
//for(int i=0;i<n;i++)p[i].out();
//cout<<"***"<<endl;
int k=0;
con.p[k++]=p[n-1];
con.p[k++]=p[0];
if(Sig(p[1].angle-p[n-1].angle)==0)con.p[k++]=p[n-1];//凸包為一線段
else{
for(i=1;i<n;i++){
//con[k-1].out();
//con[k-2].out();
//p[i].out();
if(Sig(Cross(con.p[k-1],con.p[k-2],p[i]))>0)con.p[k++]=p[i];
else {i--;k--;}
//cout<<"---"<<endl;
//for(int j=0;j<k;j++)con[j].out();
//system("pause");
}
}
return con.n=--k;
}
/*
9
1 4
3 6
5 7
2 2
3 3
5 4
8 3
9 6
7 1
*/
摘自http://blog.csdn.net/foreverlin1204/article/details/6221986
Ⅳ matlab如何求大量數據中分布最多的范圍及中心點。
樓主是不是想求出一個最小半徑的圓，圓內包含所有的點？這個問題很有趣。
尋找這個圓的時候注意一下幾點：
1.這個圓必然穿過圖中某些靠外圍的點，這樣才是最小半徑的圓。
2.幾何中我們知道，三個點可以確定一個圓, 我們就是需要找出這三個點來.
演算法如下：1.先求這些點對應的凸包，已經有現成的演算法。
2.生成凸包後，在看凸包上哪三點確定的圓可以包含凸包。
當然如果樓主討論的不是以上所述，而是模式分類的話，建議看看數據分類方法。可以搜索關鍵字：Gaussian mixtrual model, expectation-maximization algorithm 和 k-mean algorithm 學習下相關的知識。
Ⅵ C++ 散點聚類凸包相交問題
這個問題是衫陵可以做的，首先要確定的是兩類點有兩個凸包，需要分別求解。這個是二維點集生成平面圖形的問題，解決你給的這個問題的方法有很多。我給個思路，在搏枯凸包（Convex Hull）的生成過程中，採用的是從某一個基點（比如最左下角的點），將所有其他點與該點連線的斜率均計算出來，按照一定的順序（比如斜率從小到大或銀戚的順序）將各個點連接起來，這個是原始的凸包演算法，這個演算法中只考慮了斜率，沒考慮兩個點距離。因此，你這個問題需要把兩點間距離考慮進來，把距離d和斜率k綜合考慮。具體實現過程你可以自己完成了，順便多說一句，最好把d設置成一個可變化的量，比如當尋找到的下一個點是個錯誤的點，那麼就把d變化為原來的1.2倍再嘗試。
Ⅶ origin怎麼找兩條線距離最遠的點
這是一個計算幾何學問題，可以使用一些演算法來解決。以下是其中一種可能的解決方案：
假設有運沖n個點，可以首先使用暴力方法找到所有點對之間的距離毀漏，並記錄最大距離d。然後，從這些點中任選兩個距離為d的點作為起始點。
接下來，將剩餘的點分別與這兩個點計算距離，如果當前點到距離更遠的那個點的距離比當前最大距離更大，則更新最大距離，並將該點作為新的終點。重復該步驟直到遍歷完所有的點，旁余殲即可找到兩條線距離最遠的點。
上述演算法的時間復雜度為O(n^2)，在數據量較小的情況下可行。但如果數據量很大，可以考慮使用優化演算法，如kd-tree或Voronoi圖等，以降低時間復雜度
Ⅷ 跪求matlab 凸包演算法 算多邊形面積
Matlab演算法
x和y代表你畫的散點的橫縱坐標向量，當然肯定是等長度的。
plot(x,y, '*', 'markersize',10);
dt = DelaunayTri(x,y);
k = convexHull(dt);
plot(x,y, '.', 'markersize',10);
hold on;
plot(x(k), y(k), 'r');
Perimeter = sqrt(diff(x(k))*diff(x(k))'+ diff(y(k))*diff(y(k))'); % 周長
area=abs(trapz(x(k),y(k)))%面積
就是先把散點的區域用凸多邊形畫出來，然後再求多邊形的面積和周長。
Ⅸ 如何用python實現凸包演算法
#include #include #include using namespace std; typedef double Type; // 注意下面的fabs(). const int maxn = 1005; const double EPS = 1e-8; const double Pi = acos(-1.0); struct Point { Type x, y; Point () {} Point (Type & x
Ⅹ java凸包演算法
源碼一 JarvisMarch java
package nvex;
import static java lang Math abs;
import java util Iterator;
import java util LinkedList;
import java util List;
public class JarvisMarch {
private int count;
public int getCount() {
扮虧return count;
}
public void setCount(int count) {
unt = count;
}
private static int MAX_ANGLE = ;
private double currentMinAngle = ;
穗缺談private List<Point> hullPointList;
private List<Integer> indexList;
private PointFactory pf;
private Point[] ps;
public Point[] getPs() {
return ps;
}
private int firstIndex;
public int getFirstIndex() {
return firstIndex;
}
public JarvisMarch() {
this( );
}
public JarvisMarch(int count) {
pf = PointFactory getInstance(count);
猜碰initialize();
}
public JarvisMarch(int[] x int[] y) {
pf = PointFactory getInstance(x y);
initialize();
}
private void initialize() {
hullPointList = new LinkedList<Point>();
indexList = new LinkedList<Integer>();
firstIndex = pf getFirstIndex();
ps = pf getPoints();
addToHull(firstIndex);
}
private void addToHull(int index) {
indexList add(index);
hullPointList add(ps[index]);
}
public int calculateHull() {
for (int i = getNextIndex(firstIndex); i != firstIndex; i = getNextIndex(i)) {
addToHull(i);
}
showHullPoints();
return ;
}
private void showHullPoints() {
Iterator<Point> itPoint = erator();
Iterator<Integer> itIndex = erator();
Point p;
int i;
int index = ;
System out println( The hull points is: > );
while (itPoint hasNext()) {
i = itIndex next();
p = itPoint next();
System out print(i + :( + p getX() + + p getY() + ) );
index++;
if (index % == )
System out println();
}
System out println();
System out println( **************************************************************** );
System out println( The count of all hull points is + index);
}
public int getNextIndex(int currentIndex) {
double minAngle = MAX_ANGLE;
double pseudoAngle;
int minIndex = ;
for (int i = ; i < ps length; i++) {
if (i != currentIndex) {
pseudoAngle = getPseudoAngle(ps[i] getX() ps[currentIndex] getX()
ps[i] getY() ps[currentIndex] getY());
if (pseudoAngle >= currentMinAngle && pseudoAngle < minAngle) {
minAngle = pseudoAngle;
minIndex = i;
} else if (pseudoAngle == minAngle){
if((abs(ps[i] getX() ps[currentIndex] getX()) >
abs(ps[minIndex] getX() ps[currentIndex] getX()))
|| (abs(ps[i] getY() ps[currentIndex] getY()) >
abs(ps[minIndex] getY() ps[currentIndex] getY()))){
minIndex = i;
}
}
}
}
currentMinAngle = minAngle;
return minIndex;
}
public double getPseudoAngle(double dx double dy) {
if (dx > && dy >= )
return dy / (dx + dy);
if (dx <= && dy > )
return + (abs(dx) / (abs(dx) + dy));
if (dx < && dy <= )
return + (dy / (dx + dy));
if (dx >= && dy < )
return + (dx / (dx + abs(dy)));
throw new Error( Impossible );
}
}
源碼二 Point java
package nvex;
public class Point {
// 定義點的x y坐標 之所以是int類型 是為了日後可以在計算機屏幕上進行可視化
private int x;
private int y;
// x y的get方法
public int getX() {
return x;
}
public int getY() {
return y;
}
// 定義點到屏幕邊緣的距離
private static double PADDING = ;
// 點在屏幕中的范圍
private static double POINT_RANGE = ( PADDING * );
// 默認構造方法 產生隨機點
public Point() {
this x = (int) ((Math random() * POINT_RANGE) + PADDING);
this y = (int) ((Math random() * POINT_RANGE) + PADDING);
}
// 帶參構造方法 可以實現手動輸入固定點
public Point(int x int y) {
this x = x;
this y = y;
}
// 覆寫hashCode()和equals()方法 實現比較和Hash
@Override
public int hashCode() {
final int prime = ;
int result = ;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
Point other = (Point) obj;
if ((x == other x) && (y == other y))
return true;
return false;
}
}
源碼三 PointFactory java
package nvex;
public class PointFactory {
/**
* 單例模式 大批量產生Point 也可以手動產生Point
*/
private Point[] points = null;
private int newIndex;
private int firstIndex = ;
public Point[] getPoints() {
return points;
}
public int getFirstIndex() {
return firstIndex;
}
public static PointFactory getInstance() {
return new PointFactory();
}
public static PointFactory getInstance(int count) {
return new PointFactory(count);
}
public static PointFactory getInstance(int[] x int[] y) {
return new PointFactory(x y);
}
private PointFactory() {
this( );
}
private PointFactory(int count) {
points = new Point[count];
for (int i = ; i < count; i++) {
points[i] = new Point();
newIndex = i;
validatePoints();
}
firstIndex = getFirstPoint();
}
public PointFactory(int[] x int[] y) {
points = new Point[y length];
for (int i = ; i < y length; i++) {
points[i] = new Point(x[i] y[i]);
}
firstIndex = getFirstPoint();
}
private void validatePoints() {
for(int i = ; i < newIndex; i++) {
if(points[i] equals(points[newIndex])) {
points[newIndex] = new Point();
validatePoints();
}
}
}
public int getFirstPoint() {
int minIndex = ;
for (int i = ; i < points length; i++) {
if (points[i] getY() < points[minIndex] getY()) {
minIndex = i;
} else if ((points[i] getY() == points[minIndex] getY())
&& (points[i] getX() < points[minIndex] getX())) {
minIndex = i;
}
}
return minIndex;
}
}
源碼四 Test java（主函數）
package nvex;
public class Test {
public static void main(String[] args) {
long start = System currentTimeMillis();
JarvisMarch j = new JarvisMarch( );
Point[] points = j getPs();
int firstIndex = j getFirstIndex();
// for (int i = ; i < points length; i++) {
// System out print(i + :( + points[i] getX() + + points[i] getY() + ) );
// if((i+ ) % == ) {
// System out println();
// }
// }
// System out println();
// System out println( ***************************************************************** );
System out println( the first point is: + firstIndex + :( +
points[firstIndex] getX() + + points[firstIndex] getY() + ) );
System out println( ***************************************************************** );
j calculateHull();
System out println( The total running time is + (System currentTimeMillis() start) + millis );
}
lishixin/Article/program/Java/hx/201311/26948