基于C号和AutoCAD的Delaunay三角剖分算法的实现.pdf

《基于C号和AutoCAD的Delaunay三角剖分算法的实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3O卷第5期有色矿冶Vo1．3O．№52014年1O月N0N—FERR0USMININGANDMETALLURGYOctober2014文章编号：1007—967X(2O14)O5一O9一O6基于C#和AutoCAD的Delaunay三角剖分算法的实现刘建耀，刘保顺(1．北京科技大学土木与环境工程学院，北京100083；2．中色卢安夏铜业有限公司，赞比亚卢安夏90456)摘要：本文是在．net平台下AutoCAD二次开发方面的文章，是对Delaunay三角剖分算法的总结。在算法的编程实现过程中，作者提出了许多新颖的设想，并最终获得了正确的计算结果

2、和理想的时间效率。针对算法实现的整体框架和步骤，几个算法关键点以及算法的时间复杂度方面，文中提供了比较详细的论述。关键词：三角剖分；边三角形分割关联调整归并；时间复杂度中图分类号：TD171文献标识码：A点集中的两个点构成的一条边，边e的集合为E，那1三角剖分(triangulation)概念么点集V的一个三角剖分T一(V，E)是一个平面1．1三角剖分的概述图G，平面图G满足以下特性：散点集的三角剖分对数值分析以及计算机图形(1)平面图中边的端点都是点集中的点，且点学而言是一项极为重要的数据预处理技术，也是多集中的任一点至少是两条边的端点；年来广泛

3、研究的一个热点算法，具体是指在给定边(2)除了端点相连以外，任两条边都不会相交；界和边界内的一批散乱点的情况下，按照一定的约(3)平面图中的任何三角面，都是由边集E中束条件，使边界点和散乱点共同形成一个三角网框的三条边围成的，任两个三角面都没有重叠区域，且架。三角剖分在矿业软件方面更有着广泛的应用，所有三角面覆盖了整个区域。DTM、等高线、面积、体积的计算都是在剖分后的三Delaunay三角剖分又是三角剖分的一种，其定角形基础上进行的。如图1所示，就是作者编写的义是如果点集V的三角剖分T中的每一条边都是软件对简单连通域内散点集的三角剖分结果。本文D

4、elaunay边，则称这种三角剖分为Delaunay三角只讨论简单连通域的三角剖分，简单连通域是边界剖分，Delaunay边的特性如下：多边形的边之间只是端点首尾相连，任两条边都不如果一条边属于两个三角形，且每个三角形的会相交，并且从边界上的任一点出发，都可以沿着边外接圆都不会把另外一个三角形的第三个顶点包含界到达边界上指定的任何位置。像8字形区域、有在内，则这条边就是Delaunay边。如图2所示。空洞的区域都不是简单连通域。B图2相邻Delaunay三角形图1三角剖分图C点没有被三角形ABD的外接圆包含在内，同1．2三角剖分的定义时A点也没被三

5、角形BCD的外接圆包含在内，则假设V是二维实数域上的有限点集，边e是由边BD就是Delaunay边。在Delaunay三角剖分图*收稿日期：2014—06—19作者简介：刘建耀(1969一)，男，汉族，山西祁县人，测量工程师，工学学士，在职硕士研究生，主要从事露天矿山测量工作。10有色矿冶第3O卷中，边界边不用检查，因为这条边只属于一个三角形。网中，即根据待插入点的Remark属性，删除其所在的三角形，添加三个新三角形，关联和修整新三角2Delaunay三角剖分的实现过程形，使他们融入到当前的三角网中，目的就是保证在2．1实现的手段和目标一个新点插

6、入完成后，当前的三角网始终为Delau—AutoCAD有着强大的图形处理能力，并且nay三角网；AutoDesk公司专门提供了用于二次开发的．net类(6)在插入细部点过程中，因为三角形是动态库，主要就是AutoCAD安装目录下的两个动态链变化的，所以各个三角形与待插入细部点之间的映接库文件aedbmgd．dll和acmgd．dll(Auto射关系也在发生变化，应不断维护这个关系；CAD2013还要加载accoremdg．dl1)。开发工具就(7)在所有的细部点插入完成后，当前的三角是visualstudio2010中的C#语言和AutoCAD，具

7、网就是一个完整的Delaunay三角网，可以通过类的体地讲，就是使用C#语言引用上述两个动态链接属性访问他们。库文件编写一个新的动态链接库文件(*．dl1)，然2．3Delaunay三角网的数据结构后在AutoCAD中加载这个动态链接库文件，使用2．3．1类的设计自定义的命令在AutoCAD中绘出Delaunay三角众所周知，面向对象的编程就是类的设计，编程剖分中的三角形。的过程也是使用现有的类编写新类的过程，而Au—2．2算法的实现步骤toCAD和Microsoft的．net框架有大量优秀的类可实现Delaunay三角剖分从大的方面讲需要如供我们

8、使用，说形象一点，我们是站在巨人的肩膀上下几个步骤：编写程序。为了实现Delaunay三角剖分，新设计的(1)把简单连通域