Week 15: LINE_Intersection ================ Computational Geometry ---------------- Q:我們要學什麼? A:為了讓電腦幫我們運算幾何問題,學習如何將問題表示為電腦看得懂的樣子。 Struct ---------------- 基本的幾何形狀有三大要素,點、線、面。 ```c++ ``` ###點 平面中一個點(x,y) 程式: ```c++ typedef struct Point{    double x,y;    Point(double x=0 ,double y=0) : x(x) ,y(y) {} }Point; ``` ###線 平面中一條線段,可以有許多不同的表示法。 >兩點式:紀錄直線上任意兩點,即可表一直線。 程式: ```c++ ``` >點斜式:紀錄直線上任意一點,以及直線的斜率,即可表一直線。 程式: ```c++ ``` ###面 空間中一個平面,可以有許多不同表示法。 >紀錄平面上不共線三點,即可表一平面。 程式: ```c++ ``` >紀錄平面的法向量,以及通過平面上一點,即可表一平面。 程式: ```c++ ``` Vector ---------------- 資料結構與點相同 向量可以用來進行多種運算 Ex:加、減、乘、除、內 積、外積、夾角等。 程式: ```c++ typedef Point Vector; Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); } Vector operator - (Point A,Point 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)P2.x)min.x=P2.x,max.x=P1.x;    else     min.x=P1.x,max.x=P2.x;    if(P1.y>P2.y)min.y=P2.y,max.y=P1.y;    else     min.y=P1.y,max.y=P2.y;    if(min.x<=P3.x&&P3.x<=max.x&&min.y<=P3.y&&P3.y<=max.y)return 1;    else return 0; } int segments_intersect(Point A,Point B,Point C,Point D){    //check if segment AB CD has intersection return 1 yes 0 no    double d1=Cross( A-C , D-C );    double d2=Cross( B-C , D-C );    double d3=Cross( C-A , B-A );    double d4=Cross( D-A , B-A );    if(dcmp(d1*d2)<0 && dcmp(d3*d4)<0) return 1;    if( dcmp(d1)==0 && in_interval(C,D,A)==1 )return 1;    if( dcmp(d2)==0 && in_interval(C,D,B)==1 )return 1;    if( dcmp(d3)==0 && in_interval(A,B,C)==1 )return 1;    if( dcmp(d4)==0 && in_interval(A,B,D)==1 )return 1;    return 0; ``` ###相交 >正常情況下 ![](/intersectionNormal.png) A和B在異側,C和D也在異側 A和B在異側 : CA Cross CD 和 CB Cross CD 異號 C和D在異側 : AC Cross AB 和 AD Cross AB 異號 >例外 ![](/intersectionExcrption.png) 交點重疊或線段重疊 CB Cross CD = 0 且 B要在CD內 B要在CD內 : B的x/y介於C和D的x/y 之間