掃描多邊形填充算法

 掃描多邊形填充算法

在做手機地圖的過程中,由于J2ME沒提供多邊形填充的API,隻能自己實作了,以下是實作的思路,請批評指正!

多邊形填充，就是把多邊形所占據的栅格象素賦予指定的顔色值。要完成這個任務，一個首要的問題就是求出多邊形所占據的栅格象素，判斷一個網格在多邊形内還是多邊形外，在多邊形内的象素，則賦予指定的顔色值，多邊形外的象素，則不賦予指定的顔色值，具體該如何判斷象素是否在多邊形内呢？這裡我們采用”掃描線多邊形填充算法”。

掃描多邊形填充算法的基本原理——在直角坐标系中，假設有一條從左至右的掃描線穿過多邊形，從左至右開始計數，與多邊形交點為奇數時，開始進入多邊形，與多邊形交點為偶數時，走出多邊形。這樣在這相鄰配對的奇偶交點間的所有象素都在多邊形内。如圖，奇數交點a，c，都是進入多邊形，偶數交點b，d都是走出多邊形，相鄰的奇偶交點配對，a，b之間，c，d之間的象素都在多邊形内，可見一條掃描線上，與多邊形交點個數需要為偶數。依據這樣的思路，掃描線從上到下，從左到右依次掃過多邊形即可求得多邊形所占據的象素。（注意退化情況的處理，也就是掃描線剛好經過頂點或者多邊形的邊本身就是水準的情況）

具體實作——首先，求多邊形最上，最下的行号，以便于确定掃描線的行數，這個可以根據多邊形的MBR求得；其次，确定一條掃描線上，與多邊形的交點，保證交點個數為偶數，并對這些交點按列号從小到大排列；最後，掃描轉換，掃描線從上到下，每條掃描線從左到右，對這些排序好的奇偶點配對連線。所采用的資料結構類似于“鋸齒狀的二維數組”，第一維代表行号，第二維代表一行中的交點。為了實作以上的步驟，需要對多邊形邊界進行栅格化，确定邊界所經過的栅格，并把這些存儲為“鋸齒狀的二維數組”（栅格化方法有：數值微分法，Bresenham算法，栅格中心線求交法）。退化情況的處理：

一、邊線端點的處理。比較此端點與它相鄰的前後兩端點所在掃描線的行号，設此端點的行号為h0,前一端點的行号為h1，後一端點的行号為h2。

1)        h0>h1 and h0>h2，如圖，點A、C、F，這些端點的栅格點不予以記錄，即掃描線經過該點，計交點為0。

2)        h0<h1 and h0<h2，如圖，點B、E、G，這些端點的栅格點記錄兩次，即掃描線經過該點，計交點為2。

3)        h0<h1 and h0>h2 or h0>h1 and h0<h2，如圖，點D，H，這些端點的栅格點記錄一次，即掃描線經過該點，計交點為1。

二、水準線的處理。多邊形邊線段，掃描出來為一橫線，即一條線段從頭到尾都占據一行栅格。理論上，這種情況與掃描線有無數個交點，為了保持一行中交點個數為偶數，判斷目前橫線段與前後相鄰兩條線段的位置關系，同時先栅格化此橫線，作以下規定。

1)        前後相鄰兩線段位于此橫線段的異側，如圖，橫線段AB，前後兩線段AI，BC位于橫線段AB的異側，則與此橫線段交點計為1，記錄A點或者B點，均可。

2)        前後相鄰兩線段位于此橫線段的同側，如圖，橫線段GF，前後兩線段GH，FE位于橫線段GF的同側，則與此橫線段交點計為0，不記錄任何交點。

這種判斷的思想是這樣的：基于動态的思想，橫線AB，假設A和B兩點互相靠近，最終成為一點，假設為A‘，根據端點處理的方法，A’介于前後兩點I、C之間，應計交點一個，而對于橫線GF，一樣的道理，GF互相靠近最終成為一點，假設為F‘，根據端點處理的方法，F’大于前後兩點E、H，應計交點0。這種判斷可以有效處理橫線，但又帶來一個新的問題，如果相鄰前或者後兩線段也是同此橫線一樣，也是在這一行水準，這樣就要遞推到更前或者更後的線段，直到找出以上判斷的條件。

如圖，判斷線段AB，需要找到前一條線段AJ，後一條線段BC，由于BC與AB都是水準的，需要找再下一條CD，得到AJ、CD位于水準線的異側，則計交點為1。判斷線段GH，前後兩線段GF、HI都是水準的，需要分别尋找更前，、更後的線段FE、IJ，一直遞歸下去，直到确定判斷條件。如果覺得這種情況比較麻煩，在程式端點循環的時候，找到第一段不是橫線的起點開始循環，這樣，隻要判斷，橫線後面條線段的情況，直到确定判斷條件即可。

     三、島嶼情況。以上退化情況的處理同樣适合島嶼情況的處理，依然要對栅格按列從左往右排序，奇偶配對畫線即可。