求一个用C++写的Delaunay三角剖分间接实现Voronoi图的代码。最好有算法说明谢谢！！ 急用！！

#include<iostream>

#include<cmath>

using namespace std

#define N 30

typedef struct//定义点的结构体

{

int x,y

}Point

class point

{

private:

Point *v

public:

int distance(Point i,Point j)//计算两点的距离

int w(Point i,Point j,Point k) //计算三条边的长度之和

void minWeightTriangulation(int n,int t[][N],int s[][N]) //用动态规划计算最优值

void print(int s[][N],int i,int j) //输出

}

int point::distance(Point i,Point j)

{

int s=(i.x-j.x)*(i.x-j.x)+(i.y-i.y)*(i.y-i.y)

return sqrt(s)

}

int point::w(Point i,Point j,Point k)

{

return distance(i,j)+distance(j,k)+distance(i,k)

}

void point::minWeightTriangulation(int n,int t[][N],int s[][N])//用动态规划计算最优值

{

int i=0

int r=0

int k=0

for(i=1i<=ni++) t[i][i]=0

for(r=2r<=nr++)

for(i=1i<=n-r+1i++)

{

int j=i+r-1

t[i][j]=t[i+1][j]+w(v[i-1],v[i],v[j])

s[i][j]=i

for(k=i+1k<jk++)

{

int u=t[i][k]+t[k+1][j]+w(v[i-1],v[k],v[j])

if(u<t[i][j])

{

t[i][j]=u

s[i][j]=k

}

}

}

}

void point::print(int s[][N],int i,int j)

{

if(i==j)

return

print(s,i,s[i][j])

print(s,s[i][j]+1,j)

cout<<"三角行：v"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl

}

int main()

{

int n,i

Point v[N]={0,0}

point triangle

int t[N][N],s[N][N]

cout<<"输入多边形的顶点数："

cin>>n

for(i=0i<ni++)

{

cout<<"输入第"<<i+1<<"点的坐标："

cin>>v[i].x>>v[i].y

}

triangle.minWeightTriangulation(n,t,s)

triangle.print(s,1,n)

return 0

}

安装 QT 4.6.3

1.安装MinGW，C:\MinGW\bin添加到环境变量。

2.下载 QT 最新版本 4.6.3

3.运行 QT 的安装程序，忽视关于版本兼容性的报警信息

4.打开 Visual Studio的命令提示窗口

cd c:\QT\4.6.3

configure -platform win32-msvc2008

5.configure 完成后，输入 nmake，大概等待5个小时。

6.将 C:\Qt\4.6.3\bin添加到环境变量中

具体什么不太懂，不过我收藏了一个以前别人讲这方面的东西，你看看，希望对你有帮助。

Delaunay三角网是俄国数学家B.Delaunay于1934年发现的。关于Delaunay三角网构建的研究有许多，但由于本课题具有数据量大的特征，不宜直接沿用已有构建方法，笔者针对本课题数据特征，研究获得了适应本课题，速度较快的构建方法。Delaunay三角网有一个特性，每个三角网形成的外接圆都不包含其他参考点。利用这一个性质，我们可以直接构成Delaunay三角网：

一、建立第一个三角形

1、判断用来建立TIN的总脚点数，小于3则报错退出。

2、第一点的选择：

链表的第一节点，命名为Pt1

3、第二点的选择：

A.非Pt1点； B.距Pt1最近

命名为Pt2

4、第三点的选择

A.非Pt1，Pt2点；

B.与Pt1，Pt2点组成的三角形的外接圆内无其他节点；

C.与Pt1，Pt2组成的三角形中的角Pt1Pt3Pt2最大。

命名为Pt3

5、生成三边，加入边表

6、生成第一个三角形，组建三角形表

二、扩展TIN

1、从边表头取一边，要求：该边flag标志为假（只在一个三角形中）

2、从点链表中搜索一点，要求：

A、与边中的Pixel3在边的异侧；

B、该点与边组成的三角形的外接圆内无其他点

C、满足上面两条件的点中角Pt1Pt3Pt2最大的点为Pt3。

3、判断新生成的边，如果边表中没有，则加入边表尾，设定标志flag为假，如果有，则设定该边flag为真。

4、将生成的三角形假如三角形表

5、设定选中的边的标志flag为真

6、转至1，直至边表边的标志flag全部为真。

数据结构：

struct Pixel //脚点数据

{

double x,y,z,g

bool flag

}

struct List //数据链表

{

Pixel *pixel

List *next

}

struct Line //三角形边

{

Pixel *pixel1 //三角形边一端点

Pixel *pixel2 //三角形边另一端点

Pixel *pixel3 //三角形边所对顶点

bool flag

}

struct Linelist //三角形边表

{

Line *line

Linelist *next

}

struct Triangle //三角形表

{

Line *line1

Line *line2

Line *line3

Triangle *next

}

以下是我程序中关于建网的部分：

// DelaunayTIN.cpp: implementation of the CDelaunayTIN class.

//

//////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include "Reconstruction.h"

#include "DelaunayTIN.h"

#include "MyMath.h"

#include <math.h>

#include "ListControl.h"

#ifdef _DEBUG

#undef THIS_FILE

static char THIS_FILE[]=__FILE__

#define new DEBUG_NEW

#endif

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

CDelaunayTIN::CDelaunayTIN()

{

}

CDelaunayTIN::~CDelaunayTIN()

{

}

/////////////////////////////////////////////////////////////////////////////

//函数名： CreateDelaunayTIN

//编写者： Polaris

//参考资料：

//功能： 用给定的数据链表数据，组建Delaunay不规则三角网

//输入参数：数据链表list区域范围(XMin,YMin),(XMax,YMax)

//输出参数：不规则三角网首三角形地址

//备注：

/////////////////////////////////////////////////////////////////////////////

struct Triangle * CDelaunayTIN::CreateDelaunayTIN(List *list)

{

//组建第一个三角形

CMyMath MyMath

CListControl ListControl

struct List *node

struct Pixel *pt1,*pt2,*pt3

bool flag

struct Triangle *TIN

pt1=list->pixel

pt2=list->next->pixel

node=list->next->next

while(node!=NULL)

{

if(MyMath.Calculate2PtDistanceIn3D

(pt1->x,pt1->y,pt1->z,node->pixel->x,node->pixel->y,node->pixel->z)

<MyMath.Calculate2PtDistanceIn3D

(pt1->x,pt1->y,pt1->z,pt2->x,pt2->y,pt2->z))

{

pt2=node->pixel

}

node=node->next

}

node=list->next

pt3=NULL

while(node!=NULL)

{

if(node->pixel==pt1 || node->pixel==pt2)

{

node=node->next

continue

}

if(pt3==NULL)

{

pt3=node->pixel

}

else

{

if((pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,node->pixel->x,node->pixel->y),2)+pow(MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,node->pixel->x,node->pixel->y),2)-pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt2->x,pt2->y),2))/(2*MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,node->pixel->x,node->pixel->y)*MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,node->pixel->x,node->pixel->y))

<(pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt3->x,pt3->y),2)+pow(MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,pt3->x,pt3->y),2)-pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt2->x,pt2->y),2))/(2*MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt3->x,pt3->y)*MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,pt3->x,pt3->y)))

{

pt3=node->pixel

}

}

node=node->next

}

//LineList

Linelist *linehead,*linenode,*linelast

Line *ln1,*ln2,*ln3

linenode=new Linelist

linenode->line=new Line

linenode->line->pixel1=pt1

---