四節(jié)點(diǎn)四邊形網(wǎng)格單元中一種新的云圖生成算法

【摘要】 在三節(jié)點(diǎn)三角形網(wǎng)格單元基礎(chǔ)上，分析四節(jié)點(diǎn)四邊形單元特點(diǎn)，提出一種新的云圖算法，可以有效提高云圖生成效率。首先將等值線對四邊形網(wǎng)格單元的切割過程劃分為四種基本形式，又將每種基本形式的所有可能處理路徑一一分析處理。其次針對四邊形網(wǎng)格單元可能存在的二義性問題做專門討論，簡化了處理流程。該算法已在項目中實(shí)際應(yīng)用，應(yīng)用結(jié)果表明該算法是準(zhǔn)確和高效的。

【關(guān)鍵詞】 分割窮舉算法 四節(jié)點(diǎn)四邊形網(wǎng)格單元 云圖 等值線 等值多邊形

一、引言

三節(jié)點(diǎn)三角形網(wǎng)格單元中的云圖分割窮舉算法，在作者之前的文章中已經(jīng)詳細(xì)論述過[1]。四節(jié)點(diǎn)四邊形網(wǎng)格單元也是一種應(yīng)用廣泛的單元類型，其中的云圖技術(shù)既有和三角形單元相同之處，也有他的特點(diǎn)。相同之處在于，四節(jié)點(diǎn)四邊形單元中的分割窮舉算法仍然是基于等值線網(wǎng)格序列法[1]的，其次等值線對網(wǎng)格單元的分割仍然按照一定的規(guī)律排列，所以我們?nèi)耘f可以利用分割窮舉的思想對四邊形網(wǎng)格單元中的等值線數(shù)據(jù)進(jìn)行排序，最終生成四邊形單元中的等值多邊形數(shù)據(jù)，最終形成云圖數(shù)據(jù)。而區(qū)別首先在于四節(jié)點(diǎn)網(wǎng)格單元中等值線對網(wǎng)格單元的劃分形式更復(fù)雜，其次在于由于等值線數(shù)據(jù)二義性[2]的存在，對等值線數(shù)據(jù)的排序更復(fù)雜。

二、問題描述

和三角形網(wǎng)格類似，四邊形網(wǎng)格中的所有單元經(jīng)過網(wǎng)格序列法處理，已經(jīng)生成了等值線數(shù)據(jù)，并以網(wǎng)格單元為單位組織存儲。如圖1所示，為四邊形網(wǎng)格中幾種可能 的等值 線分布形式。

可以證明，與三角形網(wǎng)格單元類似，四邊形網(wǎng)格單元內(nèi)部等值點(diǎn)的排列仍然符合如下下面兩條定理：

[定理1] 等值點(diǎn)按照場值由小到大排列。

[定理2] 等值點(diǎn)按照所在網(wǎng)格邊編號由小到大排列。

這里對網(wǎng)格邊編號定義為：由頂點(diǎn)0和頂點(diǎn)1所夾邊為邊0，由頂點(diǎn)1和頂點(diǎn)2所夾邊為邊1，由頂點(diǎn)2和頂點(diǎn)3所夾邊為邊2，由頂點(diǎn)3和頂點(diǎn)0所夾邊為邊3。例如圖1（a）中，場值最小的等值線1與邊1和邊2的交點(diǎn)為第1和第2個等值點(diǎn)，場值次小的等值線2與邊1和邊2的交點(diǎn)為第3和第4個等值點(diǎn)，等等依此類推。

