正如 FastSLAM 廣泛應(yīng)用于柵格地圖一樣，Howie提出了一種基于拓?fù)涞貓D的同時定 位與地圖生成算法75]。該方法建立在廣義 Voronoi圖(Generalized Voronoi Graph,GVG) 的基礎(chǔ)之上。圖1.59給出了基于拓?fù)涞貓D的同時定位與地圖生成方法創(chuàng)建的GVG 拓?fù)涞貓D。圖中線的交點為拓?fù)涔?jié)點，代表特定地點。節(jié)點之間的連線代表連通的路徑。

考慮平面上的一組點P, 對于P 上任意一點p, 定義離p; 點較近而與其他點較遠的區(qū) 域為與p; 相關(guān)的Voronoi區(qū)域，表示為V 。這樣平面上的所有點都必定屬于某一區(qū)域。兩 個 Voronoi區(qū)域V 和 V 邊界線上的所有點到p 和p,的距離相等并且小于到其他任何點的 距離，定義這條邊界線為Voronoi 邊，表示為E, 。Voronoi 邊或者延伸到無限遠處，或者與 其他的Voronoi邊相交，交點到平面上三點P:\p 和p₆ 的距離相等且小于到其他任何點的 距離，則稱該交點為Voronoi 節(jié)點，表示為N, 并把與若干點集相對應(yīng)的Voronoi 節(jié)點和 Voronoi邊集合稱為Voronoi圖。

點集P 的 Delaunay 三角剖分是指對于每一個 Voronoi節(jié)點N, 總存在一個三角形T, T 的D點分別為P:、P;和Ph, 并且三角形T 的三個邊分別被E 、Eμ 和 E 中分。所以過Pi、 P;和ph三點的外接圓以節(jié)點N; 為圓心，并且不包含平面上的所有其他點。Delaunay 三角 剖分具有很多優(yōu)良的品質(zhì)，比如，三角剖分的結(jié)果不受點集旋轉(zhuǎn)和平移操作的影響，并且 小區(qū)域點的變化不會引起在整個Voronoi圖上的傳播，只會對局部的區(qū)域造成影響。

根據(jù)Z短距離的定義不同，可以把Voronoi圖分為很多種，比如GVG按照到物體而非 到點的Z短距離劃分Voronoi圖，可以視為單純依靠傳感器信息就能夠跟蹤的嵌入式道路 地圖(Road map)。所 以 ，GVG 非常適合于拓?fù)涞貓D的在線創(chuàng)建。

根據(jù)所知的文獻，GVG是目前W一一種可以在線創(chuàng)建的拓?fù)涞貓D，但是該方法仍然 有其不足之處：先，GVG 本身是一種道路地圖，GVG 節(jié)點可以認(rèn)為是不同通道的集結(jié) 點，在大規(guī)模未知環(huán)境中，可能存在許多特征相似的節(jié)點，給地圖創(chuàng)建或機器人定位時的 數(shù)據(jù)關(guān)聯(lián)帶來了很大的困難。這一不足比FastSLAM 有所改善，但仍然不能滿足機器人 在大規(guī)模復(fù)雜環(huán)境下的導(dǎo)航和探索要求。其次，GVG 對于環(huán)境的局部改變比較敏感，增加一個障礙物可能導(dǎo)致若干節(jié)點的產(chǎn)生，因此GVG 不適合應(yīng)用于動態(tài)環(huán)境，這一點妨礙 了 GVG 在實際機器人探索、導(dǎo)航中的應(yīng)用。