上圖是一個(gè)由任意凸多邊形構(gòu)成的導(dǎo)航網(wǎng)格踢关，白線(xiàn)包圍區(qū)域代表著不可進(jìn)入的障礙區(qū)域勺馆，紅線(xiàn)包圍區(qū)域則可以進(jìn)入或穿越咐鹤。網(wǎng)格中所有多邊形的頂點(diǎn)存儲(chǔ)次序均為順時(shí)鐘序拗秘。在下面的討論中，我們的運(yùn)算一概采用左手系進(jìn)行祈惶。
假設(shè)當(dāng)前所處的位置為p0雕旨，視線(xiàn)方向矢量為n0，p0位于多邊形A中捧请，我們知道每一條邊的兩側(cè)的多邊形的編號(hào)凡涩，現(xiàn)在的問(wèn)題是：如果求得該視線(xiàn)途經(jīng)了哪些多邊形？與這些多邊形的哪些邊相交于何處(即Way point)疹蛉？該視線(xiàn)終結(jié)于哪條邊的何處活箕？
首先讓我們來(lái)解決一個(gè)子問(wèn)題，即判斷射線(xiàn)r與某凸多邊形p之間的關(guān)系可款。不難想象育韩，r只可能與p不相交、相交于1點(diǎn)或2點(diǎn)(只有穿出筑舅、或先射入后穿出)座慰。這里我們最關(guān)心的是：(1) r究竟與p相交否？(2) 如果相交翠拣，那么r穿出p時(shí)版仔，其交點(diǎn)在哪條邊上？在哪里？
以A和射線(xiàn)r=(p0,n0)為例蛮粮，先來(lái)判斷A與r是否相交益缎，這個(gè)太容易了，只需判斷A有沒(méi)有邊與r相交即可然想。遍歷A的每一條邊e莺奔，然后得到每一條邊的起點(diǎn)和終點(diǎn)(注意，時(shí)刻牢記頂點(diǎn)順序是順時(shí)鐘的)变泄。然后令哟，分別獲得起點(diǎn)矢量from和終點(diǎn)矢量to，然后計(jì)算test_a=from×n0和test_b=to×n0妨蛹，再來(lái)檢查test_a和test_b的Z分量符號(hào)：如果相同屏富，則from、to均位于n0的同一側(cè)蛙卤，e與r不相交狠半；如果test_a.Z>0且test_b.Z<0，則e為射線(xiàn)r在A中的穿出線(xiàn)颤难；如果test_a.Z<0且test_b.Z>0神年，則要么e是射線(xiàn)的反方向與A的交線(xiàn)，要么e為射線(xiàn)在A中的射入邊行嗤。這里已日，我們最關(guān)心的是有沒(méi)有test_a.Z>0且test_b.Z<0的情況，即有沒(méi)有穿出邊昂验。
如圖捂敌，如果要對(duì)r進(jìn)行LOS test，首先我們要判斷一下p0處于哪個(gè)多邊形既琴，這個(gè)點(diǎn)與多邊形關(guān)系的判斷也很容易，這里泡嘴，我們的p0位于A中甫恩。然后，在A中找射線(xiàn)r的穿出邊和穿出點(diǎn)(求兩射線(xiàn)的交點(diǎn)酌予，trivial)磺箕，判斷穿出邊的另一側(cè)的多邊形是否可以進(jìn)入？如果是障礙或網(wǎng)格邊緣抛虫，則LOS test中止松靡，如果不是，則獲得穿出邊另一側(cè)的多邊形編號(hào)建椰，這里是B雕欺，然后繼續(xù)在B中找射線(xiàn)r的穿出邊和穿出點(diǎn)，繼續(xù)前面的一系列步驟，直到找出r的所有途經(jīng)多邊形屠列、所有穿出邊和穿出點(diǎn)為止啦逆。以上便是一次完整的視線(xiàn)檢測(cè)過(guò)程。是不是足夠簡(jiǎn)單笛洛？heh
如何判斷點(diǎn)p0是否處于凸多邊形內(nèi)?
見(jiàn)上圖夏志，這里我們采用叉乘法，雖說(shuō)只適用于凸多邊形苛让，不過(guò)計(jì)算最簡(jiǎn)便沟蔑，不涉及三角運(yùn)算(內(nèi)角和法)和開(kāi)方(面積法)，什么水平垂直交叉線(xiàn)檢測(cè)就直接免了吧狱杰，too ugly瘦材。假設(shè)多邊形是順時(shí)鐘頂點(diǎn)序，我們采用的是左手系浦旱。遍歷每條邊宇色，作一個(gè)邊矢量e，從起點(diǎn)到終點(diǎn)颁湖；然后作測(cè)試矢量t宣蠕，從邊起點(diǎn)到要測(cè)試的點(diǎn)p0；計(jì)算test=e×t甥捺，如果test矢量的Z分量符號(hào)始終保持不變抢蚀，則p0處于多邊形內(nèi)部；一旦其符號(hào)發(fā)生了改變(只需檢測(cè)到一次符號(hào)改變即可)镰禾，則p0處于多邊形外部皿曲。
導(dǎo)航網(wǎng)格和LOS檢測(cè)用來(lái)干什么的?
導(dǎo)航網(wǎng)格一般用來(lái)做層級(jí)式A*尋徑，它可以很容易地推廣到3D路徑規(guī)劃吴侦，與某些附加特性相配合屋休，能夠?qū)崿F(xiàn)更多的特殊用途；LOS檢測(cè)主要有兩個(gè)用途：動(dòng)態(tài)局部Point of View尋徑和A*路徑優(yōu)化(平滑+Cutting the Corner)备韧。
