devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

三角网（TIN）生成算法的原理及实现（有代码！！！）_三角网生长算法

作者：Cpp五条 | 2024-06-04 13:40:34

赞

踩

三角网生长算法

前段时间我导给我提出了一个任务，让我提取出离散点的外围边界点。作为技术小白的我，在网上狂搜资料。也走了很多弯路，最终根据Delaunay的三角形的特点（即所有三角形边中，只存在一个三角形中的边即为轮廓边，包含的点即为轮廓点。）来完成。

csdn上也有很多写得很好的博客，我就用自己的想法同时参考《Delaunay 三角网生长算法改进与实现》这篇文章来叙述三角网生长算法的构建过程及原理。同时结合python/C++代码，让大家更好的实现Tin！

闲话少说，TIN三角网的用途博主不再强调，此篇博客主要用于实现三角网！！！

三角网原理

三角网生长法的基本算法思路是：首先找到所有离散点中相距最短的两点，将其连接作为首三角形的初始边（基边）。然后，按照D-TIN判断法找到包含此边的Delaunay三角形的第三点，连接此点与初始边的两个顶点构成首三角形；再按D-TIN判断法以首三角形中另外两条边为基线，分别搜索第三点构成另外两条边的Delaunay三角形，依次循环，直至所有离散点均成为D-TIN的端点。

构网步骤

现假定待构网的离散点的个数为n，下面对三角网生长法的基本步骤进行简单介绍与实现分析：

第一步：在包含n离散点的点集中寻找任意两个点之间的距离最小的点对，将此两点连接起来作为初始基线。

第二步：找首三角形。应用Delaunay判断法在初始基线的右边搜索第三点。D-TIN判断法的具体方法是以基线的两个端点作为向量的起点，依次将其余的未构网的n-2个点作为向量的终点，利用公式（下图）计算两个向量间夹角的余弦值。其中P1和P2分别为基线的两个端点，Pi为还未参与构网的其他点。在这所有的余弦值中，找余弦值最小的点作为首三角形的第三点。

cos \theta =\frac{\overrightarrow{p1pi} * \overrightarrow{p2pi}}{\left |\overrightarrow{p1pi}\right |*\left |\overrightarrow{p2pi} \right |}

第三步：以三角形的三条边为基线，寻找与基线构成三角形的可能的扩展点。一条基线最多是两个三角形的公共边，因此，当基线在寻找可能扩展点的时候，应保证扩展点与基线已构成的三角形的第三点分别位于基线的两侧。否则可能会导致三角形的重叠。以下图（1）的三角形为例，寻找基线T1T2的可能扩展点判断方法如下：

首先给出基线T(1)T(2)的直线方程，记T1(x1, y1), T2(x2, y2)，利用向量的叉乘计算基线的函数方程，直线上任一点(x, y)有： 

f(x,y)=(x-x1,y-y1)\times (x2-x1,y2-y1)

在这里我们可以对未构网的离散点P(x, y)及上图 中T(3)点分别代入直线方程中，并判断f (x, y)的符号，给定以下约定：

若f(p)与f(T(3))同号（即同为正区域或负区域），则P点不是可能扩展点；若f(p)与f(T(3))异号，则P点是可能的扩展点。

第四步：对于可能的扩展点判断是否满足Delaunay原则。此步骤类似于寻找首三角形的第三点，即在所有可扩展点中寻找余弦值最小的点且构成的边不能为重复扩展边。

第五步：重复第三、第四步直到所有点都连线完毕，则构网结束。

C++分步代码

