Intersection

Intersection

這裡簡單的介紹二維座標平面上的相交計算方法。

Intersetion point of a Line and a Line

線與線的交點。可參考:http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

這裡介紹一個利用外積來計算交點的方法,其實就是上述網頁中的方法。請見下圖:

原則上,就是以p1為基準點,p34為平行四邊形的底,然後利用兩個平行四邊形的高的比例,便能求出p1到p2與p1到交點的距離比例。

平行四邊形的面積可用外積運算求出,所以這個方法相當方便。各位可依照下圖所列舉的各種情況(補上線段的延長線,使之為線),驗證此方法是有效的,並試著整理出例外情況。

實作程式碼時,要注意外積的順序,外積的順序不同會產生出正負號的差異。

Intersetion point of a Segment and a Segment

線段與線段的交點。跟上一段所述相同,只是要小心判斷兩個平行四邊形的高的比例是不是為負值、或者超過1,此即表示線段p34超出了線段p12的範圍,不會相交。至於範圍是指p1和p2兩點,以平行p34的方向所畫出的邊界線作為範圍,如下圖所示:

另外,除了以p1為基準點,還要再以p3為基準點再算一遍,才能確定兩線段到底有沒有相交。

至於兩線段共線的情況這裡就不予討論。大家可以自己揣摩看看。【待補文字】

小細節就略過,程式碼如下:

由於p13與p31只差一負號,故可以用p13代替p31。另外c2與c4也只差一負號,故可以用c2代替c4。於是程式碼可再精簡。

UVa 137 191 273 378 866 10902 10907