Vector Product

內積與外積

電腦做運算時,常會有浮點數誤差的問題。為避免浮點數誤差的問題,用電腦計算幾何問題時,會採用不同於一般數學運算時所用的公式和定理。

內積(inner product)(dot product)、外積(outer product)(cross product)這兩個運算只用了加法和乘法,而不包括除法,故能有效的避免除法所產生的浮點數誤差。內積與外積有許多很有用的特性。大部分的幾何問題,都可以用內積與外積來計算答案。

接著來介紹幾種內積與外積能做到的事情吧!不失一般性,以下都用二維空間當作範例。

資料結構與演算法

內積與外積是向量運算,所以得設計一個向量的資料結構。接著再為內積與外積各寫一隻函式。

這裡特別提一下:兩個向量做外積的結果為一個向量,但是我們最常使用到的其實是該向量的純量,故這裡設計外積函式的回傳值是該向量的純量。

內積、外積跟長度的關係

內積求得的是投影量,外積求得的是平行四邊形的面積量。兩者各除以單位向量後,便是長度。

d1的計算方法:先用內積求出v1投影在v2上的投影量,然後除以v2的長度,即是d1的距離。因為長度不可為負值,記得取絕對值。

d2的計算方法:先用外積求出v1 v2組成的平行四邊形面積,然後除以底的長度,便是高的長度,即是d2的距離。因為長度不可為負值,記得取絕對值。

這種計算方式肯定比三角函數方便多了!而且公式又優美!

判斷夾角

內積大於零時,兩向量夾角小於九十度;等於零時,夾角等於九十度;小於零時,夾角大於九十度、小於一百八十度。

判斷旋轉方位

外積大於零時,兩向量前後順序為逆時針順序(在一百八十度之內);等於零時,兩向量平行,也就是指夾角等於零度或等於一百八十度;小於零時,兩向量前後順序為順時針順序(在一百八十度之內)。

判斷點在線的哪一側

畫一條輔助線,便可以利用判斷旋轉方位的方法,來判斷點在線的哪一側。當然也可以判斷兩個點是否同側。

判斷點在凸多邊形的哪一側

沿著多邊形外圍繞一圈,看看點是不是在每一條邊的同側即可。若發現外積皆小於零,即表示點在多邊形內部:若發現外積等於零,即表示點在多邊形上、或在多邊形某條邊的延伸線上;若發現外積大於零,則表示點在多邊形外部。

另一種方式是,選定多邊形內一點做為原點(例如所有點的平均值),然後依角度大小排序所有點,用Binary Search找出給定的點在哪個夾角之內,最後判斷點是不是此夾角構成的三角形裡面。O(NlogN)預計算,O(logN)求答案。

判斷多邊形凹凸

沿著多邊形外圍繞一圈,看看每一條邊是不是折向同方向即可。