計算幾何

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

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

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

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

計算幾何演算法

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

演算法介紹

向量概念

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

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

向量的叉積

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

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

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

演算法舉例

判斷折線段的拐向

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

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

判斷點是否線上段上

外部連結

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