在可旋轉三維物件上的標籤放置問題

Abstract

本文提出一種在可旋轉的三維物件上，給定其中一個角度的佈局 時，計算三維物件在其他觀看角度時標籤位置的方法，並提出模型及 成本函數來衡量佈局的好壞。為了實際應用，本文提出了兩種演算法 ——線性規劃演算法及貪婪演算法。線性規劃演算法的優點是能算出 成本最小的佈局，但因混合二元變數，使之成為 NP 完備問題。而貪 婪演算法則有著運算時間短的優勢，計算一個佈局的時間平均不超過 1 毫秒，相對於線性規劃演算法減少了 99% 的運算時間，相對的也增 加一部分成本，增加的成本隨著錨點數量而增加。當錨點數量少於 40 時，貪婪演算法比線性規劃演算法平均多出 20% 成本。