⑴ ACM 凸包 演算法
先解釋下凸包 顧名思義 就是多邊形是凸的 沒有某個點是凹進多邊形內部的 哈 文字我也描述不清楚 在高等數學里就有凸的定義 二次導數恆不小於0
再者 就是凸包演算法的定義了 凸包演算法一般就是計算能包裹住一個點集的最小的凸多邊形
至於具體的演算法 有很多 也不貼過來了 請看這篇帖子 偽代碼比較容易看懂演算法的原理
http://www.blogjava.net/sishuiweilan/archive/2007/10/10/151671.html
不懂的地方請追問
⑵ 一個關於melkman凸包演算法的問題
Melkman只能用在簡單多邊形上。
⑶ 如何用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
⑷ 求二維凸包的增量演算法，最好能詳細解釋一下
#include <iostream>
#include <algorithm>
#include <cmath>
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 & xx, Type & yy) : x(xx), y(yy) {}
};
// 判斷正負.
int dblcmp(Type d)
{
if (fabs(d) < EPS) return 0; // 注意數據類型不同，abs()也不同.
return d > 0 ? 1 : -1;
}
// 叉乘.
// cross proct of (c->a) and (c->b).
Type Cross(Point & c, Point a, Point b)
{
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
Type Distance(Point & u, Point & v)
{
return sqrt( 0.0 + (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y) );
}
int n;
Point point[maxn];
int Stack[maxn];
int top;
double ans;
bool cmp(const Point & a, const Point & b)
{
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
void graham_scan(void)
{
int i;
int temp_top;
if (n <= 1)
{
top = 0;
return ;
}
sort(point, point + n, cmp); // point[0]即為起點.
// 做右鏈.
top = -1;
Stack[++top] = 0; Stack[++top] = 1;
for (i = 2; i < n; i++)
{
while (top >= 1 && dblcmp(Cross(point[Stack[top - 1]], point[i], point[Stack[top]])) >= 0) top--; // 如果不能左轉，則退棧. 如果只要求極點，則共線的點也是不要的(即要加等於).
Stack[++top] = i;
}
temp_top = top; // 此時的棧頂元素一定是第n個點.
// 做左鏈.
Stack[++top] = n - 2;
for (i = n - 3; i >= 0; i--)
{
while (top >= temp_top + 1 && dblcmp(Cross(point[Stack[top - 1]], point[i], point[Stack[top]])) >= 0) top--; // 如果不能左轉，則退棧. 如果只要求極點，則共線的點也是不要的(即要加等於).
Stack[++top] = i;
}
// 此時的棧頂元素是第1個點.(如果凸包是一條直線，則左右鏈倒置相同.)
// 凸包的頂點為point[Stack[0]] 到 point[Stack[top - 1]].
}
int main(void)
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%lf %lf", &point[i].x, &point[i].y);
}
graham_scan();
ans = 0;
for (i = 0; i < top; i++)
{
printf("%lf %lf\n", point[Stack[i]].x, point[Stack[i]].y);
ans += Distance(point[Stack[i]], point[Stack[i + 1]]); // point[Stack[top]] = point[Stack[0]].
}
printf("%lf\n", ans);
return 0;
}
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/******************************************************************************************************************************************************/
/* 按照lrj的黑書來寫的.
適用條件：簡單多邊形(點按順時針或逆時針給出).
復雜度：O(n).
*/
#include <iostream>
#include <algorithm>
#include <cmath>
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 & xx, Type & yy) : x(xx), y(yy) {}
};
// 判斷正負.
int dblcmp(Type d)
{
if (fabs(d) < EPS) return 0; // 注意數據類型不同，abs()也不同.
return d > 0 ? 1 : -1;
}
// 叉乘.
// cross proct of (c->a) and (c->b).
Type Cross(Point & c, Point a, Point b)
{
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
Type Distance(Point & u, Point & v)
{
return sqrt( 0.0 + (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y) );
}
int n;
Point point[maxn];
int Stack[2 * maxn]; // 兩頭棧.
int bot, top; // 棧底，棧頂.
double ans;
void Melkman(void)
{
int i;
int temp;
Stack[n] = 0;
// 注意：前三個點不能是共線的.
for (i = 1; i < n; i++)
{
Stack[n + 1] = i; // 當三點平行時要的是後一個點.
if (dblcmp(Cross(point[Stack[n]], point[Stack[n + 1]], point[i + 1]))) break; // 前三個點不共線.
}
bot = n, top = n + 1;
Stack[++top] = Stack[--bot] = i + 1;
// 保證開始的三個點成右手系，否則交換Stack[n]和Stack[n + 1] .
if (dblcmp(Cross(point[Stack[n]], point[Stack[n + 1]], point[Stack[n + 2]])) < 0)
{
temp = Stack[n]; Stack[n] = Stack[n + 1]; Stack[n + 1] = temp;
}
// 維護棧里的點為右手系(即棧中任意連續三點組成的路徑是左旋的，或成直線).
for (i = i + 2; i < n; i++)
{
if (dblcmp(Cross(point[Stack[top - 1]], point[Stack[top]], point[i])) > 0 &&
dblcmp(Cross(point[Stack[bot]], point[Stack[bot + 1]], point[i])) > 0)
{ // 如果該點對於棧頂左旋且對於棧底右旋，則說明該點在凸包內.
continue;
}
while (dblcmp(Cross(point[Stack[top - 1]], point[Stack[top]], point[i])) <= 0) top--;
Stack[++top] = i;
while (dblcmp(Cross(point[Stack[bot]], point[Stack[bot + 1]], point[i])) <= 0) bot++;
Stack[--bot] = i;
}
}
int main(void)
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%lf %lf", &point[i].x, &point[i].y);
}
Melkman(); // 得到的凸包點序列也是按極角序的.
cout << top - bot << endl;
for (i = bot; i < top; i++)
{
printf("%lf %lf\n", point[Stack[i]].x, point[Stack[i]].y);
ans += Distance(point[Stack[i]], point[Stack[i + 1]]); // Stack[top]為第1個點.
}
printf("%lf\n", ans);
return 0;
}
⑸ opencv中的凸包採用什麼演算法
我寫過c#的凸包演算法 用的是一個雜技演員(...)提出的方法
opencv不很清楚 不過這演算法本身不算很復雜 除了暴力法運算量上差異應該不大
⑹ 請問凸包演算法的時間復雜度的測試代碼怎麼寫
代碼一
（在編輯器中將"_ "(下劃線+空格）替換成兩個空格即可編譯； 注意要去掉開通的雙位元組中文空格，蛋疼的網路。）
#include <iostream>
#include <algorithm>
using namespace std;
struct point
{
_ _ int x;
_ _ int y;
} p[30005],res[30005];//p標記圖中所有的點，res標記凸包上的點
int cmp(point p1,point p2）
{
_ _ return p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x);
}
bool ral(point p1,point p2,point p3） //用叉乘判斷點的位置
{
_ _ return (p2.x - p1.x)*(p3.y - p1.y) > (p3.x - p1.x)*(p2.y - p1.y);
}
int main()
{
_ _ int n,i;
_ _ while(scanf("%d",&n) != EOF) //一共有n個點
_ _ {
_ _ _ _ for(i = 0; i < n; i++)
_ _ _ _ _ _ scanf("%d%d",&p[i].x,&p[i].y);
__ _ _ if(n == 1）
_ _ _ _ {
_ _ _ _ _ _ printf("%d %d\n",p[0].x,p[0].y);
_ _ _ _ _ _ continue;
_ _ _ _ }
_ _ _ _ if(n == 2）
_ _ _ _ {
_ _ _ _ _ _ printf("%d %d\n",p[0].x,p[0].y);
_ _ _ _ _ _ printf("%d %d\n",p[1].x,p[1].y);
_ _ _ _ _ _ continue;
_ _ _ _ }
_ _ _ _ sort(p,p + n,cmp);
_ _ _ _ res[0] = p[0];
_ _ _ _ res[1] = p[1];
_ _ _ _ int top = 1;
_ _ _ _ for(i = 2; i < n; i++)
_ _ _ _ {
_ _ _ _ _ _ while(top && !ral(res[top],res[top - 1],p[i]))
_ _ _ _ _ _ top--;
_ _ _ _ _ _ res[++top] = p[i];
_ _ _ _ }
_ _ _ _ int len = top;
_ _ _ _ res[++top] = p[n - 2];
_ _ _ _ for(i = n - 3; i >= 0; i--)
_ _ _ _ {
_ _ _ _ _ _ while(top != len && !ral(res[top],res[top - 1],p[i]))
_ _ _ _ _ _ top--;
_ _ _ _ _ _ res[++top] = p[i];
_ _ _ _ }
_ _ _ _ for(i = 0; i < top; i++)
_ _ _ _ _ _ printf("%d %d\n",res[i].x,res[i].y);//輸出凸包上的點
_ _ }
_ _ return 0;
}
代碼二
#include <iostream> // 求點集合的凸包的gram演算法。n是頂點個數，x,y是頂點
坐標。
#include <fstream> // order 是按照頂點和左下腳的角度的排序後數組。
#include <deque> // tu即是逆時針的凸包上的頂點。
#include <math.h> //
using namespace std; //使用條件：1。點可以任意給，可重復。
// 2。三個以及以上的點。
ifstream fin("input.txt"); // 3。已經考慮了邊上有點的情況。
#define NN 1000
#define pi 3.1415827
typedef struct Cseg{
double x,y,tg;
}Cseg;
int n;
double x[NN],y[NN];
deque <Cseg> order;
deque <int> tu;
Cseg seg1;
deque <Cseg> ::iterator p1;
deque <int> ::iterator p,q;
void in();
void gram();
void makeorder(int s);
double dist(double x1,double yy1,double x2,double yy2）；
double cross(double x1,double yy1,double x2,double yy2）；
void out();
int main()
{
in();
gram();
out();
return 0;
}
void out()
{
int i;
for (i=0;i<tu.size();i++){
cout<<order[tu].x<<" "<<order[tu].y<<endl;
}
cout<<tu.size()<<" Edges Polydgon"<<endl;
return;
}
void in()
{
int i;
fin>>n;
for (i=0;i<n;i++)
fin>>x>>y;
return;
}
void gram()
{
int i,mm;
mm=0;
for (i=1;i<n;i++)
if (y[mm]>y+1e-9） mm=i;
else if (fabs(y[mm]-y)<1e-9 && x[mm]>x+1e-9） mm=i;
makeorder(mm);
seg1.x=x[mm];
seg1.y=y[mm];
tu.clear();
tu.push_back(0);
tu.push_back⑴；
tu.push_back⑵；
for (i=3;i<order.size();i++){
p=tu.end();
seg1.x=order.x;
seg1.y=order.y;
p--;
q=p-1;
if
（cross(order[*p].x-order[*q].x,order[*p].y-order[*q].y,order.x-order[*
q].x,order.y-order[*q].y)>1e-9）
tu.push_back(i);
else{
tu.pop_back();
i--;
continue;
//tu.push_back(i);
}
}//for
return;
}
void makeorder(int s)
{
int i;
double tg;
order.clear();
for (i=0;i<n;i++){
if (i==s) continue;
tg=atan2(y-y[s],x-x[s]);
seg1.x=x;
seg1.y=y;
seg1.tg=tg;
p1=order.begin();
while (p1!=order.end()){
if (fabs(tg-p1->tg)<1e-9）{
if
（dist(x[s],y[s],x,y)>dist(x[s],y[s],p1->x,p1->y)+1e-9） {
p1->x=x;
p1->y=y;
}
break;
}
else
if (tg<p1->tg){
order.insert(p1,seg1）；
break;
}
p1++;
}//while
if (p1==order.end()) order.insert(p1,seg1）；
}//for
seg1.x=x[s];seg1.y=y[s];
order.insert(order.begin(),seg1）；
//for (i=0;i<order.size();i++)
// printf("i=%d %lf %lf
%lf\n",i,order.x,order.y,order.tg*180/pi);
return;
}
double cross(double x1,double yy1,double x2,double yy2）
{
return (x1*yy2-x2*yy1）；
}
double dist(double x1,double yy1,double x2,double yy2）
{
return pow((x1-x2）*(x1-x2）+(yy1-yy2）*(yy1-yy2），0.5）；
}
代碼三
P標程{pku 1113 }
{$Q-,S-,R-}
const
pi=3.1415926575;
zero=1e-6;
maxn=1000;
maxnum=100000000;
var
ans,temp :extended;
n,tot :longint;
x,y :array[0..maxn]of extended;
zz,num :array[0..maxn]of longint;
procere swap(var ii,jj:extended);
var
t :extended;
begin
t:=ii;ii:=jj;jj:=t;
end;
procere init;
var
i,j :longint;
begin
readln(n,temp);
for i:=1 to n do readln(x[i],y[i]);
end;
function ok(x,midx,y,midy:extended):longint;
begin
if abs(x-midx)<=zero then
begin
if abs(midy-y)<=zero then exit(0);
if midy>y then exit⑴
else exit⑵；
end
else
begin
if x<midx then exit⑴
else exit⑵；
end;
end;
procere qsort(head,tail:longint);
var
i,j :longint;
midx,midy :extended;
begin
i:=head;
j:=tail;
midx:=x[(head+tail) div 2];
midy:=y[(head+tail) div 2];
repeat
while ok(x[i],midx,y[i],midy)=1 do inc(i);
while ok(x[j],midx,y[j],midy)=2 do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i);
dec(j);
end;
until i>j;
if i<tail then qsort(i,tail);
if j>head then qsort(head,j);
end;
function Plot(x1,y1,x2,y2:extended):extended;
begin
Plot:=x1*y2-x2*y1;
end;
function check(first,last,new:longint):boolean;
var
ax,ay,bx,by :extended;
Pt :extended;
begin
ax:=x[last]-x[first];ay:=y[last]-y[first];
bx:=x[new]-x[first];by:=y[new]-y[first];
if Plot(ax,ay,bx,by)<-zero then exit(true)
else exit(false);
end;
procere Tbao;
var
i,j,tail :longint;
begin
tot:=0;
zz[1]:=1;tail:=1;
for i:=2 to n do
begin
while (zz[tail]<>1）and check(zz[tail-1],zz[tail],i) do dec(tail);
inc(tail);
zz[tail]:=i;
end;
inc(tot,tail-1）；
for i:=1 to tail-1 do
num[i]:=zz[i];
zz[1]:=n;tail:=1;
for i:=n-1 downto 1 do
begin
while (zz[tail]<>n)and check(zz[tail-1],zz[tail],i) do dec(tail);
inc(tail);
zz[tail]:=i;
end;
for i:=1 to tail-1 do
num[tot+i]:=zz[i];
inc(tot,tail-1）；
end;
function dist(a,b:longint):extended;
begin
dist:=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
end;
procere main;
var
i,j :longint;
begin
qsort（1,n);
Tbao;
ans:=0;
for i:=1 to tot-1 do
ans:=ans+dist(num[i],num[i+1]);
ans:=ans+dist(num[tot],num[1]);
ans:=ans+temp*pi*2;
writeln(ans:0:0);
end;
begin
init;
main;
end.
⑺ 演算法裡面凸包是什麼東西
⒈對於一個集合D，D中任意有限個點的線性組合的全體稱為D的凸包。
⒉對於一個集合D，所有包含D的凸集之交稱為D的凸包。
可以證明，上述兩種定義是等價的概念
1 點集Q的凸包（convex hull）是指一個最小凸多邊形，滿足Q中的點或者在多邊形邊上或者在其內。右圖中由紅色線段表示的多邊形就是點集Q={p0,p1,...p12}的凸包。
2 一組平面上的點，求一個包含所有點的最小的凸多邊形，這就是凸包問題了。這可以形象地想成這樣：在地上放置一些不可移動的木樁，用一根繩子把他們盡量緊地圈起來，並且為凸邊形，這就是凸包了。
⑻ 凸包的發展歷史,急需，越詳細越好，謝謝！！！！
⒈對於一個集合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]肯定是凸包里的點，這樣就可以避免在凸包「繞回來」的時候繁雜的處理。
中心法
先構造一個中心點，然後將它與各點連接起來，按斜率遞增的方法，求出凸包上部；再按斜率遞減的方法，求出凸包下部。
水平法
從最左邊的點開始，按斜率遞增的方法，求出凸包上部；再按斜率遞減的方法，求出凸包下部。水平法較中心法減少了斜率無限大的可能，減少了代碼的復雜度。編輯本段代碼例代碼一
（在編輯器中將"_ "(下劃線+空格）替換成兩個空格即可編譯； 注意要去掉開通的雙位元組中文空格，蛋疼的網路。）