Home > TaiBIF > Convex hull演算法

Convex hull演算法

November 18th, 2010

Convex hull演算法為在一個平面上,找出一最小凸多邊形可包含所有的點,目前有幾種比較常見用來計算凸多邊形演算法,如:Incremental 、Jarvis’s March (Gift Wrap)、Divide and Conquer、Quick Hull,而TaiBIF上即採用Quick Hull演算法,來協助我們畫出一個物種的最小凸多邊,因此在這邊,說明此演算法的概念及步驟:

  • 先在平面點集合中座標最小與最大值,分別標記為A與B,並畫成一直線(圖a)。
  • 尋找AB線段兩側之點集合,找出C與D點,分別距離AB線段最遠,即計算出所包圍面積最大值(下面有說明),再將AB線段取消,此時的邊界為ADBC(圖b),所圍成的區域為Discard 區。
  • 依據AD、DB、BC、CA 4個線段往外延伸(非Discard區)分別找出距離這4個線段最遠的點,形成新的邊界(圖c)。
  • 如此重複,當任一線段找不到任何一點時,此邊界即為包含原本點集合之最小凸多邊形(圖d)。

如何計算三角形中的面積,傳統的作法利用「底*高/2」的公式,但要算出每個三角形「底」與「高」雖不麻煩,但也需額外多花一點計算時間,而一個快速的作法,就是採用行列式的計算方法。

Categories: TaiBIF Tags: ,
Comments are closed.