Distance

Distance

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

Distance from a Point to the Origin

點到原點的距離。

如果你願意,也可以運用dot來計算距離。但沒有多大好處。

開根號相當耗費時間。有時候做一些幾何計算時,會將數學式子簡化到不必開根號,以節省計算時間。因此,設計不開根號的程式碼,有時候也是會有用途的。

Distance from a Point to a Point

點到點之間的距離相信大家都會算。

Distance from a Point to a Line

用數學計算時常會用ax+by=c來表示直線,但是這種方法會用到大量除法運算,造成誤差。這裡只用兩個點來代表直線,並用外積來計算長度,一切從簡。

外積可求出v1 v2組成的平行四邊形面積,然後除以v2的長度,便是垂直距離。外積可能會有負值,請記得取絕對值,才不會得到負的距離。

Distance from a Point to a Segment

點到線段的最短距離,有時候是點到線上的垂直距離,有時候卻是點到線段端點的距離。

由圖片可觀察到點到線段的距離,和三點共線、點在線上這些因素無關。就將空間劃分為垂直距離區和端點距離區兩塊即可。這只是一種劃分方式,各位也可以自行發明適合的劃分方式。

要判斷點位於哪一區,利用內積即可:兩條向量夾角若小於九十度,則內積為正值;等於九十度時,內積為零;大於九十度時,內積為負值。

Distance from a Segment to a Line

線段到線的距離。

這個問題可簡化成判斷線段的兩個端點是不是在線的同一邊。如果在同邊則需要計算距離,如果在不同邊,或者有任一點在線上,則距離為零。判斷同邊得利用外積:向量呈順時針順序外積得正值,逆時針得負值。

Distance from a Segment to a Segment之一

線段到線段的距離。

這個問題似乎沒有更簡單的方式:如果線段有相交,則距離為零;如果不相交,則窮舉所有的端點到線段距離。點到線段的距離已經在先前的段落提過了,現在剩下線段相交尚待解決。

線段相交,也就是一條線段被另一條線段分為兩邊。所以我們只要檢查線段的兩頭,是不是位於另一條線段的兩側即可。

考慮線段平行的特殊情況。兩線段平行但不共線時,恰好可以直接用端點到線段的距離求出答案。至於兩線段共線時,不管兩線段有沒有相交,恰好也可以直接用端點到線段的距離求出答案。結論就是:只要兩線段平行或共線,便可以直接用端點到線段的距離求出答案,不用理會這兩條線段是否相交。

各位可以整合「線段相交」與「點到線段距離」的程式碼,避免重複計算相同的向量,以節省時間。

Distance from a Segment to a Segment之二

線段相交,可以想像成是兩條交錯的四邊形對角線。換句話說,就是將線段的端點安排成四邊形的頂點,讓四邊形的對角線成為原來的兩條線段。如此一來,只要用一個四邊形,便可代表這兩條線段。

凸四邊形的對角線,都會相交;凹四邊形、交叉四邊形的對角線,不會相交──於是判斷線段相交,可以轉化做判斷凸四邊形。要判斷凸多邊形,只要順著多邊形的外圍繞一圈,看看是否一直往同側轉彎即可。判斷轉彎得利用外積:順時針轉彎外積得正值,逆時針得負值。

另外,外積等於零則表示線段的端點產生三點共線,分析各種情況後,發現此時可以直接用端點到線段的距離求出答案。

各位可以整合「線段相交」與「點到線段距離」的程式碼,避免重複計算相同的向量,以節省時間。

Distance from a Line to a Line

線到線的距離。

兩線相交距離為零,兩線平行距離為l1上任取一點到l2的距離。判斷平行得利用外積:外積為零時,表示兩向量平行,平行四邊形面積為零。

題目在這裡。並不是很多。

UVa 152 10514 10709