平面域Delaunay三角網(wǎng)點定位算法研究綜述

劉琴琴

（陜西師范大學(xué) 計算機科學(xué)學(xué)院，陜西 西安710062）

平面域Delaunay三角網(wǎng)點定位算法研究綜述

劉琴琴

（陜西師范大學(xué) 計算機科學(xué)學(xué)院，陜西 西安710062）

不規(guī)則三角網(wǎng)常用于地形的可視化，其生成算法一直是國內(nèi)研究熱點。Delaunay三角剖分算法是構(gòu)建不規(guī)則三角網(wǎng)的主要算法。討論了平面域離散點生成Delaunay三角網(wǎng)算法的研究現(xiàn)狀，其中逐點插入法中影響構(gòu)網(wǎng)效率的關(guān)鍵因素是任意插入點定位的速度。總結(jié)了目前國內(nèi)主流的點定位算法，對國內(nèi)該領(lǐng)域現(xiàn)有文獻研究存在的主要問題作了詳細分析，并展望了未來可能的研究走向，以期為國內(nèi)Delaunay三角網(wǎng)生成算法研究提供理論與方法上的指導(dǎo)意見。

Delaunay；不規(guī)則三角網(wǎng)；逐點插入法；點定位

在地理信息系統(tǒng)中，數(shù)字高程模型最基本和最重要的模型是不規(guī)則三角網(wǎng) （Triangulated Irregular Network，TIN）模型。不規(guī)則三角網(wǎng)是由不規(guī)則的離散點生成互不交叉、互不重疊又相互鄰接的連續(xù)三角形來擬合地形的[1-2]。由于Delaunay三角網(wǎng)[3]具有唯一性、空外接圓和最大的最小內(nèi)角等性質(zhì)，所以在一般情況下，Delaunay三角網(wǎng)被公認為是所有構(gòu)網(wǎng)規(guī)則中最優(yōu)的[4]，因此被廣泛應(yīng)用。

Delaunay三角網(wǎng)生成算法經(jīng)過20多年的研究已取得了豐富的研究成果，按照構(gòu)網(wǎng)過程的不同，主要可分為三角網(wǎng)生長法[5]、分治算法[6]和逐點插入法[7]，采用后兩種以及兩種結(jié)合算法較多。

三角網(wǎng)生長法構(gòu)網(wǎng)步驟相對簡單，時間效率較差，平均時間復(fù)雜度為O（n2）[8]，現(xiàn)應(yīng)用很少。

分治算法構(gòu)建三角網(wǎng)思路簡單，運行速度較快，構(gòu)網(wǎng)費時與離散點數(shù)基本成正比[9]，其缺點是需占用大量的內(nèi)存來存儲空間，相對復(fù)雜。……