前期准备：需要定义三个类，分别为点类（Point）、线类（Line）、向量类（MyVector）。一个结构体（LineInfo）

  1. # include <iostream>
  2. # include <math.h>
  3. # include <random>
  4. # include <vector>
  5. # include <fstream>
  6. # include <string>
  7. # include <ctime>
  1. class Point {
  2. 	public:
  3. 		double x, y, z;
  4. 		//默认构造函数
  5. 		Point(){};
  6. 		//构造函数
  7. 		Point(double x, double y, double z=0) {
  8. 			this -> x = x;
  9. 			this -> y = y;
  10. 			this -> z = z;
  11. 		}
  12. 		//计算两点间的距离
  13. 		double cal_distence(Point& other) {
  14. 			double distence = 0.0;
  15. 			distence = pow(pow(this->x - other.x, 2) + pow(this->y - other.y, 2), 0.5);
  16. 			return distence;
  17. 		}
  18. 		//重写==
  19. 		bool operator == (const Point& p) {
  20. 			bool b1 = this->x == p.x;
  21. 			bool b2 = this->y == p.y;
  22. 			bool b3 = this->z == p.z;
  23. 			if (b1 and b2 and b3) {
  24. 				return true;
  25. 			}
  26. 			return false;
  27. 		}
  28.  
  29. };
  1. class Line {
  2. 	public:
  3. 		//sametinpt为同一个三角形的顶点(类似原理中的T（3）)
  4. 		Point startpt, endpt, sametinpt;
  5. 		//flag用于判断该边被使用了几次（一个三角形最多只能作为两个三角形的边）
  6. 		int flag;
  7. 		//构造函数
  8. 		Line() {};
  9. 		Line(Point& p1, Point& p2, Point& p3, int flag = 0) {
  10. 			this->startpt = p1;
  11. 			this->endpt = p2;
  12. 			this->flag = flag;
  13. 			this->sametinpt = p3;
  14. 		}
  15. 		//重写==
  16. 		bool operator == (const Line& l) {
  17. 			bool b1 = this->startpt == l.startpt;
  18. 			bool b2 = this->endpt == l.endpt;
  19. 			bool b11 = this->startpt == l.endpt;
  20. 			bool b22 = this->endpt == l.startpt;
  21. 			if ((b1 and b2) or (b11 and b22)) {
  22. 				return true;
  23. 			}
  24. 			return false;
  25. 		}
  26. };
  1. class MyVector {
  2. 	public:
  3. 		Point startpt, endpt;
  4. 		//length为向量的长度
  5. 		double xx, yy, zz, length;
  6. 		//构造函数
  7. 		MyVector() {
  8.  
  9. 		}
  10. 		MyVector(Point& sp, Point& ep) {
  11. 			this->startpt = sp;
  12. 			this->endpt = ep;
  13. 			this->xx = ep.x - sp.x;
  14. 			this->yy = ep.y - sp.y;
  15. 			this->zz = ep.z - sp.z;
  16. 			this->length = pow(pow(this->xx, 2) + pow(this->yy, 2) + pow(this->zz, 2), 0.5);
  17. 		}
  18. 		//两向量间的叉乘
  19. 		double cal_vector(const MyVector& v1) {
  20. 			return this->xx * v1.yy - this->yy * v1.xx;
  21. 		}
  22. 		//两向量间的点乘
  23. 		double cal_number(const MyVector& v1) {
  24. 			return this->xx * v1.xx + this->yy * v1.yy + this->zz * v1.zz;
  25. 		}
  26.  
  27. };
  1. //结构体，用于存储不同类型的值
  2. struct LineInfo
  3. {
  4. 	//count为判断边的已使用次数
  5. 	int count;
  6. 	// index为判断边位于列表中的位置
  7. 	int index;
  8. };

定义三个全局vector变量ptlist(存储所有点)、allline（存储所有边）、baseline（存储所有基线边）

  1. //ptlist用于存储所有点
  2. vector<Point> ptlist;
  3. //allline用于存储所有三角形边
  4. vector<Line> allline;
  5. //baseline用于存储基线边
  6. vector<Line> baseline;

利用random头文件随机生成离散点，用于实验下面：

  1. //随机生成点
  2. void generaterand(int num) {
  3. 	default_random_engine e;
  4. 	uniform_real_distribution<double> u(0.0, 10);
  5. 	e.seed(time(0));
  6. 	for (int i = 0; i < num; i++) {
  7. 		ptlist.push_back(Point(u(e), u(e)));
  8. 	}
  9. }

将离散点中最近的两点找出返回，并在点集中删除这两点

  1. Point* findcloestpt(std::vector<Point>& v) {
  2. 	// 静态变量可以返回
  3. 	static Point cp[2];
  4. 	// 初始化
  5. 	Point p1 = v[0];
  6. 	Point p2 = v[1];
  7. 	int index1 = 0;
  8. 	int index2 = 1;
  9. 	double mindis = p1.cal_distence(p2);
  10. 	//寻找出最近的两个点
  11. 	for (int i = 1; i < v.size() - 1;i++) {
  12. 		for (int j = i + 1; j < v.size(); j++) {
  13. 			double tempdis = v[i].cal_distence(v[j]);
  14. 					if (mindis > tempdis) {
  15. 						p1 = v[i];
  16. 						p2 = v[j];
  17. 						index1 = i;
  18. 						index2 = j;
  19. 						mindis = tempdis;
  20. 					}
  21. 		}
  22. 	}
  23. 	cp[0] = p1;
  24. 	cp[1] = p2;
  25. 	// 将两点从点列表中删除
  26. 	v.erase(v.begin() + index1);
  27. 	// 注意！！！！这里-1是因为上面已经删了一个点，所有它的索引随之减小了一个
  28. 	v.erase(v.begin() + index2-1);
  29. 	cout << "最短距离为：" << mindis << endl;
  30.  
  31. 	return cp;
  32. }

