DELAUNAY三角网算法是什么东西呢。。。大概就是对于许多密集的点，，，可以形成一个三角网。。然后最近的三个点搞成一个三角形。任何一个三角形的外接圆都不包含其他的点。并且没有相交边，并且所有三角面的合集就是一个凸包。，Delaunay三角剖分所形成的三角形的最小角最大。
1.最接近：以最近的三点形成三角形，且各线段(三角形的边)皆不相交。
2.唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3.最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4.最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5.区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。
算法不久之后实现 = = #include<bits/stdc++.h>
using namespace std;
#define PI 3.1415926
struct triangleNode
{
double coordinateX[3],coordinateY[3]; //坐标
double triangleLength; //周长
double triangleArea; //面积
double triangSideleLength[3]; //边长
};
struct pointNode
{
double x,y;
};
double dist(double xx,double yy,double xxx,double yyy)
{
return sqrt((xx-xxx)*(xx-xxx)+(yy-yyy)*(yy-yyy));
}
double getTriangleCircumcircleRadius(triangleNode a) //外接圆半径
{
a.triangSideleLength[0]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[1],a.coordinateY[1]);
a.triangSideleLength[1]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[2],a.coordinateY[2]);
a.triangSideleLength[2]=dist(a.coordinateX[2],a.coordinateY[2],a.coordinateX[1],a.coordinateY[1]);
double triangleCircumcircleRadius=0.5*(sqrt((a.triangSideleLength[0]+a.triangSideleLength[1]-a.triangSideleLength[2])
*(a.triangSideleLength[0]-a.triangSideleLength[1]+a.triangSideleLength[2])
*(a.triangSideleLength[1]+a.triangSideleLength[2]-a.triangSideleLength[0]))
/(a.triangSideleLength[0]+a.triangSideleLength[1]+a.triangSideleLength[2]));
return triangleCircumcircleRadius;
}
double getTriangleCircumcircleLength(triangleNode a) //外接圆周长
{
return 2*PI*getTriangleCircumcircleRadius(a);
}
double getTriangleCircumcircleArea(triangleNode a) //外接圆面积
{
return PI*getTriangleCircumcircleRadius(a)*getTriangleCircumcircleRadius(a);
}
double getTriangleLength(triangleNode a) //三角形周长
{
a.triangSideleLength[0]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[1],a.coordinateY[1]);
a.triangSideleLength[1]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[2],a.coordinateY[2]);
a.triangSideleLength[2]=dist(a.coordinateX[2],a.coordinateY[2],a.coordinateX[1],a.coordinateY[1]);
return a.triangSideleLength[0]+a.triangSideleLength[1]+a.triangSideleLength[2];
}
double getTriangleArea(triangleNode a) //三角形面积
{
a.triangSideleLength[0]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[1],a.coordinateY[1]);
a.triangSideleLength[1]=dist(a.coordinateX[0],a.coordinateY[0],a.coordinateX[2],a.coordinateY[2]);
a.triangSideleLength[2]=dist(a.coordinateX[2],a.coordinateY[2],a.coordinateX[1],a.coordinateY[1]);
double halfPerimeter=getTriangleArea(a)*0.5; //半周长
return sqrt(halfPerimeter*(halfPerimeter-a.triangSideleLength[0])*(halfPerimeter-a.triangSideleLength[1])*(halfPerimeter-a.triangSideleLength[2])); //海伦公式
}
int main()
{
}
版权声明：本文为sky_miange原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。