[發明專利]一種含邊拓撲信息的不規則三角網弧掃式構建方案

無效

• 申請號: 201110114586.0
• 申請日: 2011-05-05
• 公開（公告）號: CN102193998A
• 公開（公告）日: 2011-09-21
• 發明（設計）人: 劉永和;王燕平;馮錦明;郭維棟;趙彥琦
• 申請（專利權）人: 河南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 安陽市智浩專利代理事務所 41116
• 代理人: 張智和

1.一種含邊拓撲信息的不規則三角網弧掃式構建方案，其特征在于，包括以下步驟：

(1)使用含頂點、有向邊、三角形的3種類型定義，分別用三個數組存放；

(2)確定一個參考中心位置，計算所有離散點相對參考中心的距離和方位角，將待構網的離散點集按照該距離從小到大升序排序；

(3)建立一個存放三角網外邊界邊序列的雙向循環鏈表，并建立一個根據鏈表中始點的方位角存放結點的方位角存儲桶；

(4)在排序過的點集中取最初三個點按逆時針順序連成首三角形，并將三條邊的記錄以同樣的逆時針順序存入一個雙向循環鏈表中，形成初始三角網外邊界；

(5)從點集中按序取下一個點，按照該點的所屬方位角，從對應的方位存儲桶開始快速找出以右側面向當前點的邊，都作為與當前點連成新三角形的基邊；

(6)將第三步中找出的所有基邊與當前掃描過的點構建成為三角形，將其加入到三角形數組中，同時基邊的反向邊以及另外兩條邊(分別稱為左側邊和右側邊)，更新外邊界鏈表；

(7)對每個新生成的三角形都要與其所有鄰接三角形進行檢驗是否符合Delaunay三角網最優準則，否則交換三角形的對角邊，并以遞歸的方式對交換后得到的三角形進行擴散式LOP優化；

(8)重復第(5)~(7)步，直至點集中所有的點都被處理過。

2.根據權利要求1所述的方案，其特征在于：頂點、有向邊和三角形這三種類型對象之間的指針聯系用它們在數組中的位置下標表示，其中有向邊的定義設置有指向其左鄰三角形和其反向邊的數組下標索引，三角形的定義設置有指向其三條鄰邊的數組下標索引并使三邊按照逆時針順序排列。

3.根據權利要求1所述的方案，其特征在于：構網前需要計算所有離散點相對于所選參考中心的距離及方位角，方位角是參考中心-離散點構成的向量逆時針離開x軸正向的夾角。

4.根據權利要求1所述的方案，其特征在于：三角網外邊界集合要用一個鏈表來表示，構網過程中要保持鏈表中的邊按逆時針順序相接，即一條邊的始點與其前驅邊的終點是同一頂點，該邊的終點與其后繼邊的始點是同一頂點。

5.根據權利要求1所述的方案，其特征在于：將方位角按等間隔劃分，每個間隔建立一個對應的存放邊界邊鏈表結點的存儲桶，每個存儲桶使用鏈表或動態數組類型，全部存儲桶用一個數組表示。

6.根據權利要求1或5所述的方案，其特征在于：存儲桶中的結點要始終與邊界鏈表中存放的結點保持一一對應，即每次向邊界鏈表中加入一條邊的結點時，要在存儲桶中加入該結點相應的記錄，且每次刪除邊界鏈表中的一個邊結點時，該結點在存儲桶中的記錄也要刪除。

7.根據權利要求1所述的方案，其特征在于：生成新三角形及新邊時，檢查新生成的右側邊是否與當前所用基邊在邊界鏈表中的前驅邊互為反向邊，若是則從邊界鏈表中刪除該前驅邊的記錄，否則將右側邊記錄作為基邊的前驅插入邊界鏈表；檢查新生成的左側邊是否與當前所用基邊在邊界鏈表中的后繼邊互為反向邊，若是則刪除該后繼邊在邊界鏈表中的記錄，否則將左側邊記錄作為基邊的后繼插入邊界鏈表。

8.根據權利要求1所述的方案，其特征在于：在優化過程中交換兩個三角形對角邊時，修改兩個三角形及兩條反向邊對象的屬性，以及設置與其它4條鄰邊有關的拓撲屬性。