[發明專利]一種單機多核環境下約束地形并行構建方法

有效

• 申請號: 201510299433.6
• 申請日: 2015-06-03
• 公開（公告）號: CN105160706B
• 公開（公告）日: 2017-12-19
• 發明（設計）人: 劉德兒;熊證
• 申請（專利權）人: 江西理工大學
• 主分類號: G06T17/05
• 分類號: G06T17/05
• 代理公司: 四川君士達律師事務所51216
• 代理人: 芶忠義

1.一種單機多核環境下約束地形并行構建方法，其特征在于，包括以下步驟：

步驟1，基于四方邊緣結構的CD-TIN數據結構及主要函數設計；

步驟2，基于負載平衡的數據劃分策略；

步驟3，基于分治算法的子三角網并行構建；

步驟4，子三角網并行合并；

步驟5，格網索引構建；

步驟6，約束點地物并行插入；

步驟7，約束線地物并行插入；

步驟8，約束面地物并行插入；

所述步驟1的具體步驟為：

CCW代表逆時針方向，CW代表順時針方向，該數據結構定義如下：

(1)假設初始邊為e，則e有一個與其方向相反的伴生邊e.twin；e.org為e的起始點坐標；e.dest為e的終點坐標；e.Rot和e.InvRot為e的對偶邊；

(2)包含“next”的邊是指以逆時針方向圍繞鄰面或頂點的下一條邊；e.Lnext指逆時針圍繞e邊左面的下一條邊，與e邊同左面；e.Dnext指逆時針圍繞e邊終點的下一條邊，與e邊同終點；e.Onext指逆時針圍繞e邊起點的下一條邊，與e邊同起點；e.Rnext指逆時針圍繞e邊右面的下一條邊，與e邊同右面；

(3)包含“prev”的邊是指以順時針方向圍繞鄰面或頂點的下一條邊；e.Dprev指順時針圍繞e邊終點的下一條邊，與e邊同終點；e.Rprev指順時針圍繞e邊右面的下一條邊，與e邊同右面；e.Lprev指順時針圍繞e邊左面的下一條邊，與e邊同左面；e.Oprev指順時針圍繞e邊起點的下一條邊，與e邊同起點；

為實現該數據結構，定義了三個數據類：節點類—VertexClass、邊類—EdgeClass和三角形類—TriangleClass，以及一個操作類：UtilityClass；VertexClass記錄節點三維坐標、關聯邊和布爾值的約束屬性，EdgeClass記錄四方邊緣結構的各拓撲邊、左右三角邊形和布爾值的約束屬性；UtilityClass中定義了CD-TIN的系列操作函數接口，

其中包含四個主要含數據接口：makeEdge、splice、connected和swap，函數功能描述如下：

(1)void splice(Edge*a,Edge*b)，該函數作用是對a、b邊進行連接或者拆分；若將a、b邊所在的兩個具有共同頂點的獨立子三角網合并，該函數將兩個子三角網在共同頂點處關聯在一起；同時，合并a和b左側的面；相反，若要在共同頂點處沿a和b邊拆分，該函數將在共同頂點處將三角網拆分成兩個獨立子三角網，同時，分裂a和b左側的面；

(2)Edge*connected(Edge*a,Edge*b)，該函數作用是連接a的終點，b的起點生成新邊c，在此過程中會建立a,b,c之間的四方邊緣結構關系,next指邊的Lnext，prev指邊的Lprev；

(3)void swap(Edge*e)，該函數作用是用來交換對角線邊，當用局部優化法LOP檢測三角形不滿足Delaunay法則時，則需要交換對角線邊，將與e邊相鄰的兩三角形組成的四邊形另兩頂點相連，形成新的邊取代e，該邊分別以e邊起點和終點逆時針方向查找，第一點為新邊的起點，第二點為終點。

2.根據權利要求1所述的一種單機多核環境下約束地形并行構建方法，其特征在于，所述步驟2的具體步驟為：

采用坐標排序法作為統一的數據劃分策略，(1)用總點數N除于計算線程數K，假設每個線程平均分配點數為m；(2)將離散點集先X軸方向，后Y軸方向進行排序；(3)根據每個線程的點數m，將點號區間[i*m,(i+1)*m-1]分配給每個線程，i為線程序號，i＝0,1,2,…,K，如果存在沒有分配完的剩余點號，則全部給最后一個線程，所有線程共享同一份數據，每個線程計算時，根據點號區間從新排序點集中讀取對應點。