計算幾何應該是一個比較複雜的東西吧，它的應用十分廣泛。為此，我花了很長的時間來學習計算幾何。
前言
計算幾何應該是一個比較複雜的東西吧，它的應用十分廣泛。為此，我花了很長的時間來學習計算幾何。
點與向量
- 點
點應該還算比較簡單吧！對于平面上的一個坐标為\((x,y)\)的點，我們可以用\(P(x,y)\)來表示它。
- 向量
向量表示的是一個有大小和方向的量，在平面坐标系下它與點一樣也用兩個數來表示。這兩個數的實際含義是将這個向量的起點移至原點後終點的坐标。通常，我們用\(\vec v\)來表示一個向量，用\(|\vec v|\)來表示向量\(\vec v\)的長度。
- 點與向量的基本定義與運算
雖然點與向量十分相像，但是它們在概念上還是有許多不同的。
下面是它們的基本定義與運算。
struct Point//一個結構體用來存儲一個點
{
double x,y;//分别存儲點的兩個坐标
Point(double nx=0,double ny=0):x(nx),y(ny){}//構造函數
};
typedef Point Vector;//向量在代碼中其實與點差不多，是以可以直接typedef一下
inline Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}//向量+向量=向量
inline Vector operator - (Point A,Point B) {return Vector(A.x-B.x,A.y-B.y);}//點-點=向量
inline Vector operator * (Vector A,double x) {return Vector(A.x*x,A.y*x);}//向量*一個數=向量
inline Vector operator / (Vector A,double x) {return Vector(A.x/x,A.y/x);}//向量/一個數=向量
點積
下面，先來介紹一下向量的點積。
- 點積的計算公式及其擴充
\[\vec v(X_1,Y_1)·\vec u(X_2,Y_2)=X_1X_2+Y_1Y_2
\]
對于兩個向量\(\vec v\)和\(\vec u\)，如果它們的夾角為\(\theta\)，則它們的點積就等同于\(|\vec v||\vec u|cos \theta\)。
既然這樣，我們就可以推導出以下公式：
向量的長度：\(\sqrt {\vec v·\vec v}\)（因為對于兩個相同的向量，\(cos\theta=0\)，是以\(\vec v·\vec v=|\vec v||\vec v|=|\vec v|^2\)）
向量的夾角：\(acos(\vec v·\vec u/|\vec v|/|\vec u|)\)（因為\(\vec v·\vec u/|\vec v|/|\vec u|=cos\theta\)，是以\(\theta=acos(\vec v·\vec u/|\vec v|/|\vec u|)\)）
以下是代碼實作：
inline double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}//點積
inline double Len(Vector A) {return sqrt(Dot(A,A));}//向量的長度等于sqrt(x^2+y^2)
inline double Ang(Vector A,Vector B) {return acos(Dot(A,B)/Len(A)/Len(B));}//向量的夾角等于acos(A·B/|A|/|B|)
- 點積的正負
該如何判斷兩個向量的點積的正負呢？
點積的正負是由兩個向量的夾角\(\theta\)所決定的。
\[\begin{cases}當\theta<90^。時，點積為正\\當\theta>90^。時，點積為負\\當\theta=90^。，即兩個向量垂直時，點積等于0\end{cases}
\]
- 其他
點積還有一個很重要的性質，就是點積滿足交換律。
叉積
叉積與點積是十分類似的。
- 叉積的計算公式及其擴充
\[\vec v(X_1,Y_1)×\vec u(X_2,Y_2)=X_1Y_2-Y_1X_2
\]
叉積有一個十分神奇的性質，就是\(\vec v×\vec u\)恰好等于這兩個向量組成的三角形的有向面積的\(2\)倍。
這樣，我們就能輕松求出兩個向量組成的三角形的面積了：
兩個向量組成的三角形的面積：\(\frac {\vec v×\vec u} 2\)
以下是代碼實作：
inline double Cro(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}//叉積
inline double Area(Vector A,Vector B) {return Cro(A,B)/2;}//求兩個向量組成三角形的有向面積
- 叉積的正負
叉積的正負是由兩個向量的位置關系決定的。
\[\begin{cases}當\vec u在\vec v左邊時，\vec v×\vec u為正\\當\vec u在\vec v右邊時，\vec v×\vec u為負\\如果\vec u與\vec v方向相同，則\vec v×\vec u為0\end{cases}
\]
- 其他
叉積是不滿足交換律的，\(\vec v×\vec u=-\vec u×\vec v\)。
後記：其他常見運算
點與向量還有一些比較基本的運算，下面就直接貼代碼了。
- 旋轉
inline Vector Rotate(Vector A,double rad) {return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}//将向量A旋轉rad度
- 求法線
inline Vector Normal(Vector A) {double len=Len(A);return Vector(-A.y/len,A.x/len);}//求向量A的機關法線