Week 15: LINE_Intersection

Computational Geometry

Q:我們要學什麼？

A:為了讓電腦幫我們運算幾何問題，學習如何將問題表示為電腦看得懂的樣子。

Struct

基本的幾何形狀有三大要素，點、線、面。

###點 平面中一個點(x,y)

程式：

###線 平面中一條線段，可以有許多不同的表示法。

兩點式：紀錄直線上任意兩點，即可表一直線。

程式：

點斜式：紀錄直線上任意一點，以及直線的斜率，即可表一直線。

程式：

###面 空間中一個平面，可以有許多不同表示法。

紀錄平面上不共線三點，即可表一平面。

程式：

紀錄平面的法向量，以及通過平面上一點，即可表一平面。

程式：

Vector

資料結構與點相同

向量可以用來進行多種運算

Ex：加、減、乘、除、內 積、外積、夾角等。

程式：

###加法 相同座標的項相加。

###減法 相同座標的項相減。

###乘法 所有座標的項乘一常數。

###除法 所有座標的項除一常數。

###小於 從最左邊的座標開始比，輸出最小的。

###全等 所有座標的項都一樣。

###內積 兩向量內積

###外積 兩向量外積

###長度 向量長度

###角度 兩向量間的夾角

Cross

外積的用途

###兩向量順逆時針的方向

###平行四邊形/三角形面積

###多邊形面積

###點到直線的距離

Segment

用兩點式來判斷線段相交情形

###相交 >正常情況下

A和B在異側，C和D也在異側

A和B在異側 : CA Cross CD 和 CB Cross CD 異號

C和D在異側 : AC Cross AB 和 AD Cross AB 異號

例外

交點重疊或線段重疊

CB Cross CD = 0 且 B要在CD內

B要在CD內 ： B的x/y介於C和D的x/y 之間