基于上述兩點(diǎn)規(guī)律，在沒有二義性時，四邊形網(wǎng)格單元與三角形單元類似，其中等值線與網(wǎng)格的相交必定是按照一個固定方向進(jìn)行的，與圖1（a） 、1（b）和圖1（c）中所示。但是與三角形網(wǎng)格單元不同，四邊形網(wǎng)格中一條等值線可能與網(wǎng)格單元存在四個交點(diǎn)。這就是四邊形網(wǎng)格中二義性問題，二義性會帶來等值線走向判斷的問題，該問題已有很好的解決方案，例如文獻(xiàn)中提到的投影不相交原理[2]。但二義性同時會導(dǎo)致等值線與四邊形網(wǎng)格不按固定方向排列的問題，這與三角形單元形成了最大的區(qū)別。例如圖1（d）中，場值最小的等值線1與邊0、1、2和3的有四個交點(diǎn)。根據(jù)二義性判斷，將其中邊0和3上的兩個等值點(diǎn)連接形成一條等值線段，將另外兩個等值點(diǎn)連接形成另一條等值線段。即圖1（d）中標(biāo)號為1的兩條等值線段，下面標(biāo)號2的等值線段同理產(chǎn)生。需要注意的是，標(biāo)號為3的等值線根據(jù)投影不相交原理將邊1和2上的兩個等值點(diǎn)連接形成一條等值線段，將另外兩個等值點(diǎn)連接形成另一條等值線段。此時等值線從原來包圍頂點(diǎn)0、2的情況突變?yōu)榘鼑旤c(diǎn)1、3的情況，而等值線不再按照之前的方向與網(wǎng)格單元相交。對這個由二義性引起的等值線相交方向突變問題的解決是四邊形網(wǎng)格中分割窮舉法的一個關(guān)鍵，后面專門討論了一種“退步處理”的思路。

三、四節(jié)點(diǎn)四邊形單元分割窮舉算法

3.1分割形式

四邊形單元被等值線分割的形式比較復(fù)雜。首先，仍然存在這樣的情況：某些網(wǎng)格單元恰好夾在兩條等值線之間，該網(wǎng)格單元沒有被任何等值線分割。此時我們可以將整個四邊形網(wǎng)格單元看成一個完整的等值四邊形。

四邊形網(wǎng)格單元被若干等值線分割的情況討論如下。

我們依照第一條等值線的場值和網(wǎng)格單元四個頂點(diǎn)的場值的大小關(guān)系，將分割形式劃分為四種基本形態(tài)：“三小一大”型、“兩小相鄰”型、“兩小相隔”型和“一小三大”型。

1） “三小一大”型：四邊形網(wǎng)格的四個頂點(diǎn)中有一個頂點(diǎn)的場值比第一條等值線的場值大，其余三個頂點(diǎn)的場值比第一條等值線的場值小。如圖1（a）所示。2） “兩小相鄰”型：四邊形網(wǎng)格的四個頂點(diǎn)中有兩個相鄰頂點(diǎn)的場值比第一條等值線的場值大，其余兩個頂點(diǎn)的場值比第一條等值線的場值小。如圖1（b）所示。3） “一小三大”型：四邊形網(wǎng)格的四個頂點(diǎn)中有三個頂點(diǎn)的場值比第一條等值線的場值大，剩余一個頂點(diǎn)的場值比第一條等值線的場值小。如圖1（c）所示。4）“兩小相隔”型：四邊形網(wǎng)格的四個頂點(diǎn)中有兩個相隔頂點(diǎn)的場值比第一條等值線的場值大，其余兩個相隔頂點(diǎn)的場值比第一條等值線的場值小。如圖1（d）所示。

“三小一大”型和“兩小相鄰”型與三角形網(wǎng)格單元中“兩小一大”型和“一小兩大”型非常類似，等值線必定按照一個固定方向排列，因此對這兩種分割方式的處理也可以參考三角形網(wǎng)格的兩種處理方式[1]。而“兩小相隔”型和“一小三大”型中由于可能存在二義性，因此等值線排列方式比較復(fù)雜，其處理方式也隨之復(fù)雜。

四邊形網(wǎng)格中“三小一大”型的處理算法如下：

首先第一條等值線和三個較小的網(wǎng)格頂點(diǎn)圍成一個等值五邊形，其包含5個頂點(diǎn)。例如圖1（a）中由等值線1的兩個端點(diǎn)和網(wǎng)格頂點(diǎn)0、1、3圍成的等值五邊形。

