今天做作业
,研究凸包算法,写了一个专说中很快的方法。听说效率N,算法的精髓在于任何的判断操作都基于一个点和向量的位置关系。
例如,要判断点是否在多边形内,只需判断点和每条边向量的位置是否都一直,都在左边或者都在右边。
bool CGrahamView::isLeft(CPoint point,m_line *line)
{
//m_line x;
float a=line->a;
float b=line->b;
float c=line->c;
float v=a*point.x+b*point.y+c*1.0f;
if(v<=0)
return true;
else
return false;
}
m_line CGrahamView::createLine(CPoint i, CPoint j)
{
//m_line *line=new m_line();
m_line line;
line.i=i;
line.j=j;
line.a=i.y-j.y;
line.b=j.x-i.x;
line.c=i.x*j.y-j.x*i.y;
return line;
}
bool CGrahamView::isInside(node *head, CPoint pt,bool isClock)
{
int flag=1;
node *p;
p=head->next;
vector<m_line> v_line;
m_line line;
while(p!=NULL&&p->next!=NULL)
{
line=createLine(p->pt,p->next->pt);
v_line.push_back(line);
p=p->next;
}
line=createLine(p->pt,head->next->pt);
v_line.push_back(line);
if(isClock==true)
{
for(int i=0;i<v_line.size();i++)
{
if(isLeft(pt,&v_line[i])==true)
{
flag=0;
break;
}
}
}
if(isClock==false)
{
for(int i=0;i<v_line.size();i++)
{
if(isLeft(pt,&v_line[i])==false)
{
flag=0;
break;
}
}
}
if(flag==0)
return false;
else
return true;
}
bool CGrahamView::findVisible(node *head, CPoint pt,bool isClock)
{
node * p;
p=head->next;
vector<m_line> v_line;
vector<int> v_point;
m_line line;
while(p!=NULL&&p->next!=NULL)
{
line=createLine(p->pt,p->next->pt);
v_line.push_back(line);
p=p->next;
}
line=createLine(p->pt,head->next->pt);
v_line.push_back(line);
if(isClock==true)
{
for(int i=0;i<v_line.size();i++)
{
if(isLeft(pt,&v_line[i])==true)
v_point.push_back(i);
}
}
else
{
for(int i=0;i<v_line.size();i++)
{
if(isLeft(pt,&v_line[i])==false)
v_point.push_back(i);
}
}
int sit=0;
int flag1;
int flag2;
int count=0;
count=v_point.size();
for(int i=0;i<v_point.size()-1;i++)
{
if(v_point[i]!=v_point[i+1]-1)
{
flag1=v_point[i];
flag2=v_point[i+1];
sit=1;
break;
}
}
if(sit==0)
{
int start=v_point[0]+1;
int end;
if(count>=2)
{
start=v_point[0]+1;
end=v_point[count-1];
for(int i=start;i<=end;i++)
//p=index(head,v_point[1]);
dele(head,start);
}
insert(head,pt,start-1);
v_point.clear();
}
else
{
int start=flag2+1;
insert(head,pt,flag2);
if(count>=2)
{
node*p=CGrahamView::index(head,(flag2+1)%CGrahamView::getSize(head));
node*q=p->next;
for(int i=count-1;i>0;i--)
{
if(q==NULL)
{
dele(head,0);
//q=head->next;
}
else
{
node*w =q;
q=q->next;
p->next=q;
delete w;
}
//if(start%CGrahamView::getSize(head)<flag2)
//flag2--;
// dele(head,start);
}
}
//insert(head,pt,flag2);
v_point.clear();
}
return 0;
}
node* CGrahamView::index(node *head, int index)
{
int i=0;
node*p;
if(index<0)
p=NULL;
else
{
p=head->next;
while(p!=NULL&&i<index)
{
p=p->next;
i++;
}
}
return p;
}
bool CGrahamView::insert(node*head,CPoint pt, int index)
{
if(index<0)
return false;
node*p;
p=CGrahamView::index(head,index);
node* np=new node();
np->pt=pt;
np->next=p->next;
p->next=np;
return true;
}
bool CGrahamView::dele(node *head, int index)
{
node*p;
int size=CGrahamView::getSize(head);
if(size==0)
// MessageBox("0");
return false;
index=index%size;
if(index<0)
return false;
if(index==0)
{
p=head->next;
head->next=p->next;
delete p;
}
else
{
p=CGrahamView::index(head,index-1);
node*q=p->next;
p->next=q->next;
delete q;
}
return true;
}
int CGrahamView::getSize(node* head)
{
int size=0;
node* p;
p=head->next;
while(p!=NULL)
{
size++;
p=p->next;
}
return size;
}
分享到:
相关推荐
graham求凸包算法 graham求凸包算法 graham求凸包算法 graham求凸包算法 graham求凸包算法 graham求凸包算法
两种凸包算法 算法导论的详细实现 C++ VS2008
本程序是基于C语言的凸包算法(Graham)实现,能够直接编译运行,计算凸包的点为随机生成。该程序为控制台应用程序,输出结果有凸包顶点坐标、以及一个50*50的矩阵,其中0表示空白点,1表示随机生成的点集,2表示...
采用Graham扫描法,实现提取凸包最小边界JS代码实现。(代码中点坐标采用平面坐标,如要在三维贴地展示,可转换为经纬度坐标)
实现凸包实现,采用MATLAB编写代码,用于凸包算法的快速实现。
通过界面化地方法实现了凸包算法,用C++语言编写,注释清晰,易懂。
C++写的二维快速凸包算法,用opengl做了展示,内含详细代码注释
凸包算法c实现,凸包在计算几何中十分基础和经典的算法
凸包算法计算随机散点的最小凸包 本人亲测,需要VS2012以上版本才可正确运行 计算复杂度为nlogn 针对大量散点(几十万),速度也很快
一种新的最小凸包算法及其应用; 一种新的最小凸包算法及其应用
/// 凸包算法 /// /// <param name="_list"></param> /// <returns></returns> private List<TuLine> BruteForceTu(List<Point> _list) { //记录极点对 List<TuLine> role = new List(); //遍历 for ...
完整凸包算法,标准C++编译,包含注释完整有效,内涵博客链接。
计算几何求凸包的java代码,运行可用,可以鼠标任意点击去点,并绘制离散点的最大凸包。
DEM两种凸包算法程序 C# .NET 点集[] 列表() VS15版窗体文件
凸包(Convex Hull)是一个计算几何(图形学)中的概念。 在一个实数向量空间中,对于给定集合,所有包含的凸集的交集被称为的凸包。
C#实现凸包算法,核心算法参考源至网络以及相关算法书籍
graham_scan_js, 在JavaScript中,Graham凸包算法的扫描实现 基于的凸壳算法的扫描为了从给定的x,y 坐标中计算凸船体,我需要一个简单的实现,我发现 hull js的凸点,或者需要其他库的依赖性。 这个实现只需要x,y ...
平面凸包算法opengl绘制 2维凸包算法 用opengl绘图
基于计算几何理论, 在分析支持向量与凸包向量关系的基础上, 提出了一种基于中心凸包算法与增量 学习的 SVM 学习算法。在确保分类器达到可靠精度的前提下, 为解决学习中时耗过长的问题, 在对当前训练集计算 凸包...
利用凸包算法,求解最优路径。main1、main2、main3为3个主程序