[求助]如何将一群随机的点连成一个三角网？

santalin

如下图所示，我已经有一个点的选择集SS_point了

我想的思路是：

任意三点，只要其包含的封闭区域不含其他点，

那么就可以绘制三角形了

好像也不对！

要求已经画过的线不要重复画

完成效果如下图所示：

 

 

landsat99

生成Delaunay三角网，建议CGAL库。 通用c++几何算法库 效率 标准化都不错

接口 ：CGAL::refine_Delaunay_mesh 可有不同特性。

GitHub ： https://github.com/CGAL/cgal   大家的维护热度很高。如有兴趣共同维护、优化

SdlFreeCAD

landsat99 发表于 2022-5-20 11:42
生成Delaunay三角网，建议CGAL库。 通用c++几何算法库 效率 标准化都不错

接口 ：CGAL::refine_Delaunay ...

CGAL库提供了不少功能, 个人学习可以. 商用需要授权.

SdlFreeCAD

lisp创建三角网速度有些慢,参考C++开发的速度:

xyp1964

santalin

LSD

请问你那个任意随机点形成三角网是如何实现的啊？

可以的话共享一下代码或者思路也行啊

谢谢！！！

santalin

xyp1964

版主啊，快快说说看啊

在等着呢！

Gu_xl

http://mjtd.com/Codes/ArticleShow.asp?ArticleID=1143

santalin

1. 对于给定的初始点集P，有多种三角网剖分方式，而Delaunay三角网有以下特性： 1）其Delaunay三角网是唯一的； 2）三角网的外边界构成了点集P的凸多边形“外壳”； 3）没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。 4）如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化”的三角网。下面简要介绍Delaunay三角形产生的基本准则： Delaunay三角形产生准则的最简明的形式是：任何一个Delaunay三角形的外接圆的内部不能包含其它任何点[Delaunay 1934]。Lawson[1972]提出了最大化最小角原则：每两个相邻的三角形构成的凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。Lawson [1977]又提出了一个局部优化过程LOP（Local Optimization Procedure）方法。如图所示。先求出包含新插入点p的外接圆的三角形，这种三角形称为影响三角形（Influence Triangulation）。删除影响三角形的公共边（图b中粗线），将p与全部影响三角形的顶点连接，完成p点在原Delaunay三角形中的插入。

复制代码

这是我查到的资料

xshrimp

根据snoopychen的程序修改一下即可,没有优化,基本能满足要求来.
附件含有源码及测试图.

santalin

xshrimp发表于2010-8-4 16:21:00根据snoopychen的程序修改一下即可,没有优化,基本能满足要求来.附件含有源码及测试图.

多谢

是可以用，但是很慢啊

有没有更快一点的程序啊

NetBee

对于建模用处最大，象CASS的建DTM一样。

 

这种遍历，算法最重要。

ljttjl

根据离散点生成三角网试用程序

注：此程序对图元重叠的情况一样可以正常使用，程序执行过程中消除重复图元。

 

 

以下为此程序演示

 

 

 

 

程序实现思路图解（注意与6楼贴子结合着看）：

 

 

1、通过ssget函数，得到ABCDEFG点选择集m，

2、由ssname函数得到选择集m中第一点A(假设第一点是A)，再从m选择集中找A点的最近点,得到B点(假如A点的最近点为B点），此时形成一条AB边。

3、将AB边左右两侧所有离散点CDEFG，分别与AB边连接形成三角形，判断形成的夹角哪个最大？得到最大夹角的那个三角形BCA(图中所示C点与AB边连接形成夹角最大，第一个三角形成，标示为1边），同时得到新边BC、CA,即1边

4、按逆时针方向，BC方向右侧离散点分别与BC边连接形成三角形，判断形成的夹角哪个最大？得到最大夹角三角形BFC（第二个三角形形成）,同时得到新边BF、FC，即2边。

5、CA方向右侧离散点分别与CA边连接形成三角形，判断形成的夹角哪个最大？得到最大夹角三角CDA（第三个三角形形成）,同时得到新边CD、DA，即2边。

6、此时图中所示的1边均以生成三角形，并得到多个新边2边，此时将1边排除，将2边做为1边，按以上45步骤操作，形成循环......，直到所有边都结束终止循环，形成三角网。