基于掃描線的線段求交算法

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

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

中圖分類(lèi)號(hào)：TP391.41

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

1 掃描線填充算法

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

圖1 所有線段兩兩相交

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

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

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

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

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

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

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

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

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

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

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

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

上述在求交測(cè)試的過(guò)程中，如果所測(cè)試的兩條線段相交，此交點(diǎn)可能在以前求交的測(cè)試中已經(jīng)求出，此時(shí)不需重復(fù)記錄，如果以前沒(méi)有求出，則需要記錄此交點(diǎn)，為此，需要建立一個(gè)交點(diǎn)表，用于存儲(chǔ)線段的交點(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；

} ；

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

3 算法步驟

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

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

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

Step3則從EvenList中刪除一個(gè)事件點(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)了對(duì)應(yīng)的算法，圖5（b）用本文算法對(duì)圖5（a）中一組線段集所得到的線段求交算法的結(jié)果。

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

圖5 線段求交

參考文獻(xiàn)：

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

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

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

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

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