摘 要：本文以基于掃描線算法求線段的交點(diǎn)，首先設(shè)有一條掃描線l，從高于所有線段的位置起，自上而下地掃描整個平面，與當(dāng)前掃描線相交的線段構(gòu)成一個掃描線狀態(tài)結(jié)構(gòu)，在掃描線從上個事件點(diǎn)移到下個事件點(diǎn)時，要根據(jù)事件點(diǎn)的不同來更新掃描線的狀態(tài)結(jié)構(gòu)。該算法能避免盲目求交時大量無效求交測試。

關(guān)鍵詞：線段；掃描線；求交

中圖分類號：TP391.41

在地理信息系統(tǒng)中，線段求交是地圖疊合處理必須要面對的問題，傳統(tǒng)的做法是對所求區(qū)域內(nèi)的所有線段對依次進(jìn)行求交測試。當(dāng)待求線段數(shù)比較少時，采用該方法能夠很方便的得到結(jié)果，且容易實(shí)現(xiàn)；但線段數(shù)目比較龐大是，傳統(tǒng)的方法就顯得“力不從心”了，本文采用掃描線的方法求線段的交點(diǎn)，適用于解決大規(guī)模線段求交的問題。

1 掃描線填充算法

線段求交最簡單的做法是依次判斷每一對線段，測試它們是否相交，如果相交，則記錄交點(diǎn)，但這種算法的時間復(fù)雜度是O（n2），如果所面對的是如圖1所示的問題，即線段集間兩兩相交，此算法的效率也是最優(yōu)解，因?yàn)闊o論采用何種算法，都需要計算每對線段間的交點(diǎn)，但實(shí)際情況是只有少數(shù)線段對間存在交點(diǎn)，即交點(diǎn)的個數(shù)遠(yuǎn)遠(yuǎn)小于線段條數(shù)n的平方級。此時，我們稱線段的交點(diǎn)為“敏感點(diǎn)”，適用于處理此種情況的算法稱為“交點(diǎn)敏感”的算法。

圖1 所有線段兩兩相交

定義1 事件點(diǎn)：線段端點(diǎn)、線段的交點(diǎn)稱為事件點(diǎn)

定義2 掃描線狀態(tài)表：與當(dāng)前掃描線相交的所有線段構(gòu)成的集合稱為“掃描線的狀態(tài)表”。掃描線狀態(tài)表按照與當(dāng)前掃描線相交的線段自左向右排序。

設(shè)有一條掃描線l，從高于所有線段的位置起，自上而下地掃描整個平面，當(dāng)掃描線到達(dá)某個事件點(diǎn)時才需要更新掃描線的狀態(tài)表，此時需要進(jìn)行一些相交測試，根據(jù)所觸及事件點(diǎn)的不同，掃描線狀態(tài)結(jié)構(gòu)表要做不同的處理，事件點(diǎn)分為線段上端點(diǎn)、線段下端點(diǎn)、線段交點(diǎn)，因此，在更新掃描線狀態(tài)表時要分為三種情況進(jìn)行討論。

1.1 事件點(diǎn)為線段的上端點(diǎn)

上端點(diǎn)所對應(yīng)的線段開始與掃描線相交，此時需要測試該線段和那些與當(dāng)前掃面線相交的線段是否相交。以圖2為例，在掃描線未到達(dá)S3的上端點(diǎn)前一瞬間掃描線的狀態(tài)表順序?yàn)镾2、S1、S4。當(dāng)掃描線到達(dá)S3的上端點(diǎn)，S3開始與當(dāng)前掃描線相交，此時掃描線的狀態(tài)表更新為S2、S1、S3、S4。也即S3在掃描線的狀態(tài)表中位于S1與S4之間，因此需要對S3 分別與S1和S4做求交測試。

圖2 事件點(diǎn)為上端點(diǎn)

1.2 事件點(diǎn)為線段的下端點(diǎn)