其次循環(huán)處理，每條等值線的兩個等值點(diǎn)和之前的一對等值點(diǎn)圍成一個等值四邊形，例如圖1（a）中由等值線1和2的四個端點(diǎn)圍成的等值四邊形。最后處理完所有等值點(diǎn)后，將最后一對等值點(diǎn)和剩下的一個網(wǎng)格頂點(diǎn)圍成一個等值三角形，例如圖1（a）中由等值線3的兩個端點(diǎn)和網(wǎng)格頂點(diǎn)2圍成的等值三角形。

四邊形網(wǎng)格中“兩小相鄰”型的處理算法如下：

首先，第一對等值點(diǎn)與較小的兩個網(wǎng)格單元頂點(diǎn)圍成一個等值四邊形。其次循環(huán)處理，每次判斷下一對等值點(diǎn)對網(wǎng)格單元的分割方式。如果分割仍然是“兩小相鄰”，那么將當(dāng)前兩個等值點(diǎn)和前一對等值點(diǎn)圍成一個等值四邊形，例如圖1（b）中由等值線1、2圍成的等值四邊形；如果當(dāng)前等值線對網(wǎng)格單元的分割變成“三小一大”型，說明當(dāng)前等值線跨過某個單元頂點(diǎn)，此時將當(dāng)前兩個等值點(diǎn)和前一對等值點(diǎn)及被他們所夾的網(wǎng)格單元頂點(diǎn)圍成一個等值五邊形，例如圖1（b）中由等值線2、3和網(wǎng)格單元頂點(diǎn)3圍成的等值五邊形。如果分割方式已變成“三小一大”型，需要跳出當(dāng)前循環(huán)，如果后續(xù)還有等值線，則按照“三小一大”型處理。

3.2“一小三大”型的處理

對于“一小三大”型，這種分割形式的后續(xù)發(fā)展有多重可能，首先該網(wǎng)格單元有可能在與后續(xù)的某條等值線相交時直接變化為“三小一大”型或“兩小相鄰”型，這樣之后的排列仍然可以按照“三小一大”型或“兩小相鄰”型的方式處理。當(dāng)變化為“三小一大”型時，意味著相鄰兩條等值線中間夾著一個等值六邊形，即由前后兩對等值點(diǎn)和所夾的兩個網(wǎng)格頂點(diǎn)組成的六邊形。例如圖1（d）中，如果沒有等值線3，則由等值線2、4和頂點(diǎn)2、3圍成一個等值六邊形。當(dāng)變化為“兩小相鄰”型時，意味著相鄰兩條等值線中間夾著一個等值五邊形，即由前后兩對等值點(diǎn)和所夾的一個網(wǎng)格頂點(diǎn)組成的五邊形。例如圖1（d）中，由等值線2、3和頂點(diǎn)3圍成一個等值五邊形。之后的處理按照前述“三小一大”型和“兩小相鄰”型的方式進(jìn)行即可?！耙恍∪蟆毙偷奶幚黼y點(diǎn)主要在后期可能轉(zhuǎn)化為“兩小相隔”型。

當(dāng)變化為“兩小相隔”型時，某條等值線的場值大于兩個對角網(wǎng)格頂點(diǎn)，小于另外兩個對角頂點(diǎn)時，意味著此時單元與某個場值的等值線有四個交點(diǎn)，產(chǎn)生二義性。這樣后續(xù)等值線與網(wǎng)格相交不再按照一個固定方向進(jìn)行的，如圖1（d）中所示。這時可以將程序流程轉(zhuǎn)入“兩小相隔”型的處理模塊。此時需要知道哪些網(wǎng)格頂點(diǎn)已經(jīng)被一條等值線包圍，因此做如下“主頂點(diǎn)”定義。

