掃描線法填充多邊形

原理

如下圖所示多邊形：

簡述

直線y=1，2，3……8順序掃描多邊形，以直線y=3為例，它與多邊形的邊有4個交點，将這4個交點的x坐标儲存下來，兩兩之間畫線，也就是（A，B）（C，D）之間畫線。對于每一個y都是兩兩之間畫線。現在考慮直線y=2，它與多邊形有3個交點，很顯然是F，G之間畫線，那麼p1怎麼處理呢？可以觀察到p1是多邊形邊的一個端點，是兩條邊的交點，是以，可以選擇将p1看作兩個點存儲，這樣（p1，p1）之間畫線，就是描一個點。或者不存儲p1，隻在（F，G）之間畫線。我采用的是不存儲p1。

活性邊表

具體每一條掃描線對應的坐标存儲在活性邊表Aet中，每一條掃描線對應一個連結清單，連結清單中的節點類型為

x

dx

ymax

next

其中，x為交點的x坐标，dx為相交直線的x方向增量(x2-x1)/(y2-y1)，ymax為直線可以到達的最大y值。由于我采用的是當掃描線與邊的端點相交時不存儲此交點，是以，掃描線y=1的Aet中沒有存儲坐标，y=2中不存儲p1，隻存儲F，G的x坐标以及F，G所在直線的斜率倒數。

新邊表

新邊表Net用來記錄y為多少時與新的邊相交，每一條掃描線也對應一個連結清單，結點類型和Net中的結點類型相同。 如圖中的新邊表中，y=1應該記錄  （p2，p3），（p4，p3）兩條直線的資訊；y=2應該記錄（p1，p6），（p1，p2）兩條直線的資訊，y=6記錄（p4，p5）一條邊的資訊，y=7記錄（p6，p5）一條邊的資訊。

掃描過程

1、建立新邊表（對于斜率為0的直線不計入新邊表）； 2、建立y=i對應的活性邊表：       檢查y=i對應的新邊表中是否有結點，若有，則将這些結點加入活性邊表 ;      檢查y=i-1對應的活性邊表，對于ymax=i的結點，忽略不計（也可以記錄，根據個人選擇） ，如果ymax<i，則将結      點中x=x+dx後，把結點加入y=i對應的活性邊表；      将y=i對應的活性邊表按照x遞增（或遞減）的順序排序。 3、依次掃描活性邊表，兩兩之間畫線。

執行個體

對于上圖來說，新邊表如下：  y=1

11

-2

4

-->

11

6

y=2

2

1.5

4

-->

2

7

y=3  NULL y=4  NULL y=5  NULL y=6

11

-3

8

y=7

2

3

8

y=8  NULL

活性邊表如下： y=1  加入新邊表的結點

11

-2

4

--〉

11

6

y=2  加入新邊表中的節點，y=1中的結點修改後加入（我這裡沒有排序，實際上應該排序的）

2

1.5

4

--〉

2

7

--〉

9

-2

4

--〉

11

6

y=3    y=2對應的活性邊表中的結點修改後加入

3.5

1.5

4

--〉

2

7

--〉

7

-2

4

--〉

11

6

y=4  

2

7

--〉

11

6

y=5

2

7

--〉

11

6

y=6

2

7

--〉

11

-3

8

y=7

2

3

8

--〉

8

-3

8

y=8   NULL

程式實作中涉及較多對連結清單的操作，包括建構、排序，會寫在以下文章中。 http://blog.csdn.net/flyfish5/article/details/49306429