二又二分之一維之邊界標示
摘要
邊界標示是一種使用大型標籤來標示地圖上稠密資訊的視覺化技術,當中地圖上每一
個點特徵會被一條正交線性線連接至地圖邊界外的標籤。盡我們所知的,過去圖形繪
製演算法與電腦圖學之文獻僅考慮平面地圖與平面標籤之二維邊界標示,或僅延伸將
平面地圖改為三維模型之邊界標示,目前為止尚無探討將標籤延伸至三維空間之研
究。然而由於三維邊界標示仍有其定義上之困難度,因此為了縮短二維與三維邊界標
示研究之差距,本計畫將定義二又二分之一維邊界標示,當中標籤可置放在三維空間
中不同於地圖之平面上。由於該定義可分為許多變形,故本計畫擬分別從演算法設計
與分析、啟發式演算法設計、與互動介面系統實作三方向來研究所有可能變形之最佳
化問題。本計畫首先從理論研究的角度來探討各種變形最佳化問題是否存在多項式時
間演算法,找出並證明NP-Complete 問題,並針對難解的問題提出近似演算法。接著,
本計畫將針對較複雜的變形問題,使用混整數規劃或模擬退火法來設計啟發式演算
法。計畫最後將實作所設計之多項式時間演算法與啟發式演算法,開發並整合在一個
互動平板系統,讓使用者可藉由觸碰與滑動的操作來與多維地圖邊界標示作互動。為
增加應用性,進一步設計將地圖置換成三維模型之系統。
個點特徵會被一條正交線性線連接至地圖邊界外的標籤。盡我們所知的,過去圖形繪
製演算法與電腦圖學之文獻僅考慮平面地圖與平面標籤之二維邊界標示,或僅延伸將
平面地圖改為三維模型之邊界標示,目前為止尚無探討將標籤延伸至三維空間之研
究。然而由於三維邊界標示仍有其定義上之困難度,因此為了縮短二維與三維邊界標
示研究之差距,本計畫將定義二又二分之一維邊界標示,當中標籤可置放在三維空間
中不同於地圖之平面上。由於該定義可分為許多變形,故本計畫擬分別從演算法設計
與分析、啟發式演算法設計、與互動介面系統實作三方向來研究所有可能變形之最佳
化問題。本計畫首先從理論研究的角度來探討各種變形最佳化問題是否存在多項式時
間演算法,找出並證明NP-Complete 問題,並針對難解的問題提出近似演算法。接著,
本計畫將針對較複雜的變形問題,使用混整數規劃或模擬退火法來設計啟發式演算
法。計畫最後將實作所設計之多項式時間演算法與啟發式演算法,開發並整合在一個
互動平板系統,讓使用者可藉由觸碰與滑動的操作來與多維地圖邊界標示作互動。為
增加應用性,進一步設計將地圖置換成三維模型之系統。