基于海量數(shù)據(jù)的二維凸包快速生成算法

馬 駿，藺東杰，凌廣明

(1.河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475004; 2.河南大學(xué) 軟件學(xué)院，河南 開封 475004)

基于海量數(shù)據(jù)的二維凸包快速生成算法

馬 駿1，藺東杰1，凌廣明2

(1.河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475004; 2.河南大學(xué) 軟件學(xué)院，河南 開封 475004)

凸包算法是計(jì)算機(jī)幾何的基本問題之一，在很多領(lǐng)域應(yīng)用廣泛。傳統(tǒng)的凸包生成算法在處理大容量數(shù)據(jù)時(shí)，表現(xiàn)出的時(shí)間復(fù)雜度相對(duì)較高而且凸包生成速率較低，已經(jīng)不能滿足實(shí)際海量數(shù)據(jù)的需求。為解決這一問題，提出了一種面對(duì)海量數(shù)據(jù)的快速凸包生成算法。該算法通過對(duì)散亂點(diǎn)集分區(qū)、一遍掃描排序，確定散亂點(diǎn)集邊界，快速處理邊界點(diǎn)集中處于共線的點(diǎn)等一系列預(yù)處理操作，快速排除凸包內(nèi)部的點(diǎn)，縮小了問題規(guī)模，避免了對(duì)不在凸包上的點(diǎn)集的掃描處理，明顯地縮短了凸包的求取時(shí)間，可保證最小凸包的快速生成。該算法極其簡(jiǎn)單，時(shí)間復(fù)雜度較低，理論上可達(dá)到o(nlogn)，有利于凸包生成速度的提高。與傳統(tǒng)算法進(jìn)行了同步對(duì)比實(shí)驗(yàn)，結(jié)果表明，該算法運(yùn)行有效性較好，且具有較好的應(yīng)用前景。

凸包；海量；平面點(diǎn)集；預(yù)處理；排序；快速

0 引 言

凸包是指包含平面點(diǎn)集內(nèi)所有點(diǎn)并且頂點(diǎn)屬于平面點(diǎn)集的最小簡(jiǎn)單凸多邊形。它作為計(jì)算幾何的基本單元之一，廣泛應(yīng)用于圖像處理、模式識(shí)別、地理信息系統(tǒng)、人工智能等領(lǐng)域。對(duì)于凸包的研究，一直是計(jì)算

幾何領(lǐng)域研究的熱點(diǎn)之一[1]。

自20世紀(jì)60年代末,貝爾實(shí)驗(yàn)室要求求解10 000個(gè)點(diǎn)的凸包?！?br>