四節點四邊形網格單元中一種新的云圖生成算法

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

【關鍵詞】 分割窮舉算法 四節點四邊形網格單元 云圖 等值線 等值多邊形

一、引言

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

二、問題描述

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

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

[定理1] 等值點按照場值由小到大排列。

[定理2] 等值點按照所在網格邊編號由小到大排列。

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

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

三、四節點四邊形單元分割窮舉算法

3.1分割形式

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

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

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

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

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

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

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

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

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

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

3.2“一小三大”型的處理

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

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

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

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

3.3“兩小相隔”型的處理

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

從“一小三大”型變化為“兩小相隔”型的第一種可能情況是被后續等值點包圍的仍然是原來的頂點和他的對角頂點，并在此種情況下結束。第二種可能情況是，先變為上述情況，然后變為“三小一大”情況。

第三種情況仍然是先變為第一種情況，然后由于二義性的存在后續的某條等值線不在包圍原始的兩個頂點，而包圍另外兩個頂點，并在此種情況結束。也可能最后變為“三小一大”情況。最后一種可能情況是，一進入“兩小相隔”型即由于二義性的存在，改變了被包圍的頂點，并在此種情況結束，或有可能最后變為“三小一大”情況。

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

四、結論

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

參 考 文 獻

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

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