一种基于最小搜索圆平面多边形域约束Delaunay三角剖分算法  

Constrained Delaun Triangulation Algorithm for Planar Polygonal Domains Based on Minimum Search Circle

作　　者：陈学工[1] 马金金[1] 黄伟[1] 李楠[2] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083 [2]中国地质科学院矿产资源研究所,北京100037

出　　处：《小型微型计算机系统》2011年第2期374-378,共5页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划项目(2006AA06Z114)资助

摘　　要：给出一种新的基于边优先的二维多边形域任意散乱数据的约束Delaunay三角剖分算法.算法结合网格分块技术,提出基于最小搜索圆的点搜索思想,并证明了该思想的正确性,有效地提高了搜索"第三点"的速度.算法中散乱数据可以是任意复杂的折线、封闭多边形环及离散点.另外,在三角剖分过程中,实时地去掉封闭点和封闭边,极大地加快了构网速度,实现了平面多边形域散乱数据的快速约束Delaunay三角化.This paper presents a new algorithm based on the edge priority for Constrained Delaunay Triangulation of arbitrary data scattered in 2D region with polygonal boundary. Combining with grid partition technology, the new algorithm presents the point searching idea based on minimum search circle. The new idea is proved correctly and improves the speed of searching the third point effective- ly. The characteristic constraints of the data could be complicated broken lines, closed polygons and scatter points. Besides , removing the occluded edges and occluded points can accelerate the speed of triangulation and realize the Constrained Delaanay Triangulation fast.

关 键 词：约束DELAUNAY三角化 分块技术 最小搜索圆 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]