文章目錄

• 基本概念
• • 點(diǎn)與向量的運(yùn)算
  • • 精度問題
  • 線段，射線和直線
  • 點(diǎn)積：
  • 夾角
  • 叉積
  • 向量的極角
  • 旋轉(zhuǎn)一個向量
  • 求三角形面積
  • 直線交點(diǎn)
  • 點(diǎn)到直線距離
  • 點(diǎn)在直線上的投影
  • 判斷兩條線段是否相交
  • 點(diǎn)與直線的位置關(guān)系
  • • 點(diǎn)是否在直線左側(cè)
    • 點(diǎn)是否在直線上
    • 點(diǎn)是否在線段上
  • 點(diǎn)與多邊形的位置關(guān)系
  • • 掃描法：
    • 轉(zhuǎn)角法
  • 線段與多邊形位置關(guān)系
  • 多邊形的面積

基本概念

點(diǎn)：平面上一點(diǎn)，用坐標(biāo)(x,y)來表示

struct Point{double x,y; };

向量：同時具有大小和方向的量 。把向量從原點(diǎn)出發(fā)到達(dá)的點(diǎn)的坐標(biāo)作為該向量的坐標(biāo)

typedef Point Vector;

點(diǎn)與向量的運(yùn)算

點(diǎn) + 向量 = 點(diǎn)
向量 + 向量 = 向量
點(diǎn) - 點(diǎn) = 向量
向量 * k = 向量

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); } struct point{double x,y;point(){}point(double x1,double y1):x(x1),y(y1){}point operator +(const point &z)const{return point(x+z.x,y+z.y);}point operator -(const point &z)const{return point(x-z.x,y-z.y);}point operator 8 (const double &rate)const{return point(x*rate,y*rate);} }p[N];

精度問題

因?yàn)楦↑c(diǎn)數(shù)的精度問題會造成微小的偏差

const double eps=1e-10; int dcmp(double x) {if(fabs(x)<eps)return 0;else return x>0?1;-1; } bool operator == (Point a,Point b) {return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y); }

線段，射線和直線

表示方式：

解析幾何（y = kx+b）

點(diǎn)+向量

具體區(qū)分線段射線和直線

struct Line{Point p;Vector v;int f; }; f=0 說明是線段 f=1 說明是射線 f=2 說明是直線 struct Line{point p,v;Line(){}Line(point _p.point _v):p(_p),v(_v){} }L[N];

點(diǎn)積：

點(diǎn)積表示的是兩個向量的長度之積再乘上他們夾角的余弦值，也就是a在b上的投影長度乘上b的模長

double dot(Vector a,Vector b) {return a.x*b.x+a.y*b.y; }

夾角

利用點(diǎn)積的定義：

double angle(Vector a,Vector b) {return acos(dot(a,b)/length(a)/length(b)); }

叉積

叉積表示的是兩個向量的長度之積再乘上它們的夾角的正弦值
也就是以這兩個向量為相鄰兩邊所成平行四邊形的面積
（叉積還可以表示方向）

double cross(Vector a,Vector b) {return a.x*b.y-a.y* b.x; }

v2在v1的順時針方向那么sin<v1,v2>就是負(fù)值，否則就輸正值。“順負(fù)逆正”
sin函數(shù)的符號就是叉積的符號
叉積的一個非常重要性質(zhì)是可以通過它的符號判斷兩矢量相互之間的順逆時針關(guān)系：
若 P × Q > 0 , 則P在Q的順時針方向。（用手勢判斷，大拇指朝上）
若 P × Q < 0 , 則P在Q的逆時針方向。
若 P × Q = 0 , 則P與Q共線，但可能同向也可能反向。
a×b的方向：四指由a開始，指向b，拇指的指向就是a×b的方向，垂直于a和b所在的平面；（大拇指朝上為正）

向量的極角

求α
tan α=y/x
這里的極角范圍是[-π， π)

