双向分块快速Delaunay三角剖分算法  

A Speeding Double Direction Marking Block Algorithm for Delaunay Triangulation

作　　者：占自才[1] 

机构地区：[1]华东交通大学电气与电子工程学院,江西南昌330013

出　　处：《华东交通大学学报》2005年第4期106-109,共4页Journal of East China Jiaotong University

摘　　要：介绍一种双向分块快速Delaunay平面剖分算法,该算法有别于其他的分治算法,其特点是运算速度快,时间度为O(Nlog2N),算法易于理解和实现.该算法在二维平面中首先把被三角剖分的点集均匀分为多个只有3点(最多有一个块不是3个点)的点块.首先对每一个点块进行Delaunay三角剖分,再对相邻的点块中三角剖分进行合并.并介绍了该算法的数据结构,充分说明了该算法的可操作性.This paper introduces a speeding double direction marking block Algorithm for Delaunay Triangulation. Differing from other Algorithm, its characteristics is speediness of calculating, having time degree for O（Nlog2N） and easy realization of the designs. The scattered data points are divided a lot of point-blocks and every one has only three points or two points. We process Delaunay Triangulation about every point-block and merge them which are conjoint in place. Then the paper introduces the data structures about the Algorithm and explains its maneuverability.

关 键 词：双向分块 快速 合并 三角剖分 数据结构 

分 类 号：O189.11[理学—数学]