基于圖的主方向關(guān)系一致性檢驗(yàn).pdf

1、一致性檢驗(yàn)問(wèn)題是一個(gè)基礎(chǔ)理論問(wèn)題，是空間方向關(guān)系推理研究領(lǐng)域的重要分支，越來(lái)越引起研究者的注意。就一般情況而言，一致性檢驗(yàn)是NP完全的。由此，國(guó)內(nèi)外學(xué)者主要都是針對(duì)特定子類(lèi)——凸關(guān)系網(wǎng)絡(luò)展開(kāi)研究，雖采用的合成運(yùn)算方法不同，但最終的判定原理大都是基于業(yè)內(nèi)現(xiàn)有的“路徑一致性理論”，傳統(tǒng)的純數(shù)學(xué)方法沒(méi)有新的突破。 本文分別對(duì)區(qū)域物體和點(diǎn)物體，給出了新的解決方案，一種基于有向圖的可視檢驗(yàn)，為一致性檢驗(yàn)提供了新的思路。論文給出了區(qū)域物體方

2、向關(guān)系的圖模型的一系列相關(guān)定義，通過(guò)劃分，把每一組方向關(guān)系轉(zhuǎn)化為有向圖，即節(jié)點(diǎn)代表對(duì)象，有向邊表示它們之間的方向關(guān)系。然后依據(jù)一定規(guī)則對(duì)整個(gè)約束關(guān)系集的劃分圖進(jìn)行合并、精煉，得到最終的SGV(Spatial Graph in Vertical)。通過(guò)檢驗(yàn)SGV中是否存在環(huán)來(lái)檢驗(yàn)其一致性，若有環(huán)存在則說(shuō)明給定的方向關(guān)系集是不一致的，同時(shí)給出了理論證明。最后運(yùn)用實(shí)例證明了該方法的正確性。 文中還討論了點(diǎn)物體的主方向關(guān)系一致性檢驗(yàn)，基