根据余弦定理公式 ，分别与剩余点计算，找出最小的余弦值的点，组成第一个三角形。

  1. void findfirsttin(Point& p1, Point& p2, std::vector<Point>& v) {
  2. 	// 初始化
  3. 	MyVector mv1, mv2;
  4. 	int index = 0;
  5. 	mv1 = MyVector(p1, v[0]);
  6. 	mv2 = MyVector(p2, v[0]);
  7. 	double cos00 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
  8. 	// 循环找出最小的余弦值
  9. 	for (int i = 1; i < v.size(); i++) {
  10. 		mv1 = MyVector(p1, v[i]);
  11. 		mv2 = MyVector(p2, v[i]);
  12. 		double cos0 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
  13. 		if (cos0 < cos00) {
  14. 			cos00 = cos0;
  15. 			index = i;
  16. 		}
  17. 	}
  18. 	// 形成三条边，同时存入allline和baseline
  19. 	Line line1 = Line(p1, p2, ptlist[index], 1);
  20. 	Line line2 = Line(p1, ptlist[index], p2, 1);
  21. 	Line line3 = Line(p2, ptlist[index], p1, 1);
  22. 	allline = { line1, line2, line3 };
  23. 	baseline = { line1, line2, line3 };
  24. 	cout << "第一个三角形已经寻找成功" << endl;
  25. 	cout << "三角形总边数为：" << allline.size() << endl;
  26. }

