計算幾何

計算幾何是一門興起於二十世紀七十年代末的電腦科學的一個分支,主要研究解決幾何問題的演算法。

自從1946年世界上第一台電腦問世以來,電腦應用的一個重要里程碑是1962年美國麻省理工學院發明了世界上第一台圖形顯示器。自此之後,電腦可以透過圖形顯示器直接輸入、輸出圖形,並且可以在顯示器上透過游標的移動,直接修改圖形。而在這之前,工程師是透過一厚疊紙上密密麻麻的數字來間接表達工程圖形的。

1962年被認為是美國和歐洲CAD開始發展的一年。首先的應用領域是汽車、飛機和造船工業。這3個行業,由於其產品的外形曲面特別複雜,要求特別苛刻,而成為CAD首先應用的領域。

與此同時,也就發展出了一門新興學科——計算幾何,它在美國常常被稱為CAGD(Computer Aided Geometric Design,電腦輔助幾何設計),專門研究「幾何圖形資訊(曲面和三維實體)的電腦表示、分析、修改和綜合」。1972年在美國舉行CAGD第一次國際會議,標誌計算幾何學科的形成。

計算幾何演算法

  • 判斷點是否在直線上
  • 判斷兩線段是否相交
  • 判斷線段和直線是否相交
  • 判斷點是否在矩形內
  • 判斷線段、折線、多邊形是否在矩形內
  • 判斷矩形是否在矩形內
  • 判斷圓是否在矩形內
  • 判斷矩形是否在圓內
  • 判斷點是否在多邊形內
  • 判斷線段是否在多邊形內
  • 判斷點是否在圓內
  • 判斷圓是否在圓內
  • 計算相交多邊形的重疊區域
  • 計算點到線段的最近點
  • 計算點到圓的最近點及點坐標
  • 凸包求法等

演算法介紹

向量概念

如果把一條線段的端點作出次序之分,則可將這種線段看作有向線段。如果有向線段 的起點 在坐標原點,則把它稱為向量 。這樣,點  可以看作起點為原點 的二維向量。相應地,三維空間坐標系下的坐標也可以作類似理解為三維向量。

設二維向量 ,則向量的加法定義為 ,向量的減法定義為 。向量的加減法有以下性質: 。因為點可視為坐標原點至該點的向量,所以點的加減法就是向量的加減法。

向量的叉積

向量的叉積,也稱向量的叉乘。向量  的叉乘記作 。定義 ,其結果是一個純量。幾何意義為由原點、點 、點 、點 四點共同組成的平行四邊形的面積(帶正負號)。計算向量叉積是直線和線段相關演算法的核心。向量的叉積有以下性質: 

叉乘的一個非常重要的性質是,可以通過它的正負號判斷兩向量之間的順逆時針關係:

  •  ,則  的順時針方向(左旋);
  •  ,則  的逆時針方向(右旋);
  •  ,則  共線,可能同向也可能反向。

演算法舉例

判斷折線段的拐向

折線段的拐向判斷方法可以直接由向量叉積的性質推出。 對於有公共端點的線段  ,通過計算 的符號,就可以確定折線的拐向:

  •  ,則  點拐向右側得到 
  •  ,則  點拐向左側得到 
  •  ,則   三點共線。

判斷點是否線上段上

外部連結