[求助]如何将一群随机的点连成一个三角网？
<p><strong><font face="楷体_GB2312" size="5">如下图所示，我已经有一个点的选择集SS_point了</font></strong></p><p><strong><font face="楷体_GB2312" size="5">我想的思路是：</font></strong></p>
<p><strong><font face="楷体_GB2312" color="#ff0000" size="5">任意三点，只要其包含的封闭区域不含其他点，</font></strong></p>
<p><strong><font face="楷体_GB2312" color="#ff0000" size="5">那么就可以绘制三角形了</font></strong></p>
<p><strong><font face="楷体_GB2312" color="#ff0000" size="5">好像也不对！</font></strong></p>
<p><strong><font face="楷体_GB2312" size="5">要求已经画过的线不要重复画</font></strong></p>
<p><strong><font face="楷体_GB2312" size="5">完成效果如下图所示：</font></strong></p>
<p> </p>
<p> </p> 本帖最后由 landsat99 于 2022-5-20 11:44 编辑
生成Delaunay三角网，建议CGAL库。 通用c++几何算法库 效率 标准化都不错
接口 ：CGAL::refine_Delaunay_mesh 可有不同特性。
GitHub ： https://github.com/CGAL/cgal 大家的维护热度很高。如有兴趣共同维护、优化 landsat99 发表于 2022-5-20 11:42
生成Delaunay三角网，建议CGAL库。 通用c++几何算法库 效率 标准化都不错
接口 ：CGAL::refine_Delaunay ...
CGAL库提供了不少功能, 个人学习可以. 商用需要授权. lisp创建三角网速度有些慢,参考C++开发的速度:
<p><strong><font face="楷体_GB2312" color="#0000ff" size="5">LSD</font></strong></p>
<p><strong><font face="楷体_GB2312" color="#0000ff" size="5">请问你那个任意随机点形成三角网是如何实现的啊？</font></strong></p>
<p><strong><font face="楷体_GB2312" color="#0000ff" size="5">可以的话共享一下代码或者思路也行啊</font></strong></p>
<p><strong><font face="楷体_GB2312" color="#0000ff" size="5">谢谢！！！</font></strong></p> <p><font face="Verdana" color="#da2549"><b>xyp1964</b></font></p>
<p>版主啊，快快说说看啊</p>
<p>在等着呢！</p> <font face="Verdana">http://mjtd.com/Codes/ArticleShow.asp?ArticleID=1143</font> 对于给定的初始点集P，有多种三角网剖分方式，而Delaunay三角网有以下特性： 1）其Delaunay三角网是唯一的； 2）三角网的外边界构成了点集P的凸多边形“外壳”； 3）没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。 4）如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化”的三角网。下面简要介绍Delaunay三角形产生的基本准则： Delaunay三角形产生准则的最简明的形式是：任何一个Delaunay三角形的外接圆的内部不能包含其它任何点。Lawson提出了最大化最小角原则：每两个相邻的三角形构成的凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。Lawson 又提出了一个局部优化过程LOP（Local Optimization Procedure）方法。如图所示。先求出包含新插入点p的外接圆的三角形，这种三角形称为影响三角形（Influence Triangulation）。删除影响三角形的公共边（图b中粗线），将p与全部影响三角形的顶点连接，完成p点在原Delaunay三角形中的插入。这是我查到的资料
根据snoopychen的程序修改一下即可,没有优化,基本能满足要求来.<br/><font class="Apple-style-span" color="#FF00FF">附件含有源码及测试图.</font><br/><br/><div><br/></div> xshrimp发表于2010-8-4 16:21:00static/image/common/back.gif根据snoopychen的程序修改一下即可,没有优化,基本能满足要求来.附件含有源码及测试图.
<p><strong><font face="楷体_GB2312" size="5">多谢</font></strong></p>
<p><strong><font face="楷体_GB2312" size="5">是可以用，但是很慢啊</font></strong></p>
<p><strong><font face="楷体_GB2312" size="5">有没有更快一点的程序啊</font></strong></p> <p>对于建模用处最大，象CASS的建DTM一样。</p>
<p> </p>
<p>这种遍历，算法最重要。</p> 本帖最后由 作者 于 2010-8-30 18:20:05 编辑 <br /><br /> <p>根据离散点生成三角网试用程序</p>
<p>注：此程序对图元重叠的情况一样可以正常使用，程序执行过程中消除重复图元。</p>
<p> </p>
<p></p>
<p> </p>
<p>以下为此程序演示</p>
<p> </p>
<p></p>
<p> </p>
<p> </p>
<p> </p>
<p>程序实现思路图解（注意与6楼贴子结合着看）：</p>
<p> </p>
<p></p>
<p> </p>
<p>1、通过ssget函数，得到ABCDEFG点选择集m，</p>
<p>2、由ssname函数得到选择集m中第一点A(假设第一点是A)，再从m选择集中找A点的最近点,得到B点(假如A点的最近点为B点），此时形成一条AB边。</p>
<p>3、将AB边左右两侧所有离散点CDEFG，分别与AB边连接形成三角形，判断形成的夹角哪个最大？得到最大夹角的那个三角形BCA(图中所示C点与AB边连接形成夹角最大，第一个三角形成，标示为1边），同时得到新边BC、CA,即1边</p>
<p>4、按逆时针方向，BC方向右侧离散点分别与BC边连接形成三角形，判断形成的夹角哪个最大？得到最大夹角三角形BFC（第二个三角形形成）,同时得到新边BF、FC，即2边。</p>
<p>5、CA方向右侧离散点分别与CA边连接形成三角形，判断形成的夹角哪个最大？得到最大夹角三角CDA（第三个三角形形成）,同时得到新边CD、DA，即2边。</p>
<p>6、此时图中所示的1边均以生成三角形，并得到多个新边2边，此时将1边排除，将2边做为1边，按以上45步骤操作，形成循环......，直到所有边都结束终止循环，形成三角网。</p>