double Polar_angle(int x,int y) {return atan2(y,x); }

旋轉(zhuǎn)一個向量

利用極坐標(biāo)

point rotate(double alpha) {return point(x * cos(alpha) - y * sin(alpha),x * sim(alpha) + y * cos(alpha)); }

求三角形面積

此處為有向面積

double trianglearea(Point a,Point b,Point c) {return cross(b-a,c-a)/2; }

直線交點(diǎn)

Point getline(Point p,Vector v,Point q,Vector w) {Vector u=p-q;double t=cross(w,u)/cross(v,w);return p+v*t; }

有正負(fù)性質(zhì)

點(diǎn)到直線距離

double distancetoline(Point p,point a,Point b) {Vector v1=b-a,v2=p-a;return fabs(cross(v1,v2))/length(v1); }

點(diǎn)在直線上的投影

double getlineprojection(Point p,Point a,Point b) {Vector v=b-a;return a+v*(dot(v,p-a)/dot(v,v)); }

dot(v,v):ab的模長
dot(v,p-a):ab的模長 * ap的模長

判斷兩條線段是否相交

bool segement(Point a1,Point a2,Point b1,Point b2) {double c1=cross(a2-a1,b1-a1);double c2=cross(a2-a1,b2-b1);double c3=cross(b2-b1,a1-b1);double c4=cross(b2-b1,a2-b1);return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0; }

返回是否等號
相當(dāng)于判斷b1和b2是否在線段a1a2的兩側(cè)

點(diǎn)與直線的位置關(guān)系

點(diǎn)是否在直線左側(cè)

利用叉積的性質(zhì)

bool onleft(Line l,Point p) {return cross(l.v,p-l.p)>0; }

點(diǎn)p是否在直線l的左側(cè)
大于 0說明點(diǎn)在線段的左側(cè)

點(diǎn)是否在直線上

bool on_line(Line l,Point p) {return fabs(cross(l.v,p-l.p))<eps; }

點(diǎn)是否在線段上

bool on_seg(Point a,Point b,Point p) {bool flag1=fabs((p-a),(b-a))<eps;//AB與PA的叉積=0 bool flag2=dot(p-a,p-b)<-eps;//PA與PB的點(diǎn)積<0 return flag1&flag2; }

點(diǎn)與多邊形的位置關(guān)系

判斷點(diǎn)與多邊形的內(nèi)部，外部或者邊上（不一定為凸多邊形）
判斷點(diǎn)在邊哪一側(cè)（適用于凸多邊形）

掃描法：

從給定點(diǎn)水平向右放出射線，根據(jù)射線與多邊形交點(diǎn)個數(shù)的奇偶性來判斷
考慮特殊情況：射線與頂點(diǎn)相交或與邊重合
解決方法：水平邊不考慮，頂點(diǎn)只考慮在對應(yīng)邊上較高或較低的點(diǎn)

轉(zhuǎn)角法

求出從一固定點(diǎn)沿某一方向每次連接多邊形上相鄰兩點(diǎn)所成有向角之和
若該點(diǎn)在多邊形內(nèi)，角度和為360度，在多邊形外則為0度

利用叉積來求角度（帶方向）

線段與多邊形位置關(guān)系

先判斷線段的兩個端點(diǎn)
若線段與某條邊嚴(yán)格相交，則必然不在多邊形內(nèi)

若線段與若干頂點(diǎn)相交，則需要考慮相鄰交點(diǎn)連成的線段是否在多邊形內(nèi)

多邊形的面積

與轉(zhuǎn)角法類似，只需要每次所形成的三角形的有向面積累加即可

double area(Vector<Point>poly) {double sum=cross(poly[0],poly[poly.size()-1]);for(int i=1;i<poly.size();i++)sum+=cross(poly[i],poly[i-1]);return sum/2; }

總結(jié)

以上是生活随笔為你收集整理的计算几何基础-1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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