平面嵌入(編輯修改稿)
2025-08-15 00:10 本頁面
【文章內(nèi)容簡(jiǎn)介】 會(huì)依次處理下面幾種情況 : ?遇到終止節(jié)點(diǎn)或者塊的根時(shí) ,終止遍歷 . ?節(jié)點(diǎn)有包含相關(guān)節(jié)點(diǎn)的子塊 ,到它子塊中繼續(xù)遍歷 . ?節(jié)點(diǎn)不是外部活躍節(jié)點(diǎn) ,走向下一節(jié)點(diǎn) . 當(dāng)加入回落邊的以后 ,會(huì)將該邊所連接的兩個(gè)塊和它們之間的塊全部合并 .它和分離是對(duì)應(yīng)的 .節(jié)點(diǎn)所在塊與子塊合并后也不再擁有該子塊 . ?分離是在加入樹邊的時(shí)候 . Walkdown — 向下遍歷 (2) ?合并是在加入回落邊以后 . 翻轉(zhuǎn)操作 為了將所有的回落邊都順利的加入圖 GP 中 ,圖 GP 必須始終滿足一個(gè)性質(zhì) . 這個(gè)性質(zhì)就是 : ?外部活躍節(jié)點(diǎn)都必須留在外部面上 . 翻轉(zhuǎn)操作 我們把接觸最外層空間的面 ,叫做外部面 .(圖中黃線標(biāo)出的面 ) 翻轉(zhuǎn)操作 為了將所有的回落邊都順利的加入圖 GP 中 ,圖 GP 必須始終滿足一個(gè)性質(zhì) . 這個(gè)性質(zhì)就是 : ?外部活躍節(jié)點(diǎn)都必須留在外部面上 . 加入回落邊的時(shí)候會(huì)覆蓋向下遍歷時(shí)經(jīng)過的面 ,這可能導(dǎo)致外部活躍節(jié)點(diǎn)被覆蓋 ,為了保證圖 GP的性質(zhì) .定義一個(gè)翻轉(zhuǎn)操作 . 翻轉(zhuǎn)操作 u v w e v’ w w w w w w w w w w w e w w s1 Walkdown — 向下遍歷 (3) u v w k v’ w k s2 e e s 信息取得 算法需要有快速取得外部活躍信息和相關(guān)信息的方法 .
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1