圖形可以提示一點位於某條邊的哪一側,但程式需要一個精確的判定。叉積正好提供這個判定;把同一個行列式沿多邊形求和,便得到它的有向面積。本章把三個問題分開處理:頂點次序是否為順時針、某點是否位於邊界上,以及所用的算術能否表示答案。
1. 不用斜率的定向判斷
定義 8.1.1
(點相對於有向直線的叉積測試)
對於點 、 和 ,定義
當 位於有向直線 的左側時,此值為正;位於右側時為負;位於直線上時為零。
這個方法對垂直的邊同樣適用,而斜率公式在這種情況下會出現除以零。單憑零值只能說明 與該邊共線,並不能說明它位於有限的線段上。若要判斷是否在線段上,還須檢查兩個座標是否都落在端點所定的區間之內。
例題 8.1.2
(共線但在線段之外的點)
取 和 ,則 。點 、 和 的叉積為
第一點在左側,第二點在右側。最後的叉積為零,所以 與該直線共線;但它的 座標 在區間 之外,因此不在線段上。
快速檢查
(對 、、,計算 。 是否在線段 上?)
代入 和 。
解答 · 答案
,所以 在直線 上。但 不在 之內,所以 不在線段上。
2. 兩倍有向面積
定義 8.1.3
(兩倍有向面積(鞋帶和))
設 為簡單多邊形按邊界次序排列的頂點,令 ,,定義
面積為 。在一般的笛卡兒(Descartes)座標定向下,逆時針邊界給出 ,順時針邊界給出 。把頂點列表反轉,會令每條有向邊反向,從而改變 的正負號,但不改變其絕對值。這條公式是相對於原點的各個有向三角形貢獻之和:把區域分解成三角形時,內部的有向邊會以相反方向各出現一次,因而互相抵消。當原點位於多邊形之外時,有向貢獻是不可或缺的。輸入必須是簡單多邊形;若對任意自相交的路徑套用 ,得到的是代數意義上的有向面積,未必等於其填充區域的面積。
例題 8.1.4
(五邊形的鞋帶和)
取按逆時針排列的頂點 ,並以 封閉。正向乘積 為 ,總和為 ;反向乘積 為 ,總和為 。因此 ,面積為 。
把 保留為整數,可以精確地表示半整數面積:計算 |S| / 2,並在 |S| % 2 == 1 時(且僅在此時)在後面加上 .5。須確保所選的數據類型既能表示 ,也能表示 ;對有號類型的最小負值取絕對值可能會溢位。
例題 8.1.5
(半整數面積與順時針列表)
對三角形 ,各被加項為 、 和 ,所以 。由於 為奇數,面積為 ,輸出為 1.5。若把同一個三角形按順時針列為 ,被加項為 ,故 :面積相同,正負號相反。
快速檢查
(計算順時針正方形 的 及面積。)
以 封閉列表,計算四個被加項。
解答 · 答案
四個被加項為 、、 和 。所以 :因列表為順時針而取負值。面積為 ,與邊長為 的正方形相符。
快速檢查
(若把上面五邊形的頂點列表反轉, 與面積各是多少?)
反轉列表會令每條有向邊反向,每個被加項配對都變號。
解答 · 答案
,因為反轉列表會使總和變號。面積 不變。
3. 凸性把每條邊變成一個約束條件
假設已知輸入是一個按逆時針排列的非退化、簡單、凸多邊形。它的閉區域(包括邊界)是其各條有向邊界邊的閉左半平面的交集;它的內部則是相應開半平面的交集。因此,對每條邊計算與 的叉積。
定理 8.1.6
(點的邊測試分類)
設 是非退化的簡單凸多邊形,頂點 按逆時針排列,。對點 ,記 。則:
- 若有某個 ,則 在 外部;
- 若沒有 為負,且至少有一個為零,則 在 的邊界上;
- 若所有 ,則 嚴格位於 內部。
證明
(半平面給出三種情況)
令 為第 條邊的閉左半平面。我們引用凸多邊形的標準半平面描述:邊按逆時針排列時,。(其中一個方向是容易的:每條邊都支撐 ,所以 的每個點都在每個 內。逆向包含則需要凸性。)
因此 恰好當所有 。取逆否命題便得第一種情況:只要有某個 為負, 就在 之外。
有限個集合的交集的內部等於各集合內部的交集,而 的內部是開半平面 。所以 在 的內部恰好當所有 ,這就是第三種情況。
閉集 的邊界是 減去它的內部。所以 在邊界上恰好當所有 而並非所有 ,亦即沒有負值且至少有一個零。這就是第二種情況。
證明透視
凸性與零叉積在哪裏起作用
證明中只有一步用到凸性:等式 。對凸多邊形,每條邊都支撐 ,這給出包含關係 ;逆向包含則是半平面定理。對凹多邊形,此等式不成立,下面的反例就給出一個屬於 卻不在某個 內的點。有了這個等式之後,論證只涉及半平面:有限交集的內部等於各內部之交(有限性是必要的),而閉集的邊界是該集減去其內部。因此,單獨一個零叉積並不是邊界的憑證;它之所以有效,是因為其餘叉積全部非負,已先把 放進 之內。
凸性並非形式上的條件,一個具體的凹多邊形便可說明。
反例模式
單側測試需要凸性
人們很容易把同一個「所有叉積」測試套用到任何按逆時針排列的簡單多邊形。取凹多邊形 。它的鞋帶和為 ,所以按逆時針排列,面積為 (正方形 減去面積為 的凹口三角形 )。點 在多邊形內部:它在正方形內,而凹口只在 處與直線 相交。對邊 ,,,叉積為 。這個測試會把內部的點判為外部。修正方法是加上凸性的假設:對凹多邊形,各左半平面的交集小於多邊形本身。
例題 8.1.7
(以五邊形分類三個點)
沿用五頂點的例子。對 ,五個叉積為 ,全部為正,所以 嚴格位於內部。對 ,前兩個叉積為 和 ,第三個為 ,所以 在外部。對 ,叉積為 :沒有負值,而第一個為零,所以 在邊界上(它位於 至 的邊上)。
例題 8.1.8
(頂點屬於邊界點)
取同一五邊形的頂點 ,它位於相交於該處的兩條邊上。邊 給出 ,邊 給出 。其餘三個叉積同樣計算:邊 ,,得 ;邊 ,,得 ;邊 ,,得 。兩個零和三個正值:沒有負叉積且有零,所以 在邊界上,與預期相符。
常見錯誤
(把零叉積當作在邊界上)
取 和五邊形的第一條邊 :叉積為 ,但 並不在多邊形上。第二條邊 給出 ,所以 在外部。只有在沒有其他叉積為負時,零才是邊界的憑證。
常見錯誤
(把順時針列表交給逆時針規則)
把五邊形反向列出:。每條反向的邊會令叉積變號,所以 的五個叉積為 ,按原規則會把嚴格位於內部的點判為外部。應先計算 ,在 時反轉列表。
輸入的約定十分重要:對順時針多邊形,各正負號會反轉。使用此規則前,應先計算有向面積,並把順時針的頂點列表反轉。在非退化多邊形的前提條件下,有向面積為零的輸入應予拒絕;單憑正負號並不能證明任意輸入是簡單或凸的。
快速檢查
(對上面的五邊形,利用邊叉積把 分類。)
對五條有向邊逐一計算叉積;遇到第一個負值便可停止。
解答 · 答案
邊 :。邊 :,故 。邊 :,故 。邊 :,故 。邊 :,故 。五個叉積全部為正,所以 嚴格位於內部。
4. 成本與精確算術
命題 8.1.9
(單次掃描的線性成本)
對有 個頂點的多邊形,一次有向面積計算或一次點查詢恰好計算 個被加項或叉積,因此需要 次算術運算及 個額外純量。
證明
(對各邊的單一迴圈)
條邊 ()各被訪問一次,每次訪問只做常數次減法、乘法,以及一次比較或把值加進累計值。除輸入外,只需儲存迴圈計數器、累計和及當前的叉積。
單次有向面積計算或單次點查詢會訪問 條邊,需要 次算術運算。對 個點重複查詢需要 ;此分析並不聲稱有更快的預處理方法。若要保留多邊形以作多次查詢,需要 的儲存空間;一次掃描只需 個額外純量。
命題 8.1.10
(整數範圍上界)
若每個整數座標的絕對值不超過 ,則每個座標差的絕對值不超過 ,每個叉積值 的絕對值不超過 ,鞋帶公式中每個被加項的絕對值不超過 ,而任意 個被加項的累計和的絕對值不超過 。
證明
(逐項使用三角不等式)
兩個屬於 的數之差屬於 。叉積中的兩個乘積各自是兩個這樣的差相乘,絕對值不超過 ,兩者之差的絕對值不超過 。在鞋帶被加項 中,每個乘積的絕對值不超過 ,所以被加項不超過 ,而 個被加項之和不超過 。
這些是安全的上界,並不代表每個輸入都會同時達到它們。應選用一種能表示所需中間值的有號類型,並在進行減法或乘法之前先把座標提升至該類型。溢位發生後才取餘數或擴闊類型,都無法恢復已失去的值。簡單的累計和上界 可能超出一種足以應付單次定向測試的類型的範圍。因此,要麼使用更寬的累加器,要麼為每個部分和證明一個更緊的上界。雖然對於位於該方框內的簡單多邊形,最終的 不超過 ,但這個最終值的上界本身並不能約束各個部分和。
概念視角幾何
同一個和,看成三角形扇
固定頂點 ,把多邊形切成三角形 。則 ;五邊形的各項為 ,同樣得 。對逆時針的凸多邊形,每一項都是正數,所以部分和遞增至 ,累加器不會超出最終的界。
例題 8.1.11
(十億的座標下 64 位算術足夠嗎?)
設 。座標差不超過 ,一個乘積不超過 ,一個叉積不超過 。由於 ,只要在相減之前先把座標提升至 64 位,單個叉積就可以放進有號 64 位整數。對 的鞋帶和,上界 超過 ,所以這個簡單上界不能證明 64 位累加器足夠;需要更寬的累加器或更緊的論證。
常見錯誤
(以最終值的上界代替部分和的上界)
對簡單多邊形,最終的 不超過 ,但 是逐個被加項累加而得,而部分和有憑證的上界只是 個被加項後的 。宣稱只要某個類型能容納 就足以作累加器,便忽略了這個差距。
快速檢查
(當 ,且座標先提升至有號 64 位整數再運算時,單個叉積會溢位嗎?)
比較上界 與 。
解答 · 答案
不會。叉積的絕對值不超過 ,小於 。若座標在提升之前就以 32 位相乘,乘積可能已經溢位,所以必須先提升再運算。
檢查清單。 在套用邊測試之前,確認輸入是簡單、凸及非退化的。確定邊界的定向,在定向確定之前保留有向面積,區分直線與線段,並按實際的輸入範圍推導溢位上界。