計算幾何

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

自從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}}$ 共線，可能同向也可能反向。