【摘 要】對凸多邊形頂點排序問題做深入分析，提出一種基于矢量方向比較的凸多邊形頂點排序分治算法。首先深入分析凸多邊形頂點排序問題的背景；其次提出基于矢量方向比較的凸多邊形頂點排序分治算法；最后通過C++編程實現(xiàn)該算法，并分析該算法的時間復(fù)雜度和空間復(fù)雜度。該算法已經(jīng)應(yīng)用在實際項目中，證明該算法是簡單高效的。

【關(guān)鍵詞】凸多邊形 頂點排序 凸包問題 分治算法

一、問題描述

（一）凸包問題和凸多邊形定義

凸包問題[1]是計算機(jī)圖形學(xué)中一個很重要的基礎(chǔ)問題，在GIS、CAD等領(lǐng)域有廣泛的應(yīng)用。對凸包問題的求解有不少高效算法，例如卷包裹算法[2]，分治算法[3]等。簡單多邊形[4]的凸包問題是其中一個特例，而凸多邊形頂點排序問題又是簡單多邊形凸包問題的一個特例，目前對其研究不多。下面給出凸多邊形的嚴(yán)格定義。

[定義1]在一個簡單多邊形中，如果所有頂點都是凸頂點[5]，則稱該多邊形是一個凸多邊形。

（二）凸多邊形頂點排序問題

作者在開發(fā)有限元系統(tǒng)時遇到這樣的問題，一個空間六面體網(wǎng)格單元被一個平面切割， 12條邊可能與切割面相交于n（3<=n<=6）個點，n點連接后必然形成一個凸多邊形。

六面體與平面相交后只有n個交點的坐標(biāo)信息，頂點的連接順序就是我們要解決的凸多邊形頂點排序問題。

二、算法分析

首先可以簡化問題：當(dāng)切平面與某坐標(biāo)平面不垂直時，可以將n個交點投影到該坐標(biāo)平面（例如xoy平面）上，這樣將三維問題簡化為二維問題。

在二維坐標(biāo)平面上的n個點排序就是一個典型的凸包問題，我們提出一種全新的快速分治算法?；A(chǔ)思想就是找一個凸多邊形的內(nèi)部點，然后將該點與所有n個頂點連接形成n個矢量，最后根據(jù)矢量與坐標(biāo)軸夾角將n個點排序。假設(shè)P為凸多邊形內(nèi)部任意點，PQ為x軸正方向，A到F是凸多邊形的6個頂點。顯然按照PA、PB等矢量方向與PQ的逆時針夾角從小到大的順序，可以將所有6個頂點逆時針排序，反之亦可。

該算法具體實現(xiàn)時，有以下幾個問題需要解決。

（一）如何選擇投影坐標(biāo)面。

任取三個頂點所在平面與某坐標(biāo)面不垂直時，我們可以投影到該坐標(biāo)面。一個平面不可能同時與三個坐標(biāo)面垂直，所以總能找到一個坐標(biāo)面來投影。計算可以利用叉積求法向量的方式，但是該方式計算量大，我們可以逆用如下定理。

[定理1]：任取三點的xy坐標(biāo)比值相同，則該平面必然垂直于xoy平面。

簡單證明如下：當(dāng)（Xa/Ya） = （Xb/Yb） = （Xc/Yc）時，a、b、c三點在xoy平面上的投影共線，則a、b、c三點所在平面垂直于xoy面。同理可得到xoz和yoz平面的類似結(jié)論。

（二）如何選擇凸多邊形內(nèi)部點。

任取三頂點，求其幾何中心P，則P點必然在凸多邊形內(nèi)。如公式（2.1）所示。

Xp=（Xa+Xb+Xc）/3

Yp=（Ya+Yb+Yc）/3

Xp=（Ya+Yb+Yc）/3 （2.1）

（三）如何對各頂點排序。

夾角的cos值在[0，π]之間隨角度增大而減小，[π，2π]之間隨角度增大而增大。因此，我們在對所有點排序前，需要將全部點分為兩個子集。以在xoy平面的投影為例，按照y坐標(biāo)是否大于P點可以將全部點分為“上部點”（例如{ABC}）和“下部點”（例如{DEF}）兩個子集。對“上部點”我們按照cos值降序排列，對“下部點”按照cos值升序排列，這樣就得到全部點的排列。而這種將問題分解，減小問題規(guī)模分而治之的思想正是典型的“分治”算法。cos值可以按照公式（2.2）求得。

cos（QPA）=（Xa-Xp）/（Ya-Yp） （2.2）

三、算法實現(xiàn)和復(fù)雜度分析

在c++中函數(shù)的聲明形式為：int sortpolynode（int n， double *nodes）。其中函數(shù)返回值為排序的頂點數(shù)，返回值為-1時表示函數(shù)出錯。參數(shù)n為多邊形的頂點數(shù)，nodes是一個長度為3n的數(shù)組，存儲n個頂點排序前的xyz坐標(biāo)；排序后的頂點坐標(biāo)仍然放在該數(shù)組中，實現(xiàn)數(shù)據(jù)的輸出。

算法定義的輔助變量主要包括幾個double類型的vector，包括upnodes、downnodes、upcoss、downcoss。前兩個分別存儲上部點和下部點的坐標(biāo)，后兩個存對應(yīng)頂點與內(nèi)部點P形成的矢量與橫坐標(biāo)正方向夾角的余弦值。前兩個vector長度相加為3n，后兩個相加等于n，另外還需要一些零散輔助空間，所以算法的空間復(fù)雜度為O（n）。

算法運行時，需要四個重要的循環(huán)。第一個循環(huán)次數(shù)為n，將n個頂點按照是否高于內(nèi)部點p的縱坐標(biāo)劃分到“上部點”upnodes和“下部點”downnodes中。第二個循環(huán)次數(shù)為n，用于求所有頂點的cos值。第三個循環(huán)利用選擇法或起泡法對upnodes、downnodes、upcoss和downcoss排序，循環(huán)次數(shù)為：（n-1）！=n（n-1）/2。第四個循環(huán)用于將upnodes和downnodes數(shù)據(jù)復(fù)制回nodes中作為函數(shù)輸出，循環(huán)次數(shù)為n。所以整個算法的時間復(fù)雜度為O（n^2）。

四、結(jié)語

通過上述分析可知，該算法時空效率都很高。該算法已經(jīng)應(yīng)用在實際項目中，實踐證明該算法是準(zhǔn)確高效的。

參考文獻(xiàn)：

[1] （美）萊維丁.算法設(shè)計與分析基礎(chǔ)[M].北京：清華大學(xué)出版社，2007：53-105.

[2] 宋麗，姜旭東.卷包裹法求凸包問題算法分析與程序?qū)崿F(xiàn)[J].牡丹江師范學(xué)院學(xué)報（自然科學(xué)版）， 2005， 04期：18-19.

[3] 劉新，劉任任.一種改進(jìn)的構(gòu)建凸包的分治算法[J].計算機(jī)工程與科學(xué)，2006，vol.28， NO.8：63-65.

[4] 劉潤濤.簡單多邊形凸包的算法[J].哈爾濱理工大學(xué)學(xué)報，2002，vol.7，NO.2：98-100.

[5] 吳尚智.一種求簡單多邊形凸包的算法[J].甘肅科學(xué)學(xué)報，2000，vol.12，NO.4：11-13.