我们在进行下面的建网过程会碰到一个问题，就是如何判断这个边它在整个三角形网中的使用次数？很简单的，我们利用前文Line类中的flag属性即可；具体判断函数代码如下：

  1. struct LineInfo lineusedcount(Line& line, std::vector<Line>& v) {
  2. 	// 结构体用于返回信息
  3. 	LineInfo lineinfo;
  4. 	// 与allline中每条边判断
  5. 	for (int i = 0; i < v.size(); i++) {
  6. 		// 我们已在Line类中重写了==
  7. 		if (line == v[i]) {
  8. 			// 如果该边已经使用了两次，即已经存在于两三角形中
  9. 			if (v[i].flag == 2) {
  10. 				lineinfo.count = 2;
  11. 				lineinfo.index = i;
  12. 				return lineinfo;
  13. 			}
  14. 			// 如果该边只存在于一个三角形内
  15. 			else
  16. 			{
  17. 				lineinfo.count = 1;
  18. 				lineinfo.index = i;
  19. 				return lineinfo;
  20. 			}
  21. 		}
  22. 	}
  23. 	// 如果这条边是新边，即allline表中没有它
  24. 	lineinfo.count = 0;
  25. 	lineinfo.index = -1;
  26. 	return lineinfo;
  27. }

 构网

  1. void creatTin(std::vector<Line>& va, std::vector<Line>& vb,std::vector<Point>& vp) {
  2. 	//建网结束的标志就是基线表baseline不存在元素了
  3. 	while (vb.size())
  4. 	{
  5. 		// 依次对基线表中的基线进行扩展
  6. 		Line baseline = vb[0];
  7. 		// 如果该基线虽然还没有扩展，但是其它基线边扩展的过程中已经产生了它2次，那它将不会进行扩展
  8. 		// 因为一条边 最多 存在于两个三角形内
  9. 		if (lineusedcount(baseline, va).count==2) {
  10. 			vb.erase(vb.begin());
  11. 			continue;
  12. 		}
  13. 		// 寻找第三点
  14. 		while (true)
  15. 		{
  16. 			// potential用于存储可能的扩展点
  17. 			std::vector<Point> potentialpt;
  18. 			double re1 = MyVector(baseline.startpt, baseline.endpt).cal_vector(MyVector(baseline.startpt, baseline.sametinpt));
  19. 			for (int i = 0; i < vp.size(); i++) {
  20. 				double re2 = MyVector(baseline.startpt, baseline.endpt).cal_vector(MyVector(baseline.startpt, vp[i]));
  21. 				// 异号才可能是扩展边
  22. 				if (re1 * re2 < 0) {
  23. 					potentialpt.push_back(vp[i]);
  24. 				}
  25. 			}
  26. 			// 如果列表为0。及该基线可能为最外层的边，它的一边不存在点了
  27. 			if (potentialpt.size() == 0) {
  28. 				vb.erase(vb.begin());
  29. 				break;
  30. 			}
  31. 			// 找出最小的余弦值
  32. 			MyVector mv1, mv2;
  33. 			int index=0;
  34. 			mv1 = MyVector(baseline.startpt, potentialpt[0]);
  35. 			mv2 = MyVector(baseline.endpt, potentialpt[0]);
  36. 			double cos00 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
  37. 			for (int i = 1; i < potentialpt.size(); i++) {
  38. 				mv1 = MyVector(baseline.startpt, potentialpt[i]);
  39. 				mv2 = MyVector(baseline.endpt, potentialpt[i]);
  40. 				double cos0 = mv1.cal_number(mv2) / (mv1.length * mv2.length);
  41. 				if (cos0 < cos00) {
  42. 					cos00 = cos0;
  43. 					index = i;
  44. 				}
  45. 			}
  46. 			// 组成可能的扩展边
  47. 			Line newl1 = Line(baseline.startpt, potentialpt[index], baseline.endpt, 1);
  48. 			Line newl2 = Line(baseline.endpt, potentialpt[index], baseline.startpt, 1);
  49.  
  50. 			LineInfo info1 = lineusedcount(newl1, va);
  51. 			// 如果是“新出现”的边，同时加入allline和baseline
  52. 			if (info1.count == 0) {
  53. 				va.push_back(newl1);
  54. 				vb.push_back(newl1);
  55. 			}
  56. 			// 否则将其flag的值改为2
  57. 			else
  58. 			{
  59. 				vb.push_back(newl1);
  60. 				va[info1.index].flag = 2;
  61. 			}
  62. 			LineInfo info2 = lineusedcount(newl2, va);
  63. 			if (info2.count == 0) {
  64. 				va.push_back(newl2);
  65. 				vb.push_back(newl2);
  66. 			}
  67. 			else
  68. 			{
  69. 				vb.push_back(newl2);
  70. 				va[info2.index].flag = 2;
  71. 			}
  72. 			// 基线边只要经过一次扩展，肯定存在于两三角形内
  73. 			va[lineusedcount(baseline, va).index].flag = 2;
  74. 			vb.erase(vb.begin());
  75. 			break;
  76. 		}
  77. 		//cout << vb.size() << endl;
  78. 	}
  79. 	cout << "构网结束！" << endl;
  80. }

主函数main

  1. int main(){
  2. 	generaterand(1000);
  3. 	cout << "列表个数为：" << ptlist.size() << std::endl;
  4. 	fstream file;
  5. 	file.open("H:\\points.txt", ios::out);
  6. 	for (int i = 0; i < ptlist.size(); i++) {
  7. 		file << to_string(ptlist[i].x) << "," << to_string(ptlist[i].y) << "\n";
  8. 	}
  9. 	file.close();
  10. 	cout << "原始点存储成功" << endl;
  11. 	/*vector<int> a = { 1,2,3,4,5 };
  12. 	a.erase(a.begin() + 2);
  13. 	for (int i = 0; i < a.size(); i++) {
  14. 		cout << a[i] << endl;
  15. 	}*/
  16. 	
  17. 	Point *ccpp;
  18. 	double st = clock();
  19. 	ccpp = findcloestpt(ptlist);
  20. 	cout << "列表个数为：" << ptlist.size() << std::endl;
  21. 	cout << "相邻两点第一个点的坐标为：" << ccpp->x <<","<< ccpp->y << endl;
  22. 	cout << "相邻两点第二个点的坐标为：" << (ccpp+1)->x << ","<<(ccpp + 1)->y << endl;
  23. 	findfirsttin(*ccpp, *(ccpp + 1), ptlist);
  24. 	creatTin(allline, baseline, ptlist);
  25. 	cout << "构网用时：" << clock() - st << "ms" << endl;
  26. 	cout << "三角形总边数为：" << allline.size() << endl;
  27. 	
  28. 	return 0;
  29. }

构建的三角网 

此章结束，博主叙述难免会有遗漏或疏忽，大家如果有啥疑惑可以留言沟通。同时如果需要python版本的程序，我会近期出一期相关博客！ 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/672093
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号