投稿
  1. 首页
  2. 软件运维

离散点外包凸多边形生成算法（C#或者C++），要有详细代码和说明，最好有可运行的样例程序好的另外加分，急

四川传媒学院专科 • 2023-5-26 • 软件运维 • 阅读 31

离散点外包凸多边形生成算法（C#或者C++），要有详细代码和说明，最好有可运行的样例程序好的另外加分，急,第1张

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=fip2=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

}

}

不知道可以不，应该可以运行吧，你先试试

实这个算法是在一年前得某场比赛中临时抱佛脚学的，今天重新的来温习了一遍

如何来理解凸包？一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了，百度百科中的这张图很生动+活泼+形象，所以你懂的

好说完这个我们首先要来了解下极角排序和左转判定

极角排序：就是选取一个最左的点，按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=1i<ni++)if(p[i]<p[t])t=i

swap(p[t],p[0])

for(i=0i<ni++){

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=0i<ni++)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=1i<ni++){

//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=0j<kj++)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

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/yw/12568761.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
四川传媒学院专科 四川传媒学院专科 一级用户组
0 0
上一篇 2023-05-26
下一篇 2023-05-26

发表评论

登录后才能评论

评论列表（0条）

保存