[定義1] 主頂點(diǎn)：當(dāng)四邊形某頂點(diǎn)所在的兩條邊都有等值點(diǎn)存在，并且離該頂點(diǎn)最近的兩個等值點(diǎn)恰好是某條等值線的兩個端點(diǎn)，則稱該四邊形頂點(diǎn)為一個“主頂點(diǎn)”。

當(dāng)程序流程轉(zhuǎn)入“兩小相隔”型的處理模塊時，將當(dāng)時的主頂點(diǎn)信息傳入，并傳入最后一條包圍主頂點(diǎn)的等值線信息，以待后用。

3.3“兩小相隔”型的處理

“三小一大”型和“兩小相鄰”型（包括從“一小三大”型變化過去的情況）中等值線對網(wǎng)格單元的切割總是按照一個固定的方向前進(jìn)，這種固定的方向是上述處理的基礎(chǔ)。但是對于“兩小相隔”型（包括從“一小三大”型變化過去的情況），等值線對網(wǎng)格單元的切割方式不再按照固定順序，而是有可能在某種情況下發(fā)生突變。

從“一小三大”型變化為“兩小相隔”型的第一種可能情況是被后續(xù)等值點(diǎn)包圍的仍然是原來的頂點(diǎn)和他的對角頂點(diǎn)，并在此種情況下結(jié)束。第二種可能情況是，先變?yōu)樯鲜銮闆r，然后變?yōu)椤叭∫淮蟆鼻闆r。

第三種情況仍然是先變?yōu)榈谝环N情況，然后由于二義性的存在后續(xù)的某條等值線不在包圍原始的兩個頂點(diǎn)，而包圍另外兩個頂點(diǎn)，并在此種情況結(jié)束。也可能最后變?yōu)椤叭∫淮蟆鼻闆r。最后一種可能情況是，一進(jìn)入“兩小相隔”型即由于二義性的存在，改變了被包圍的頂點(diǎn)，并在此種情況結(jié)束，或有可能最后變?yōu)椤叭∫淮蟆鼻闆r。

開始就是“兩小相隔”型的情況下，等值線可能的分割形式與上述情況相似，但是有兩點(diǎn)不同。首先，不再有第一條在“一小三大”情況下產(chǎn)生的標(biāo)號為1的等值線；其次，不存在第四種情況。無論上述哪種情況，經(jīng)過分析發(fā)現(xiàn)，一旦由于二義性，被等值線包圍的頂點(diǎn)發(fā)生變化，則等值線對網(wǎng)格單元的切割順序即發(fā)生變化。沒發(fā)生變化前，切割總是從兩個角開始沿著對角線向里切割。當(dāng)發(fā)生變化后，等值線開始沿著另外一條對角線向外不斷切割。

四、結(jié)論

該算法已在作者所在項目中應(yīng)用，事實(shí)證明該算法是準(zhǔn)確和高效的。如圖2所示，是一組實(shí)驗(yàn)數(shù)據(jù)所繪制的云圖，左圖為條紋云圖，右圖為光順云圖。該數(shù)據(jù)中包含3552個網(wǎng)格單元和16條等值線。測試計算機(jī)CPU為INTEL G630，主頻2.7GHz，內(nèi)存4G。云圖計算和繪制時間的測試結(jié)果為1.76秒。當(dāng)然本算法有進(jìn)一步改進(jìn)的可能，例如可以利用等參元變換對每條等值線進(jìn)行插值，將現(xiàn)有的直線段式等值線優(yōu)化成折線段式等值線，使繪圖結(jié)果更美觀。這些都是今后可能的研究方向。

參 考 文 獻(xiàn)

[1] 杜小甫， 王成恩. 基于等值線數(shù)據(jù)的一種新的云圖算法[J]. 東北大學(xué)學(xué)報（自然科學(xué)版）， 2013， Vol. 34 （5）： 624-627.

[2] 王成恩. 面向科學(xué)計算的網(wǎng)格劃分與可視化技術(shù)[M]. 北京：科學(xué)出版社，2011：109-133.