下端點(diǎn)所對應(yīng)的線段將不再與掃面線相交，因此需要將該線段從狀態(tài)表中刪去，以圖3為例，掃描線到達(dá)S3下端點(diǎn)的前一瞬間，掃描線狀態(tài)表的狀態(tài)為S2、S1、S3、S4，當(dāng)掃描線到達(dá)S3下端點(diǎn)時S3從狀態(tài)表中刪除，此時掃描線狀態(tài)表的狀態(tài)變?yōu)镾2、S1、S4，也即S1與S4變?yōu)橄噜彽木€段，需要對他們進(jìn)行求交測試。

圖3 事件點(diǎn)為下端點(diǎn)

1.3 事件點(diǎn)為線段的交點(diǎn)

以圖4為例，在掃描線進(jìn)入事件點(diǎn)前一瞬間，S4與S1相鄰，S3與S5相鄰，當(dāng)掃描線到達(dá)下一個事件點(diǎn)前，掃描線狀態(tài)表的順序變?yōu)镾2、S1、S3、S4、S5，也即變?yōu)镾3與S1相鄰，S4與S5相鄰，此時需要對它們進(jìn)行求交測試。

圖4 事件點(diǎn)為線段的交點(diǎn)

上述在求交測試的過程中，如果所測試的兩條線段相交，此交點(diǎn)可能在以前求交的測試中已經(jīng)求出，此時不需重復(fù)記錄，如果以前沒有求出，則需要記錄此交點(diǎn)，為此，需要建立一個交點(diǎn)表，用于存儲線段的交點(diǎn)。

2 數(shù)據(jù)結(jié)構(gòu)

實(shí)現(xiàn)本文算法用到以下數(shù)據(jù)結(jié)構(gòu)：

（1）事件點(diǎn)

class point

{

double x，y

} ；

（2）線段

class Line

{

point p1，p2；

} ；

對于每條線段p1存儲上端點(diǎn)，p2存儲下端點(diǎn)，如果線段為水平線段時，p1存儲左端點(diǎn)，p2存儲右端點(diǎn)。

3 算法步驟

實(shí)現(xiàn)本文算法步驟如下：

Step1初始化一個事件隊(duì)列EvenList，事件隊(duì)列的初值為線段端點(diǎn)序列，在該序列中，端點(diǎn)從上到下，處于同一水平線的上端點(diǎn)從上到下排序。初始化一個初值為空的交點(diǎn)鏈表IntersectList；初始化一個初值為空的掃描線狀態(tài)表StatusList；

Step2如果EvenList不為空，轉(zhuǎn)到Setp3 ，否則轉(zhuǎn)到Step4；

Step3則從EvenList中刪除一個事件點(diǎn)， 根據(jù)事件點(diǎn)的不同更新掃描線狀態(tài)結(jié)構(gòu)表。如果求出新的交點(diǎn)，則把新交點(diǎn)添加到IntersectList，并按順序插入到EvenList中；

Step4 算法結(jié)束。

4 實(shí)驗(yàn)結(jié)果

根據(jù)本文基于掃描線的線段求交算法，筆者在VC++6.0環(huán)境下實(shí)現(xiàn)了對應(yīng)的算法，圖5（b）用本文算法對圖5（a）中一組線段集所得到的線段求交算法的結(jié)果。

（a） 線段集 （b） 線段集交點(diǎn)

圖5 線段求交

參考文獻(xiàn)：

[1]吳立新，史文中.地理信息系統(tǒng)原理與算法[M].科學(xué)出版社，2005.

[2]周陪德.計算幾何——算法設(shè)計與分析（第4版）[M].清華大學(xué)出版社，2011.

[3]Joseph O’Rourke.Computation Geometry in C[M].機(jī)械工業(yè)出版社，2005.

[4]Mark de Berg等著，鄧俊輝譯.計算幾何：算法與應(yīng)用（第3版）[M].清華大學(xué)出版社，2009.

作者簡介：李源（1981-），男，碩士，助教，主要研究方向：計算機(jī)圖形學(xué)、地理信息系統(tǒng)；李永鋼（1985-），男，碩士，助教，主要研究方向：面向服務(wù)體系結(jié)構(gòu)，數(shù)據(jù)倉庫與數(shù)據(jù)分析。