計算幾何

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

自從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）.