版本 0157fd6fe8df47cd6b5282b7ecaca2c7b21ca96e
Changes from 0157fd6fe8df47cd6b5282b7ecaca2c7b21ca96e to bce929e6452daf7c652730ae7a65db07103f5aeb
123
Week 15: LINE_Intersection
================
Computational Geometry
----------------
Q:我們要學什麼？
A:為了讓電腦幫我們運算幾何問題，學習如何將問題表示為電腦看得懂的樣子。
Struct
----------------
基本的幾何形狀有三大要素，點、線、面。
```c++
```
###點
平面中一個點(x,y)
程式：
```c++
```
###線
平面中一條線段，可以有許多不同的表示法。
>兩點式：紀錄直線上任意兩點，即可表一直線。
程式：
```c++
```
>點斜式：紀錄直線上任意一點，以及直線的斜率，即可表一直線。
程式：
```c++
```
###面
空間中一個平面，可以有許多不同表示法。
>紀錄平面上不共線三點，即可表一平面。
程式：
```c++
```
>紀錄平面的法向量，以及通過平面上一點，即可表一平面。
程式：
```c++
```
Vector
----------------
資料結構與點相同
向量可以用來進行多種運算
Ex：加、減、乘、除、內 積、外積、夾角等。
程式：
```c++
```
###加法
相同座標的項相加。
```c++
```
###減法
相同座標的項相減。
```c++
```
###乘法
所有座標的項乘一常數。
```c++
```
###除法
所有座標的項除一常數。
```c++
```
###小於
從最左邊的座標開始比，輸出最小的。
```c++
```
###全等
所有座標的項都一樣。
```c++
```
###內積
兩向量內積
```c++
```
###外積
兩向量外積
```c++
```
###長度
向量長度
```c++
```
###角度
兩向量間的夾角
```c++
```
Cross
----------------
外積的用途
```c++
```
###兩向量順逆時針的方向
```c++
```
###平行四邊形/三角形面積
```c++
```
###多邊形面積
```c++
```
###點到直線的距離
Segment
----------------
用兩點式來判斷線段相交情形
```c++
```
###相交
>正常情況下
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 之間
