計算幾何是算法競賽的一大塊，而叉積是計算機和的基礎(chǔ)。

首先叉積是計算說向量之間的叉積，那么我們可以這樣定義向量，以及向量的運算符重載。

?

struct Point {double x,y;Point(double x=0,double y=0):x(x),y(y) {} }; typedef Point Vector; Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); } Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); } Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); } Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); }bool operator < (const Point& a,const Point& b) {return a.x<b.x || (a.x==b.x && a.y<b.y); } int dcmp(double x) // {if(fabs(x)<esp) return 0;else return x<0?-1:1; } bool operator == (const Point& a,const Point& b) {return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y)==0; }

?

首先在二維坐標(biāo)下介紹一些定義：

點：A（x1，y1），B（x2，y2）

向量：向量AB=（ x2 - x1 , y2 - y1 ）= ( x , ?y );

向量的模 |AB| = sqrt ( x*x+y*y );

?

向量的點積：?結(jié)果為 x1*x2 + y1*y2。

點積的結(jié)果是一個數(shù)值。

點積的集合意義：我們以向量 a 向向量 b 做垂線，則 | a | * cos（a,b）為 a 在向量 b 上的投影，即點積是一個向量在另一個向量上的投影乘以另一個向量。且滿足交換律

應(yīng)用：可以根據(jù)集合意義求兩向量的夾角，cos（a,b） =（ 向量a * 向量b ） / （| a | * | b |） =??x1*x2 + y1*y2 /?（| a | * | b |）

?

?

向量的叉積：?結(jié)果為 x1*y2-x2*y1

叉積的結(jié)果也是一個向量，是垂直于向量a，b所形成的平面，如果看成三維坐標(biāo)的話是在 z 軸上，上面結(jié)果是它的模。

方向判定：右手定則，（右手半握，大拇指垂直向上，四指右向量a握向b，大拇指的方向就是叉積的方向）

叉積的集合意義：1：其結(jié)果是a和b為相鄰邊形成平行四邊形的面積。

2：結(jié)果有正有負(fù)，有sin（a，b）可知和其夾角有關(guān)，夾角大于180°為負(fù)值。

3：叉積不滿足交換律

應(yīng)用：

1：通過結(jié)果的正負(fù)判斷兩矢量之間的順逆時針關(guān)系

若 a x b > 0表示a在b的順時針方向上

若 a x b < 0表示a在b的逆時針方向上

若 a x b == 0表示a在b共線，但不確定方向是否相同

?

2：判斷折線拐向，可轉(zhuǎn)化為判斷第三點在前兩的形成直線的順逆時針方向，然后判斷拐向。

3：判斷一個點在一條直線的那一側(cè)，同樣上面的方法。

4：判斷點是否在線段上，可利用叉乘首先判斷是否共線，然后在判斷是否在其上。

5：判斷兩條直線是否想交（跨立實驗）

根據(jù)判斷點在直線那一側(cè)我們可以判斷一個線段的上的兩點分別在另一個線段的兩側(cè)，當(dāng)然這是不夠的，因為我們畫圖發(fā)現(xiàn)這樣只能夠讓直線想交，而不是線段，所以我們還要對另一條線段也進(jìn)行相同的判斷就ok。

///計算點積，及向量長度，及向量夾角 double Dot(Vector A,Vector B) { return A.x*B.x+A.y*B.y; } double Length(Vector A) { return sqrt(Dot(A,A)); } double Angle(Vector A,Vector B) { return acos(Dot(A,B))/Length(A)/Length(B); } //計算叉積，向量逆時針旋轉(zhuǎn),兩線段是否想交 double Cross(Vector A,Vector B) { return (A.x*B.y-A.y*B.x); } double Area2(Vector A,Vector B,Vector C) { return Cross(B-A,C-A); } Vector Rotate(Vector A,double rad) {return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); } bool Converxline(Vector A,Vector B,Vector C,Vector D) {//共線或平行if((Area2(A,B,C)==0&&Area2(A,B,D)==0) || Area2(A,B,C)*Area2(A,B,D)>0||Area2(C,D,A)*Area2(C,D,B)>0)return false;elsereturn true; }

轉(zhuǎn)自https://blog.csdn.net/y990041769/article/details/38258761

模板如下：

const double eps = 1e-10; //考慮誤差的加法 double add(double a, double b) {if(fabs(a + b) < eps * (fabs(a) + fabs(b))) return 0;return a + b; } //考慮誤差的與0比較 int dcmp(double x) {if(fabs(x) < eps) return 0;else return x<0?-1:1; } struct P {double x, y;P(){}P(double x, double y) :x(x), y(y){}bool operator == (P p) {return dcmp(x - p.x) == 0 && dcmp(y - p.y) == 0;}P operator + (P p) {return P(add(x, p.x), add(y, p.y));}P operator - (P p) {return P(add(x, -p.x), add(y, -p.y));}P operator * (double p) {return P(x * p, y * p);}P operator / (double p) {return P(x / p, y / p);}//點積double dot(P p) {return add(x * p.x, y * p.y);}//叉積double cross(P p) {return add(x * p.y, -y * p.x);} }; typedef P Vector; //向量逆時針旋轉(zhuǎn) Vector Rotate(Vector a,double rad) {return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); } //向量的模 double len(Vector a){return sqrt(a.dot(a)); } //兩向量的夾角 double angle(Vector a, Vector b) {return acos(a.dot(b) / len(a) / len(b)); } //絕對值為三點確定的三角形的面積的兩倍 double area2(Vector a, Vector b, Vector c) {return (b - a).cross(c - a); } //判斷p點是否在線段a-b上 bool on_seg(P p, Vector a, Vector b) {return (a - p).cross(b - p) == 0 && (a - p).dot(b - p) <= 0; } //判斷兩條線段是否相交 bool intersect(Vector a, Vector b, Vector c, Vector d) {if(area2(a, b, c) == 0 && area2(a, b, d) == 0|| area2(a, b, c) * area2(a, b, d) > 0|| area2(c, d, a) * area2(c, d, b) > 0) return false;return true; } //判斷兩條線段是否有交點 bool _intersect(Vector a, Vector b, Vector c, Vector d) {if(area2(a, b, c) == 0 && area2(a, b, d) == 0 && !on_seg(a, c, d) && !on_seg(b, c, d)|| area2(a, b, c) * area2(a, b, d) > 0|| area2(c, d, a) * area2(c, d, b) > 0) return false;return true; }

?

總結(jié)

以上是生活随笔為你收集整理的【ACM算法讲堂之 - 计算几何基础】：【点积和叉积】（附一些模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。