逐点插入法建立Delaunay三角网

<P>逐点插入法进行构网，分析该算法中制约运行速度的因素，在三角网拓扑关系、三角形的查找、LOP算法（Local Optimization Procedure）等方面进行了优化处理，使之有了较高的执行效率。<BR>　　1　数据结构<BR>　　在采用逐点插入进行Delaunay三角剖分的过程中，存在大量的查询操作，利用数据结构提供三角形之间的拓扑信息，能够有效地提高算法效率。边结构应包含点与三角形的信息，三角形结构应包含点与边的信息，再考虑到构网过程中动态的数据更新，算法中采用了双向链表结构，以方便于剖分过程中新旧边（三角形）的添加、删除工作。<BR>　　2　算法原理<BR>　　逐点插入法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：对于已有的三角网络，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。<BR>　　3　算法基本步骤</P>
<P>      a: 点在三角形内，b:点在三角形边上。<BR>　　在按a进行剖分时，添加了三条新边及三个新三角形NT，删除了旧三角形T。同样，在b的情况中，记录点所在的边E，根据拓扑关系，找出该边的左右相邻三角形T1，T2，添加四条新边和四个新三角形NT，删除T1，T2以及边E。<BR>　　构网的关键是对新剖分出的三角形用LOP算法进行优化，其基本过程为：新三角形与周围的三角形构成共用同一条对角线的四边形，逐个对四边形中的两个三角形进行空外接圆检测，如果满足空外接圆准则，则略过。如果不满足，则用另一对角线替换现有对角线，在交换对角线后，又会产生相应的新四边形，继续进行空外接圆检测。这种方法可连续进行,直到全部满足空外接准则为止。这个过程是随着数据点P的逐次插入，与三角剖分同时进行的，可以通过递归调用优化程序来实现。<BR>　　</P>

<img src="images/post/smile/dvbbs/em01.gif" /><img src="images/post/smile/dvbbs/em01.gif" />

<P><img src="images/post/smile/dvbbs/em02.gif" /></P>
<P>支持,顶</P>

<P>谢谢提供信息!</P>
<P>支持以下!</P>

谢谢，能详细点吗？

<img src="images/post/smile/dvbbs/em01.gif" /><img src="images/post/smile/dvbbs/em01.gif" /><img src="images/post/smile/dvbbs/em01.gif" />我顶！！1

<P>谢谢还有吗？</P>

<P>谁有用TIN生成等高线的程序？</P>
<P>不胜感激。</P>

<img src="images/post/smile/dvbbs/em02.gif" /><img src="images/post/smile/dvbbs/em03.gif" /><img src="images/post/smile/dvbbs/em04.gif" /><img src="images/post/smile/dvbbs/em07.gif" /><img src="images/post/smile/dvbbs/em08.gif" />

可否再就数据结构，以及点的查找提供些资料！