在對圖進行計算時，很常用的一個操作就是求若干條線段的交點，比如對圖的疊加、截窗，需要頻繁地計算線段交點，如果求交算法效率很低，上層的算法再優秀也表現不出好的性能。
兩條線段交點的計算
先考慮一個很簡單的情形：只有兩條線段，求它們是否相交，如果相交，交點在哪？
如上圖，如果線段[a0,a1]與[b0,b1]相交，則端點a0、a1必定落在[b0,b1]兩側，同時端點b0、b1必定落在[a0,a1]兩側。只要這兩個條件同時滿足，即認為兩線段相交。（一條線段的端點落在另一條線段上也認為是兩線段相交）
一種比較快速的方法是使用向量外積。三角形面積公式的向量形式為：
面積恰是兩邊a,b外積大小的一半。而外積是有方向的。判斷兩點是否同側，只需要判斷外積是否同號。比如對上面的圖進行如下計算：
s1=(xb0-xa0)*(yb1-ya0)-(xb1-xa0)*(yb0-ya0)
s2=(xb0-xa1)*(yb1-ya1)-(xb1-xa1)*(yb0-ya1)
其中s1方向垂直屏幕向內，s2方向垂直屏幕向外，兩者異號，所以點a0、a1位於線段[b0,b1]兩側。
同理，計算s3=(xa1-xb0)*(ya0-yb0)-(xa0-xb0)*(ya1-yb0)和s4=s2-s1+s3異號，可以確定b0、b1落在[a0,a1]兩側。（由面積恆等關係s4-s3=s2-s1可以直接計算s4）
確定兩條線段相交，接著就要計算交點。這一步沒有必要用向量計算，只要求解直角座標下的方程組就好。不過需要注意端點重合的情況。
//inte[i][0]為交點x座標
//inte[i][1]為交點y座標
//_inteCount為之前找到的交點總數
if(xa0==xa1 || xb0==xb1)
{
if(xa0==xa1)
{
b=(yb0-yb1)/(xb0-xb1);
inte[_inteCount][0]=xa0;
inte[_inteCount][1]=b*(inte[_inteCount][0]-xb1)+yb1;
}else{
a=(ya0-ya1)/(xa0-xa1);
inte[_inteCount][0]=xb0;
inte[_inteCount][1]=a*(inte[_inteCount][0]-xa1)+ya1;
}
}else{
a=(ya0-ya1)/(xa0-xa1);
b=(yb0-yb1)/(xb0-xb1);
inte[_inteCount][0]=(a*xa1-b*xb1-ya1+yb1)/(a-b);
inte[_inteCount][1]=a*(inte[_inteCount][0]-xa1)+ya1;
}
多條線段交點的計算
現在考慮有很多條線段的情形。如果把這N條線段兩兩檢查交點，時間複雜度是O(n^2)，在線段數目很多時，計算速度會非常慢。這時，就需要掃描線算法了。
觀察一下那些相交的線段有什麼特點。把每條線段向y軸投影：
可以看出相交的線段的投影會彼此疊加，而且投影不重合的線段也不可能相交。
利用這個特性，用一條平行的直線從上到下平移，平移的過程中會與某些線段相交，在任何時刻只考慮這些與掃描線相交的線段之間是否相交。現考慮某時刻這條掃描線上的M條線段（M<=N）：
在這條掃描線上，相交的線段一定是相鄰的，比如b和c。雖然存在b和d不相鄰也相交的情況，但由於算法的特點，處理到那個交點時，b和d一定是相鄰的。比如：
掃描線在點T上方時，c與d相鄰，但b與d不相鄰。找到交點T。但掃描線經過T到達S上方時，c與d的位置交換了，此時b與d相鄰而且相交。所以，只有相鄰的線段才有可能相交。
我們把相鄰的線段稱為互為鄰居，比如a是b的左鄰居，c是b的右鄰居。
在掃描線行進的過程中，需要動態維護兩個數據結構：
- 一條鏈表，負責記錄所以線段的端點和已經找到的交點，每個點按y遞減順序存儲（y相同的，按x遞增排序）；
- 一棵二叉樹，負責記錄與掃描線相交的線段（確切地說，保存的是每條線段的上端點），每條線段按照上端點的x座標遞增順序存儲。
所謂“掃描”，即程序從頭到尾依次處理鏈表上的每個點，在每處理一個新的點時，會相應地更新鏈表和二叉樹。
新的點共有三種，相應的處理方法如下所述：
新點是某線段的上端點：
把這個端點存入二叉樹，然後在樹中找到p0的左鄰居pa和右鄰居pb，檢查p0與pa是否相交，p0與pb是否相交。如果有交點，把交點存入鏈表。
比如b的上端點接觸到掃描線，只需要檢查a與b是否相交，b與c是否相交。
新交點一定會在掃描線的下方，它在鏈表中的位置也一定在p0的後面，會在未來某個時刻得到處理。因為如果這個交點的位置在p0之前，說明掃描線在之前已經經過了這個交點，程序也已經處理過它了。
新點是某線段的下端點
在二叉樹內找到p1相應的上端點，然後找到上端點的左鄰居pa和右鄰居pb。把p0從二叉樹刪除，檢查pa與pb是否相交。如果有交點，把交點存入鏈表。
比如b的下端點離開掃描線，刪除b後檢查a與c是否相交。
新點是交點
輸出這個交點的座標。然後在二叉樹中找到這個交點所在的兩條線段pl和pr（假設pl在pr的左邊），再找到pl的左鄰居pa，和pr的右鄰居pb，檢查pr與pa是否相交，pl與pb是否相交。如果有交點，把交點存入鏈表。
比如b與c的交點接觸到掃描線，檢查a與c是否相交，b與d是否相交。
以上就是掃描線算法的全部細節。採用這種算法，可以把時間複雜度降到O(nlogn+klogn)，其中n是線段數目，k是交點數目。如果想了解這個時間是怎樣計算出來的，可以參考《Computational Geometry Algorithms and Applications》（作者：M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf）。
我用C實現了這個算法，並且用OpenGL繪製出所有線段及交點。代碼可以在這裡下載：
https://github.com/johnhany/SegmentsIntersection
這是程序運行的結果：
