兩條畫出的線段可能交叉、共用端點、沿直線重疊,也可能互不相交。程式必須從座標分清這些情況,包括垂直線段,以及兩端點重合的線段。先計算斜率會引入不必要的除法和垂直線特例;方向行列式則直接提供所需的側向資訊。
本節使用整數座標及精確運算。主要工作是一個判定問題:分類交集,而不一定求出其座標。分開這兩項工作,即使實際交點座標不是整數,也能讓分類保持精確。
從兩個位移向量推導方向測試
定義 8.2.1
(一般笛卡兒(Descartes)座標系中的方向判定)
對點 、、,定義
當 ,正結果代表 在有向直線 左側,負結果代表右側,零則代表在直線上。這個約定使用通常座標軸:x 向右增加,y 向上增加。
若 ,式子對每個 都是零,但這時沒有唯一的有向承載直線。因此,零長度線段需要以下的成員條件,不能把這個退化式子當成側向測試來解讀。
公式是向量 與 的行列式,其絕對值等於兩向量生成的平行四邊形面積,也就是三角形面積的兩倍。反轉第一個方向會改變符號。把所有點平移同一向量,不會改變位移,所以結果不變。
方向值本身不是有向距離。當 ,除以 才得到至有向直線的有向垂直距離。例如 、、 的方向值是 10,有向距離卻是 。決定左右側只需行列式,相交分類毋須計算這個距離。
共線只是屬於線段的部分條件
定義 8.2.2
(閉線段)
閉線段 包括兩個端點,由 時的點 組成。特別地,若 ,它只包含這一個點。
命題 8.2.3
(閉線段的成員判定)
點 屬於閉線段 ,當且僅當方向值為零,而且兩個座標界限都成立:
證明
(方向值為零定出直線,界限定出參數)
線段成員顯然滿足這些條件。反過來,若 ,零方向值使 在承載直線上,所以存在實數 ,使 。至少一個位移座標非零,相應的座標界限就迫使 。若 ,兩個界限則迫使 。因此,同一測試也能正確處理點線段。
證明透視
為甚麼一個非零座標已經足夠
每項假設各只用一次。方向值為零表示 與 平行;因為 ,這就給出實數 使 。然後只對 非零的某個座標 使用座標界限:,所以 ,而「 在 與 之間」恰好就是 。另一個座標的界限隨之自動成立,並非獨立的檢查。非常規的一步,是選一個線段並非常數的座標,這樣就避開斜率與垂直線的特例。論證在 處分開:那時不存在參數,界限直接把 釘在 。沒有這些界限,論證就只停在「 在直線上」。
所以只看方向值,永遠不足以判定成員;下一個具體例子說明這點。
反例模式
方向值為零,不等於在兩端點之內
點 、、 共線,所以第三點相對前兩點的方向值為零。但它的 x 座標超過二,仍在兩點的閉線段之外。只測試零方向值,就會把無限承載直線錯當成有限線段。
用兩組側向測試判定真正交叉
對線段 、,定義
真正交叉指兩條不共線線段,在各自嚴格內部交於一點。當且僅當 嚴格異號,而且 也嚴格異號,才會發生。零不算這裏的異號,而屬於邊界情況。
定理 8.2.4
(真正交叉的判定準則)
設 與 是長度為正、且不在同一直線上的線段。它們有一個對雙方都是內部點的公共點,當且僅當 嚴格異號,而且 嚴格異號。
證明
(方向值沿線段是仿射函數)
沿 ,相對於 的方向值等於 。
設 嚴格異號。這個式子便有唯一零點,出現在 。兩直線不平行,因為平行方向會使兩個方向值相同。所以兩條承載直線的唯一交點嚴格在線段 內部。 異號對同一個唯一直線交點給出同樣結論,即它在 內部,所以該點是兩線段的內部點。
反過來,設 ()是公共點,同時是 的內部點。這時 在直線 上,所以 。因此 不是全為零,便是嚴格異號。若全為零,、 都在直線 上,與兩線段不在同一直線矛盾。所以 嚴格異號;把兩線段的角色對調,同一論證給出 嚴格異號。
證明透視
每組符號只證明一條線段
證明的引擎是:方向值沿線段是仿射函數,所以兩個端點的值決定它在哪裏為零。嚴格性使零點落在開區間內:若有端點的值為零,交點就在端點,屬於邊界情況。兩個同號的嚴格值,則使零點落在線段之外,或使兩直線平行。不共線只用於必要性,用來排除 。第一組符號說明直線 穿過線段 ;第二組說明直線 穿過線段 。證明能夠收尾,是因為兩項陳述指向同一個點,即兩直線的唯一交點。只留一組符號,就只得到一半結論。
每組符號只證明其中一條線段,下面的例子把這個缺口具體化。
反例模式
只跨越其中一條承載直線並不足夠
取 、、、。、,顯示 跨越通過 的直線。
但 、 同號。直線交點是 ,已越過端點 ,所以線段不相交。排除此情況的正是第二組符號。
例題 8.2.5
(不用斜率計算的精確交叉)
取 、、、,四個方向值為
兩組都嚴格異號。兩條線段的參數式各在參數 相遇,交點為 。判定本身只需要符號,不需要求該點時用到的除法。
整數輸入不代表交點也是整數:從 到 的線段,與從 到 的線段,真正交叉於 。把交點四捨五入至整數座標,不是精確判定的一部分。
明確處理共線與退化情況
若四個方向值全為零,而且至少一條線段長度非零,所有端點都在該線段的承載直線上。把點按字典序排列:先比較 x,再比較 y。在非垂直直線,這個次序沿著 x 排列;在垂直直線,則沿著 y 排列。因此,可用這個次序中的區間來測試重疊。
把候選交集端點設為
其中最小與最大都使用字典序。若 ,線段不相交;若 ,共用一個點;若 ,則沿正長度線段重疊。
兩條點線段的四個方向值也全為零,即使兩點不同,而且沒有指定唯一共同承載直線。它們的字典序區間是單元素,因此同一重疊規則仍能正確判斷兩點是否相同。
若四個方向值並非全零,某個零值仍可能代表共用端點,或某個點線段位於另一線段上。應對相應端點使用完整的 on_segment 測試。沒有座標界限的零方向值仍不足夠。
例題 8.2.6
(邊界情況屬於閉線段的使用條件)
除另有說明外,下列例子都在 x 軸上。
| 第一線段 | 第二線段 | 分類 |
|---|---|---|
| 至 | 至 | 單點接觸 |
| 至 | 至 | 正長度重疊 |
| 至 | 至 | 不相交 |
| 點 | 至 | 單點接觸 |
| 點 | 至 | 不相交 |
| 點 | 點 | 單點接觸 |
| 點 | 點 | 不相交 |
「點」代表兩端點重合的線段。單點接觸可以出現在另一線段內部,不一定是兩條線段共同的端點。
例題 8.2.7
(T 形接觸需要零方向值加成員測試)
取 、、、。則 ,,第一組不是嚴格異號,所以不是真正交叉。又 ,,嚴格異號。由於 ,把 對 做成員測試:方向值為零,且 、,所以 在線段 上。分類為 touch:垂直線段終止於水平線段的內部。單靠零方向值不能下此結論;若 改為 ,方向值仍是零,界限卻不成立。
命題 8.2.8
(兩條閉線段的精確分類)
設 與 是閉線段,長度可以為零,方向值 如上。
- 若 ,交集是字典序中由 至 的區間: 時為空, 時為一點, 時為正長度線段。
- 否則交集至多一個點。它非空,當且僅當兩線段真正交叉,或某個方向值為零的端點對另一線段通過閉線段成員測試。
證明
(按承載直線的配置分情況)
設四個方向值全為零。若 長度為正,則 把 、 放在直線 上;若 長度為正,則 把 、 放在直線 上;若兩者都是點,就只有兩個點。每種情況下,所有端點都在同一直線上,字典序與沿直線的位置一致,所以每條線段就是其端點在此次序下之間的區間;兩個這樣區間的交集是 , 時為空。
現設四個方向值並非全為零, 是公共點。若其中一條線段是點,例如 ,則 在 上,由成員命題,即 且 通過界限測試; 的情況對稱。若兩者長度都為正而兩直線平行,則兩直線不同時沒有公共點,重合時四個方向值全為零。否則兩直線恰交於一點, 就是該點,交集至多一點。若 在兩線段內部,由上面的準則,兩線段真正交叉;否則 是某線段的端點,並在另一線段上,所以該端點方向值為零,並通過成員測試。反過來,每個所列條件都由交叉準則或成員判定給出一個公共點。
常見錯誤
(用非嚴格不等式測試乘積)
一個誘人的捷徑,在 且 時報告相交。對 、、、,四個方向值全為零,兩個乘積都是零,捷徑便報告接觸。但這兩條閉線段不相交:,,所以 。必須先把共線情況分出,再用區間測試決定。
常見錯誤
(在垂直線上只比較 x 座標)
從 到 與從 到 的線段, 值都只有 ,所以只比較 的重疊測試看到相同的區間,報告接觸。這兩條線段其實不相交。字典序在 相同時比較 ,得 、,所以 。
精確整數分類函數
輸入點以前提要求為含兩個整數的元組,函數不驗證座標類型或元組形狀。它回傳 cross 表示真正交叉、touch 表示邊界或退化的單點接觸、overlap 表示正長度共線交集,否則為 disjoint。這些字串分類交集,而不是回傳交點座標。
def orient(a, b, p):
return ((b[0] - a[0]) * (p[1] - a[1])
- (b[1] - a[1]) * (p[0] - a[0]))
def on_segment(a, b, p):
return (orient(a, b, p) == 0
and min(a[0], b[0]) <= p[0] <= max(a[0], b[0])
and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))
def opposite(x, y):
return (x < 0 < y) or (y < 0 < x)
def segment_relation(a, b, c, d):
o1, o2 = orient(a, b, c), orient(a, b, d)
o3, o4 = orient(c, d, a), orient(c, d, b)
if o1 == o2 == o3 == o4 == 0:
lower = max(min(a, b), min(c, d))
upper = min(max(a, b), max(c, d))
if lower > upper:
return "disjoint"
return "touch" if lower == upper else "overlap"
if opposite(o1, o2) and opposite(o3, o4):
return "cross"
if ((o1 == 0 and on_segment(a, b, c))
or (o2 == 0 and on_segment(a, b, d))
or (o3 == 0 and on_segment(c, d, a))
or (o4 == 0 and on_segment(c, d, b))):
return "touch"
return "disjoint"
例如,segment_relation((0,0),(4,2),(1,3),(3,-1)) 回傳 cross,只有一組跨側的反例則回傳 disjoint。反轉任一線段端點,或交換兩條線段,都不改變分類,即使某些方向符號會改變。
函數直接處理垂直線段、重複端點及相同點線段,不需要除法、斜率比較或指定容差。這個精確整數前提,也不能用來支持把每個零測試隨意改成浮點 ;近似座標需要另一套數值模型與分析。
選固定位元類型前,先分析算術範圍
程式使用常數次算術操作與比較。若整數座標不受大小限制,這是操作次數,而不是常數位元執行時間的聲稱。若每個座標的絕對值至多 ,每個差的絕對值至多 ,每個乘積至多 ,行列式便有保守界限
這已足以推算所需數值範圍,並不聲稱最緊。對 位元座標,差與行列式有 位元,必須計入乘法成本。Python 整數保持精確;固定位元版本則必須讓差和乘積本身使用足夠寬的表示,不能在溢位後才擴大結果類型。
像以上直接用比較判斷異號,就避免為了判斷負乘積而計算 。兩個行列式相乘所需的中間範圍,比單一行列式更大;幾何判定只需要它們的符號。
練習與詳解
快速檢查
(對 、、,求方向值及至有向直線的有向距離。為甚麼只判定 在哪一側時,不需要正規化?)
只有需要距離時,才除以 的長度。
解答 · 答案
方向值為 。因為 ,除以 得有向距離 。正的正規化因子不改變符號,所以方向值已能正確判定左側。
快速檢查
(對 、、、,列出四個方向值。為甚麼第一組異號不能證明線段相交?)
除了 、,也要算 、。
解答 · 答案
數值為 。 跨越通過 的無限直線,但交點 在 外。另一組不異號,所以完整的真正交叉測試會拒絕此情況。
快速檢查
(在 軸上,先比較 至 與 至 的線段,再比較 至 與 至 的線段。、 分別是甚麼?兩組分類有何分別?)
把 、 當作字典序的最大與最小來計算。
解答 · 答案
第一組候選交集由 至 ,有正長度,回傳 overlap。第二組有 ,為單點 touch。區分兩者的正是端點次序中的嚴格小於與相等。
快速檢查
(若 ,另一線段從 到 ,為甚麼零方向值不足夠?若該點改為 ,或兩條線段都是同一個點,又會怎樣?)
比較兩個單元素區間。
解答 · 答案
全部方向值為零,但 的單元素區間與另一端點區間不重疊,所以答案為 disjoint。點在 時得到 touch,兩條線段都是同一點時也得到 touch。包圍盒與有序區間條件已處理這些情況,毋須替一個點虛構有向直線。
快速檢查
(把所有點平移同一個固定向量,四個方向值如何改變?若交換 、,第一組符號和最終相交分類又如何改變?)
方向值是兩個位移向量的行列式。
解答 · 答案
平移不改變位移向量,所以所有方向值不變。反轉 會令 變號,並交換 。異號、零與線段成員條件仍描述同一幾何線段,所以分類不變。
快速檢查
(每個座標絕對值至多 ,推導文中的保守行列式界限。固定位元實作為甚麼可以優先直接比較符號,而不是計算兩個方向值的乘積?)
先界定每個差,再界定每個乘積。
解答 · 答案
每個座標差的絕對值至多 ,兩個乘積各至多 ,所以相減的絕對值至多 。兩個這樣的行列式相乘,可能需要大得多的範圍;直接比較正負能避免該額外乘積,卻完成判定所需的同一符號決策。