[發(fā)明專利]虛擬場景中有寬度物體移動路徑的優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201210246083.3
• 申請日: 2012-07-16
• 公開（公告）號: CN102799781A
• 公開（公告）日: 2012-11-28
• 發(fā)明（設(shè)計）人: 劉德建;陳宏展;張斌;吳擁民;徐順帆
• 申請（專利權(quán)）人: 福建天晴數(shù)碼有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 福州市鼓樓區(qū)京華專利事務(wù)所(普通合伙) 35212
• 代理人: 宋連梅

1.一種虛擬場景中有寬度物體移動路徑的優(yōu)化方法，其特征在于：包括如下步驟：

步驟10、使用掩碼地圖數(shù)據(jù)，經(jīng)過尋路算法搜索后，得到一個由一組連續(xù)路徑節(jié)點組成的節(jié)點集，節(jié)點集首尾分別為路徑的起始節(jié)點S和終止節(jié)點E；并檢查節(jié)點集的數(shù)據(jù)是否有效；

步驟20、先將起始節(jié)點S作為判斷起點在所有剩余節(jié)點中查找起始節(jié)點S可見的最遠節(jié)點，該最遠節(jié)點為第一最遠節(jié)點T1，再將第一最遠節(jié)點T1作為判斷起點查找可見的最遠節(jié)點，得到第二最遠的節(jié)點T2，再由第二最遠節(jié)點T2作為判斷起點查找可見的最遠節(jié)點，得到第三最遠節(jié)點T3，然后按此規(guī)律一直查找下去，直到所可見的最遠節(jié)點為終止節(jié)點E為止；

所述可見是指有寬度物體在從判斷起點到目標節(jié)點的途中不會有障礙物；所述可見的最遠節(jié)點是指離判斷起點最遠的目標節(jié)點；

步驟30、最后，將起始節(jié)點S、第一最遠節(jié)點T1、第二最遠節(jié)點T2、第三最遠節(jié)點T3……終止節(jié)點E的中心點順次連接起來，所得到的連線即為優(yōu)化路徑。

2.根據(jù)權(quán)利要求1所述的虛擬場景中有寬度物體移動路徑的優(yōu)化方法，其特征在于：所述步驟20中，判定所述可見的最遠節(jié)點的方法是：計算有寬度物體從判斷起點到目標節(jié)點的移動過程的矩形區(qū)域外圍，所有位于該矩形區(qū)域內(nèi)的完整節(jié)點和部分節(jié)點即為掃描節(jié)點集，判斷該掃描節(jié)點集中是否有障礙物節(jié)點，若有則不可見，若無則可見。

3.根據(jù)權(quán)利要求2所述的虛擬場景中有寬度物體移動路徑的優(yōu)化方法，其特征在于：所述判定所述可見的最遠節(jié)點的方法具體過程如下：

步驟21：假設(shè)物體占地區(qū)域長度為橫向節(jié)點數(shù)L，寬度為豎向節(jié)點數(shù)W，判斷起點為節(jié)點A，目標節(jié)點為節(jié)點B；

步驟22：定位所述有寬度物體的重心節(jié)點，計算重心節(jié)點從四個方向到達物體邊緣的距離left、top、right、bottom，得到以下數(shù)據(jù)：?

left=(L-1)/2，

right=L/2，

bottom=(W-1)/2，

top=W/2；

步驟23：計算有寬度物體移動過程的矩形區(qū)域外圍，得出該矩形區(qū)域的兩個對角線頂點所在節(jié)點的坐標分別為(minX,minY),(maxX,maxY)，其中：

minX=min(x1,x2)–left，

minY=min(y1,y2)–bottom，

maxX=max(x1,x2)+right，

maxY=max(y1,y2)+top；

步驟24：根據(jù)物體上下邊緣點軌跡獲取掃描節(jié)點集，假設(shè)節(jié)點A與節(jié)點B的中心點連接起來直線的方程式為f(x):y=ax+b，在二維空間下，直線形態(tài)歸納為以下四種情況：

第1種:x=b，表示有寬度物體朝水平方向移動，所述矩形區(qū)域中的所有節(jié)點就是掃描節(jié)點集；

第2種:y=b，a=0，有寬度物體朝垂直方向移動，所述矩形區(qū)域中的所有節(jié)點就是掃描節(jié)點集；

第3種:y=ax+b，a>0，有寬度物體正向傾斜移動，通過A、B兩節(jié)點的坐標求出a、b的值，設(shè)上、下邊緣點的軌跡直線分別為f_b(x)：y=ax+b_b，f_t(x)：y=ax+b_t；根據(jù)二維數(shù)學(xué)幾何知識可得：

b_t=b+m，

b_b=b-n，

根據(jù)重心節(jié)點在物體中的位置固定，計算得出m與n的值分別為：

m=a×(left+0.5)+top+0.5，

n=a×(right+0.5)+bottom+0.5；

通過以上計算，求出直線f_b(x)與f_t(x)的方程式：

f_b(x):y=a×x+b-(a×(right+0.5)+bottom+0.5)；?

f_t(x):y=a×x+b+a×(left+0.5)+top+0.5；

兩直線f_b(x)與f_t(x)中間的區(qū)域與步驟23中獲得的矩形區(qū)域的重疊部分即為掃描節(jié)點集所在區(qū)域，只要橫坐標x從minX開始遍歷至maxX，依次計算直線f_b(x)和f_t(x)在該橫坐標下的縱坐標為掃描起始縱坐標和掃描終止縱坐標，即可獲得所有掃描節(jié)點集中的節(jié)點；

第4種:y=ax+b，a<0，有寬度物體反向傾斜移動，通過A、B兩節(jié)點的坐標求出a、b的值，設(shè)上、下邊緣點的軌跡直線分別為f_b(x)：y=ax+b_b，f_t(x)：y=ax+b_t；根據(jù)二維數(shù)學(xué)幾何知識可得：

b_t=b+m，

b_b=b–n，

根據(jù)重心節(jié)點在物體中的位置固定，計算得出m與n的值分別為：

m=|a|×(right+0.5)+top+0.5，

n=|a|×(left+0.5)+bottom+0.5，

通過以上計算，求出直線f_b(x)與f_t(x)的方程式：

f_b(x):y=a×x+b–(|a|×(left+0.5)+bottom+0.5)

f_t(x):y=a×x+b+|a|×(right+0.5)+top+0.5

兩直線f_b(x)與f_t(x)中間的區(qū)域與步驟23中獲得的矩形區(qū)域的重疊部分即為掃描節(jié)點集所在區(qū)域，只要橫坐標x從minX開始遍歷至maxX，依次計算直線f_b(x)和f_t(x)在該橫坐標下的縱坐標為掃描起始縱坐標和掃描終止縱坐標，即可獲得所有掃描節(jié)點集中的節(jié)點；

步驟25：對所獲得的掃描節(jié)點集中的每個節(jié)點進行屬性判斷，只要有一個節(jié)點是障礙物節(jié)點，則A、B兩節(jié)點不可見，否則A、B兩節(jié)點可見。

4.根據(jù)權(quán)利要求2所述的虛擬場景中有寬度物體移動路徑的優(yōu)化方法，其特征在于：所述步驟20中，所述可見的最遠節(jié)點的查找過程采用二分法查找，即先判斷離判斷起點最遠處的節(jié)點是否可見，若不可見則判斷該判斷起點與該最遠處的節(jié)點的中間位置節(jié)點是否可見，以此規(guī)律遍歷下去直到找到該判斷起點的可見的最遠節(jié)點。?