計算幾何

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

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

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

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

計算幾何演算法

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

演算法介紹

向量概念

如果把一條線段的端點作出次序之分，則可將這種線段看作有向線段。如果有向線段$P_{1}P_{2}$的起點$P_{1}$在坐標原點，則把它稱為向量${\boldsymbol {P}}_{2}$。這樣，點$P(x,y)$ 可以看作起點為原點$O(0,0)$的二維向量。相應地，三維空間坐標系下的坐標也可以作類似理解為三維向量。

設二維向量${\boldsymbol {P}}=(x_{1},y_{1}),{\boldsymbol {Q}}=(x_{2},y_{2})$，則向量的加法定義為${\boldsymbol {P}}+{\boldsymbol {Q}}=(x_{1}+x_{2},y_{1}+y_{2})$，向量的減法定義為${\boldsymbol {P}}-{\boldsymbol {Q}}=(x_{1}-x_{2},y_{1}-y_{2})$。向量的加減法有以下性質：${\boldsymbol {P}}+{\boldsymbol {Q}}={\boldsymbol {Q}}+{\boldsymbol {P}},{\boldsymbol {P}}-{\boldsymbol {Q}}=-({\boldsymbol {Q}}-{\boldsymbol {P}})$。因為點可視為坐標原點至該點的向量，所以點的加減法就是向量的加減法。

向量的叉積

向量的叉積，也稱向量的叉乘。向量${\boldsymbol {P}}$與${\boldsymbol {Q}}$的叉乘記作${\boldsymbol {P}}\times {\boldsymbol {Q}}$。定義${\boldsymbol {P}}\times {\boldsymbol {Q}}=x_{1}y_{2}-x_{2}y_{1}$，其結果是一個純量。幾何意義為由原點、點$P$、點$Q$、點$P+Q$四點共同組成的平行四邊形的面積（帶正負號）。計算向量叉積是直線和線段相關演算法的核心。向量的叉積有以下性質：${\boldsymbol {P}}\times {\boldsymbol {Q}}=-({\boldsymbol {Q}}\times {\boldsymbol {P}}),{\boldsymbol {P}}\times (-{\boldsymbol {Q}})=-({\boldsymbol {P}}\times {\boldsymbol {Q}})$。

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

• 若${\boldsymbol {P}}\times {\boldsymbol {Q}}>0$，則${\boldsymbol {P}}$在${\boldsymbol {Q}}$的順時針方向(左旋)；
• 若${\boldsymbol {P}}\times {\boldsymbol {Q}}<0$，則${\boldsymbol {P}}$在${\boldsymbol {Q}}$的逆時針方向(右旋）；
• 若${\boldsymbol {P}}\times {\boldsymbol {Q}}=0$，則${\boldsymbol {P}}$和${\boldsymbol {Q}}$共線，可能同向也可能反向。

演算法舉例

判斷折線段的拐向

折線段的拐向判斷方法可以直接由向量叉積的性質推出。 對於有公共端點的線段$AP$和$PB$，通過計算$\nabla =(B-P)\times (P-A)$的符號，就可以確定折線的拐向：

• 若$\nabla >0$，則$AP$在$P$點拐向右側得到$PB$；
• 若$\nabla <0$，則$AP$在$P$點拐向左側得到$PB$；
• 若$\nabla =0$，則$A$、$P$、$B$三點共線。

外部連結

• 主要的學術會議網頁（頁面存檔備份，存於互聯網檔案館）Symposium of Computation Geometry (SoCG)
• 劉鼎元. 苏步青先生对计算几何和CAD事业的贡献. （原始內容存檔於2007-07-07）.