邊界填充演算法

⑴ web填充怎麼設置

web填充設置：單擊上面工具欄中的「設計」按鈕。下一步點擊「頁面顏色」按鈕。單擊顏色下拉菜單中的填充效果按鈕。點擊填充效果屏幕上的「圖片」按鈕。點擊屏幕上的」選擇圖像」按鈕。

<Meta http-equiv="Page-Enter" Content="blendTrans(Duration=0.5)">，<Meta http-equiv="Page-Exit" Content="blendTrans(Duration=0.5)">。

blendTrans其實就是一種動態濾鏡效果，當然還有其他的方法也可以產生這種動態濾鏡效果，<Meta http-equiv="Page-Enter" Content="revealTrans(ration=x, transition=y)">。

邊標志填充演算法步驟：

1、用邊界色畫出多邊形輪廓線,也就是將多邊形邊界所經過的象素打上邊標志。

2、為了縮小范圍,加快填充速度,須找出多邊形的最小包圍盒：xmin、ymin、xmax、ymax。

3、逐條掃描線進行處理,初始時標志為假,對每條掃描線依從左往右的順序,逐個訪問該掃描線上的象素。每遇到邊界象素,標志取反。然後,按照標志是否為真決定象素是否為填充色。

⑵ 地理信息系統知識點

什麼是地理信息系統篇一：地理信息系統的基本概念

（一）數據與信息

數據是一種未經加工的原始資料，是通過數字化或記錄下來可以被鑒別的符號。數字、文字、符號、圖像都是數據。

信息（Information）是用文字、數字、符號、語言、圖像等介質來表示事件、事物、現象等的內容、數量或特徵，從而向人們（或系統）提供關於現實世界新的事實和知識，作為生產、建設、經營、管理、分析和決策的依據。信息具有客觀性、適用性、可傳輸性和共享性等特徵。信息來源於數據（Data）。

數據是客觀對象的表示，而信息則是數據內涵的意義，是數據的內容和解釋。例如，從實地或社會調查數據中可獲取到各種專門信息；從測量數據中可以抽取出地面目標或物體的形狀、大小和位置等信息；從遙感圖像數據中可以提取出各種地物的圖形大小和專題信息。

（二）地理信息

地理信息是指表徵地理圈或地理環境固有要素或物質的數量、質量、分布特徵、聯系和規律的數字、文字、圖象和圖形的總和。地理信息是有關地理實體的性質、特徵和運動狀態的表徵和一切有用的知識，它是對表達地理特徵與地理現象之間關系的地理數據的解釋。而地理數據則是各種地理特徵和現象間關系的符號化表示，包括空間位置、屬性特徵（簡稱屬性）及時域特徵三部分。空間位置數據描述地物所在位置。這種位置既可以根據大地參照系定義，如大地經緯度坐標，也可以定義為地物間的相對位置關系，如空間上的相鄰、包含等；屬性數據有時又稱非空間數據，是屬於一定地物、描述其特徵的定性或定量指標。時域特徵是指地理數據採集或地理現象發生的時刻/時段。時間數據對環境模擬分析非常重要，正受到地理信息系統學界越來越多的重視。空間位置、屬性及時間是地理空間分析的三大基本要素。

地理信息除了具有信息的一般特性，還具有以下獨特特性：

（1）空間分布性。地理信息具有空間定位的特點，先定位後定性，並在區域上表現出分布式特點，其屬性表現為多層次，因此地理資料庫的分布或更新也應是分布式。

（2）數據量大。地理信息既有空間特徵，又有屬性特徵，另外地理信息還隨著時間的變化而變化，具有時間特徵，因此其數據量很大。尤其是隨著全球對地觀測計劃不斷發展，我們每天都可以獲得上萬億兆的關於地球資源、環境特徵的數據。這必然對數據處理與分析帶來很大壓力。

（3）信息載體的多樣性。地理信息的第一載體是地理實體的物質和能量本身，除此之外，還有描述地理實體的文字、數字、地圖和影像等符號信息載體以及紙質、磁帶、光碟等物理介質載體。對於地圖來說，它不僅是信息的載體，也是信息的傳播媒介。

（三）地理信息系統

地理信息系統（GeographicInformationSystem或Geo－Informationsystem，GIS）有時又稱為「地學信息系統」或「資源與環境信息系統」。它是一種特定的十分重要的空間信息系統。它是在計算機硬、軟體系統支持下，對整個或部分地球表層（包括大氣層）空間中的有關地理分布數據進行採集、儲存、管理、運算、分析、顯示和描述的技術系統。地理信息系統處理、管理的對象是多種地理空間實體數據及其關系，包括空間定位數據、圖形數據、遙感圖像數據、屬性數據等，用於分析和處理在一定地理區域內分布的各種現象和過程，解決復雜的規劃、決策和管理問題。

通過上述的分析和定義可提出GIS的如下基本概念：

1、GIS的物理外殼是計算機化的技術系統，它又由若干個相互關聯的子系統構成，如數據採集子系統、數據管理子系統、數據處理和分析子系統、圖像處理子系統、數據產品輸出子系統等，這些子系統的優劣、結構直接影響著GIS的硬體平台、功能、效率、數據處

理的方式和產品輸出的類型。

2、GIS的操作對象是空間數據，即點、線、面、體這類有三維要素的地理實體。空間數據的最根本特點是每一個數據都按統一的地理坐標進行編碼，實現對其定位、定性和定量的描述、這是GIS區別於其它類型信息系統的根本標志，也是其技術難點之所在。

3、GIS的技術優勢在於它的數據綜合、模擬與分析評價能力，可以得到常規方法或普通信息系統難以得到的重要信息，實現地理空間過程演化的模擬和預測。

4、GIS與測繪學和地理學有著密切的關系。大地測量、工程測量、礦山測量、地籍測量、航空攝影測量和遙感技術為GIS中的空間實體提供各種不同比例尺和精度的定位數；電子速測儀、GPS全球定位技術、解析或數字攝影測量工作站、遙感圖像處理系統等現代測繪技術的使用，可直接、快速和自動地獲取空間目標的數字信息產品，為GIS提供豐富和更為實時的信息源，並促使GIS向更高層次發展。地理學是GIS的理論依託。有的學者斷言，「地理信息系統和信息地理學是地理科學第二次革命的主要工具和手段。如果說GIS的興起和發展是地理科學信息革命的一把鑰匙，那麼，信息地理學的興起和發展將是打開地理科學信息革命的一扇大門，必將為地理科學的發展和提高開辟一個嶄新的天地」。GIS被譽為地學的第三代語言——用數字形式來描述空間實體。

GIS按研究的范圍大小可分為全球性的、區域性的和局部性的；按研究內容的不同可分為綜合性的與專題性的。同級的各種專業應用系統集中起來，可以構成相應地域同級的區域綜合系統。在規劃、建立應用系統時應統一規劃這兩種系統的發展，以減小重復很費，提高數據共享程度和實用性。

什麼是地理信息系統篇二：地理信息系統名詞解釋大全(整理版本)

地理信息系統作為信息技術的一種，是在計算機硬、軟體的支持下，以地理空間資料庫（GeospatialDatabase）為基礎，以具有空間內涵的地理數據為處理對象，運用系統工程和信息科學的理論，採集、存儲、顯示、處理、分析、輸出地理信息的計算機系統，為規劃、管理和決策提供信息來源和技術支持。簡單地說，GIS就是研究如何利用計算機技術來管理和應用地球表面的空間信息，它是由計算機硬體、軟體、地理數據和人員組成的有機體，採用地理模型分析方法，適時提供多種空間的和動態的地理信息，為地理研究和地理決策服務的計算機技術系統。地理信息系統屬於空間型信息系統。

地理信息是指表徵地理圈或地理環境固有要素或物質的數量、質量、分布特徵、聯系和規律等的數字、文字、圖像和圖形等的總稱；它屬於空間信息，具有空間定位特徵、多維結構特徵和動態變化特徵。

地理信息科學與地理信息系統相比，它更加側重於將地理信息視作為一門科學，而不僅僅是一個技術實現，主要研究在應用計算機技術對地理信息進行處理、存儲、提取以及管理和分析過程中提出的一系列基本問題。地理信息科學在對於地理信息技術研究的同時，還指出了支撐地理信息技術發展的基礎理論研究的重要性。

地理數據是以地球表面空間位置為參照，描述自然、社會和人文景觀的數據，主要包括數字、文字、圖形、圖像和表格等。

地理信息流即地理信息從現實世界到概念世界，再到數字世界（GIS），最後到應用領域。

數據是通過數字化或記錄下來可以被鑒別的符號，是客觀對象的表示，是信息的表達，只有當數據對實體行為產生影響時才成為信息。

信息系統是具有數據採集、管理、分析和表達數據能力的系統，它能夠為單一的或有組織的決策過程提供有用的信息。包括計算機硬體、軟體、數據和用戶四大要素。

四叉樹數據結構是將空間區域按照四個象限進行遞歸分割（2n×2n，且n≥1），直到子象限的數值單調為止。凡數值（特徵碼或類型值）呈單調的單元，不論單元大小，均作為最後的存儲單元。這樣，對同一種空間要素，其區域網格的大小，隨該要素分布特徵而不同。

不規則三角網模型簡稱TIN，它根據區域有限個點集將區域劃分為相連的三角面網路，區域中任意點落在三角面的頂點、邊上或三角形內。如果點不在頂點上，該點的高程值通常通過線性插值的方法得到（在邊上用邊的兩個頂點的高程，在三角形內則用三個頂點的高程）。

拓撲關系拓撲關系是指網結構元素結點、弧段、面域之間的空間關系，主要表現為拓撲鄰接、拓撲關聯、拓撲包含。根據拓撲關系，不需要利用坐標或距離，可以確定一種地理實體相對於另一種地理實體的位置關系，拓撲數據也有利於空間要素的查詢。

拓撲結構為在點、線和多邊形之間建立關聯，以及徹底解決鄰域和島狀信息處理問題而必須建立的數據結構。這種結構應包括以下內容：唯一標識，多邊形標識，外包多邊形指針，鄰接多邊形指針，邊界鏈接，范圍（最大和最小x、y坐標值）。

遊程編碼是逐行將相鄰同值的網格合並，並記錄合並後網格的值及合並網格的長度，其目的是壓縮柵格數據量，消除數據間的冗餘。

空間數據結構是指適合於計算機系統存儲、管理和處理的地學圖形的邏輯結構，是地理實體的空間排列方式和相互關系的抽象描述。

矢量數據結構是利用歐幾里得幾何學中的點、線、面及其組合體來表示地理實體空間分布的一種數據組織方式。這種數據組織方式能最好地逼近地理實體的空間分布特徵，數據精度高，數據存儲的冗餘度低，便於進行地理實體的網路分析，但對於多層空間數據的疊合分析比較困難。

柵格數據結構基於柵格模型的數據結構簡稱為柵格數據結構，指將空間分割成有規則的網格，在各個網格上給出相應的屬性值來表示地理實體的一種數據組織形式。

空間索引是指依據空間對象的位置和形狀或空間對象之間的某種空間關系按一定的順序排列的一種數據結構，其中包含空間對象的概要信息。作為一種輔助性的空間數據結構，空間索引介於空間操作演算法和空間對象之間，它通過篩選作用，大量與特定空間操作無關的空間對象被排除，從而提高空間操作的速度和效率。

空間數據編碼是指將數據分類的結果，用一種易於被計算機和人識別的符號系統表示出來的過程。編碼的目的是用來提供空間數據的地理分類和特徵描述，同時為了便於地理要素的輸入、存儲、管理，以及系統之間數據交換和共享的需要。

Delaunay三角網即由狄洛尼三角形組成的三角網，它是在地形擬合方面表現最出色的三角網，因此常被用於TIN的生成。狄洛尼三角形有三個最鄰近的點連接而成，這三個相鄰點對應的Voronoi多邊形有一個公共的頂點，此頂點同時也是狄洛尼三角形外接圓的圓心。

Voronoi多邊形即泰森多邊形，它採用了一種極端的邊界內插方法，只用最近的單個點進行區域插值。泰森多邊形按數據點位置將區域分割成子區域，每個子區域包含一個數據點，各子區域到其內數據點的距離小於任何到其它數據點的距離，並用其內數據點進行賦值。

柵格數據壓縮編碼有鍵碼、遊程長度編碼、塊碼和四叉樹編碼等。其目的，就是用盡可能少的數據量記錄盡可能多的信息，其類型又有信息無損編碼和信息有損編碼之分。

邊界代數演算法邊界代數多邊形填充演算法是一種基於積分思想的矢量格式向柵格格式轉換演算法，它適合於記錄拓撲關系的多邊形矢量數據轉換為柵格結構。它不是逐點判斷與邊界的關系完成轉換，而是根據邊界的拓撲信息，通過簡單的加減代數運算將邊界位置信息動態地賦給各柵格點，實現了矢量格式到柵格格式的高速轉換，而不需要考慮邊界與搜索軌跡之間的關系，因此演算法簡單、可靠性好，各邊界弧段只被搜索一次，避免了重復計算。

DIME文件美國人口普查局在1980年的人口普查中提出了雙重獨立地圖編碼文件。它含有調查獲得的地理統計數據代碼及大城市地區的界線的坐標值，提供了關於城市街道，住址范圍以及與人口普查局的列表統計數據相關的地理統計代碼的綱要圖。在1990年的人口普查中，TIGER取代了DIME文件。

空間數據內插即通過已知點或分區的數據，推求任意點或分區數據的方法。空間數據壓縮即從所取得的數據集合S中抽出一個子集A，這個自己作為一個新的信息源，在規定的精度范圍內最好地逼近原集合，而又取得盡可能大的壓縮比。

坐標變換實質是建立兩個平面點之間的一一對應關系，包括幾何糾正和投影轉換，他們是空間數據處理的基本內容之一。

仿射變換是GIS數據處理中使用最多的一種幾何糾正方法。它的主要特性為：同時考慮到因地突變形而引起的實際比例尺在x和y方向上的變形，因此糾正後的坐標數據在不同方向上的長度比將發生變化。

數據精度是考察數據質量的一個方面，即對現象描述的詳細程度。精度低的數據並不一定準確度也低。

空間數據引擎是一種空間資料庫管理系統的實現方法，即在常規資料庫管理系統之上添加一層空間資料庫引擎，以獲得常規資料庫管理系統功能之外的空間數據存儲和管理的能力。代表性的是ESRI的SDE。

空間數據引擎在用戶和異種空間資料庫的數據之間提供了一個開放的介面，它是一種處於應用程序和資料庫管理系統之間的中間件技術。使用不同廠商GIS的客戶可以通過空間數據引擎將自身的數據提交給大型關系型DBMS，由DBMS統一管理；同樣，客戶也可以通過空間數據引擎從關系型DBMS中獲取其他類型GIS的數據，並轉化成客戶可以使用的方式。

資料庫管理系統是操作和管理資料庫的軟體系統，提供可被多個應用程序和用戶調用的軟體系統，支持可被多個應用程序和用戶調用的資料庫的建立、更新、查詢和維護功能。

空間資料庫是地理信息系統在計算機物理存儲介質上存儲的`與應用相關的地理空間數據的總和，一般是以一系列特定結構的文件的形式組織在存儲介質之上的。

空間數據模型是關於現實世界中空間實體及其相互間聯系的概念，為描述空間數據組織和設計空間資料庫模式提供了基本的方法。一般而言，GIS空間數據模型由概念數據模型、邏輯數據模型和物理數據模型三個有機聯系的層次所組成。

分布式資料庫是一組數據的集合，這些數據在物理上分布於計算機網路的不同結點上，而邏輯上屬於同一個系統。它具有分布性，同時在邏輯上互相關聯。

對象－關系管理模式/型是指在關系型資料庫中擴展，通過定義一系列操作空間對象（如點、線、面）的API函數，來直接存儲和管理非結構化的空間數據的空間資料庫管理模式。

緩沖區分析是根據分析對象的點、線、面實體，自動建立他們周圍一定距離的帶狀區，用以識別這些實體或主體對鄰近對象的輻射范圍或影響度，以便為某項分析或決策提供依據。

疊合分析是指在統一空間參照系統條件下，每次將同一地區兩個地理對象的圖層進行疊合，以產生空間區域的多重屬性特徵，或建立地理對象之間的空間對應關系。

空間分析是基於空間數據的分析技術，它以地學原理為依託，通過分析演算法，從空間數據中獲取有關地理對象的空間位置、空間分布、空間形態、空間形成、空間演變等信息。

網路分析是運籌學模型中的一個基本模型，即對地理網路和城市基礎設施網路進行地理分析和模型化。它的根本目的是研究、籌劃一項網路工程如何安排，並使其運行效果最好。

透視圖從數字高程模型繪制透視立體圖是DEM的一個極其重要的應用。透視立體圖能更好地反映地形的立體形態，非常直觀。與採用等高線表示地形形態

相比有其自身獨特的優點，更接近人們的直觀視覺。調整視點、視角等各個參數值，就可從不同方位、不同距離繪制形態各不相同的透視圖製作動畫。

網路是一個由點、線的二元關系構成的系統，通常用來描述某種資源或物質在空間上的運動。

變數篩選分析是通過尋找一組相互獨立的變數，使相互關聯的復雜的多變數數據得到簡化的空間統計分析方法。常用的有主成分分析法、主因子分析法、關鍵變數分析法等。

變數聚類分析是將一組數據點或變數，按照其在性質上親疏遠近的程度進行分類的空間統計分析方法。兩個數據點在m為空間的相似性可以用這些點在變數空間的距離來度量。

數字地面模型簡稱DTM，是定義於二維區域上的一個有限項的向量序列，它以離散分布的平面點來模擬連續分布的地形。

數字高程模型當數字地面模型的地面屬性為海拔高程時，則該模型即為數字高程模型。簡稱DEM。

GIS應用模型是根據具體的應用目標和問題，藉助於GIS自身的技術優勢，使觀念世界中形成的概念模型，具體化為信息世界中可操作的機理和過程。

OGC即OpenGIS協會(OpenGISConsortium)其目的是使用戶可以開放地操縱異質的地理數據，促進採用新的技術和商業方式來提高地理信息處理的互操作性(Interoperablity)，OGC會員主要包括GIS相關的計算機硬體和軟體製造商，數據生產商以及一些高等院校，政府部門等，其技術委員會負責具體標準的制定工作。

開放式地理信息系統（OpenGIS）OpenGIS(,OGIS-開放的地理數據互操作規范)由美國OGC（開放地理信息系統協會）提出。其目標是，制定一個規范，使得應用系統開發者可以在單一的環境和單一的工作流中，使用分布於網上的任何地理數據和地理處理。它致力於消除地理信息應用之間以及地理應用與其它信息技術應用之間的藩籬，建立一個無「邊界」的、分布的、基於構件的地理數據互操作環境，與傳統的地理信息處理技術相比，基於該規范的GIS軟體將具有很好的可擴展性、可升級性、可移植性、開放性、互操作性和易用性。

數據結構是地理實體的數據組織形式及其相互關系的抽象描述。

空間數據質量是對空間數據在表達空間位置、空間關系、專題特徵以及時間等要素時，所能達到的准確性、一致性、完整性以及它們之間統一性的度量，一般描述為空間數據的可靠性和精度，用誤差來表示。

數字地球是把浩瀚復雜的地球數據加以數字化、網路化，變成一個地球信息模型計劃。是一種可以嵌入海量地理數據、多種解析度、三維的地球表達，是對真實地球及其相關現象的統一性的數字化重現和認識。其核心思想有兩點：一是用數字化手段統一處理地球問題；二是最大限度地利用信息資源。

虛擬現實也稱虛擬環境或人工現實，是一種由計算機生成的高級人機交互系統，即構成一個以視覺感受為主，也包括聽覺、觸覺、嗅覺的可感知環境，演練者通過專門的設備可在這個環境中實現觀察、觸摸、操作、檢測等試驗，有身臨其境之感。

地圖投影是建立平面上的點（用平面直角坐標或極坐標表示）和地球表面上的點（用緯度和精度表示）之間的函數關系。

投影轉換是從一種地圖投影變換為另一種地圖投影。其實質是建立兩平面場之間及鄰域雙向連續點的一一對應的關系。

虛擬地理環境簡稱VGE，是基於地學分析模型、地學工程等的虛擬現實，它是地學工作者根據觀測實驗、理論假設等建立起來的表達和描述地理系統的空間分布以及過程現象的虛擬信息地理世界，一個關於地理系統的虛擬實驗室，它允許地學工作者按照個人的知識、假設和意願去設計修改地學空間關系模型、地學分析模型、地學工程模型等，並直接觀測交互後的結果，通過多次的循環反饋，最後獲取地學規律。

高斯-克呂格投影Gauss-KruegerProjection①是一種橫軸等角切橢圓柱投影。它是將一橢圓柱橫切於地球橢球體上，該橢圓柱面與橢球體表面的切線為一經線，投影中將其稱為中央經線，然後根據一定的約束條件即投影條件，將中央經線兩側規定范圍內的點投影到橢圓柱面上從而得到點的高斯投影。

②一種等角橫切橢圓柱投影。其投影帶中央子午線投影成直線且長度不變，赤道投影也為直線，並與中央子午線正交。

UTM投影全球橫軸墨卡托投影的簡稱。是美國編制世界各地軍用地圖和地球資源衛星象片所採用的橫軸墨卡托投影的一種變型投影。它規定中央經線長度比為0.9996。

電子地圖當紙地圖經過計算機圖形圖像系統光——電轉換量化為點陣數字圖像，經圖像處理和曲線矢量化，或者直接進行手扶跟蹤數字化後，生成可以為地理信息系統顯示、修改、標注、漫遊、計算、管理和列印的矢量地圖數據文件，這種與紙地圖相對應的計算機數據文件稱為矢量化電子地圖。

元數據[空間]是指描述空間數據的數據，它描述空間數據集的內容、質量、表示方式、空間參考、管理方式以及數據集的其他特徵，是空間數據交換的基礎，也是空間數據標准化與規范化的保證，在一定程度上為空間數據的質量提供了保障。

Web地理信息系統（WebGIS）是Web技術和GIS技術相結合，即利用Web技術來擴展和完善地理信息系統的一項新技術。從WWW的任一個節點，Internet用戶可以瀏覽WebGIS站點中的空間數據、製作專題圖、進行各種空間檢索和空間分析。

GIS互操作互操作是指在異構環境下的兩個或多個實體，盡管它們實現的語言、執行的環境和基於的模型不同，但仍然可以相互通信和協作，以完成某一特定任務。這些實體包括應用程序、對象、系統運行環境等。空間數據的互操作針對異構的資料庫和平台，實現數據處理的互操作，與數據轉換相比，它是「動態」的數據共享，獨立於平台，具有高度的抽象性，是空間數據共享的發展方向。

組件式GIS是採用了面向對象技術和組件式軟體的GIS系統（包括基礎平台和應用系統）。其基本思想是把GIS的各大功能模塊劃分為幾個組件，每個組件完成不同的功能。各個GIS組件之間，以及GIS組件與其它非GIS組件之間，都可以方便地通過可視化的軟體開發工具集成起來，形成最終的GIS基礎平台以及應用系統。

客戶機/伺服器結構即C/S結構，是一種分布式系統結構，在該體系中，客戶端通常是同最終用戶交互的應用軟體系統，而伺服器由一組協作的過程構成，為客戶端提供服務。客戶機和伺服器通常運行相同的微內核，一個客戶機/伺服器機制可以有多個客戶端，或者多個伺服器，或者兼而有之。客戶機/伺服器模式基於簡單的請求/應答協議，即客戶端向伺服器提出信息處理的請求，伺服器端接收到請求並將請求解譯後，根據請求的內容執行相應操作，並將操作結果傳

⑶ 區域填充的主要思想和方法

掃描線種子填充演算法思想
首先填充種子所在的尚未填充的一區段,然後確定與這一區段相鄰的上下兩條掃描線上位於該區段內是否存在需要填充的新區段,如果存在,則依次把每個新區段最右端的象素作為種子放入堆棧。反復這個過程,直到堆棧為空。
掃描線種子填充演算法步驟 1、初始化堆棧。 2、種子壓入堆棧。 3、While（堆棧非空）從堆棧彈出種子象素。
(1)如果種子象素尚未填充,則： ① 求出種子區段：xleft、xright。
② 填充整個區段。 (2)檢查相鄰的上掃描線的xleft≤x≤xright區間內,是否存在需要填充的新區段,如果存在,則把每個新區段在xleft≤x≤xright范圍內的最右邊的象素,作為新的種子象素依次壓入堆棧。 (3)檢查相鄰的下掃描線的xleft≤x≤xright區間內,是否存在需要填充的新區段,如果存在,則把每個新區段在xleft≤x≤xright范圍內的最右邊的象素,作為新的種子象素依次壓入堆棧。 }
有關堆棧操作的輔助代碼
1、定義棧結構： # define MAX 100 /*定義最大棧空間*/
struct stack
{
int top; /*指向棧頂的計數器*/
int xy[MAX][2]; /*種子點（二維）*/
}s; 2、初始化堆棧 s.top=－1; 3、進棧操作 pushxy(int x,int y)
{
if(s.top= =MAX－1)
{
printf(「Overflow!」);
exit(1);
}
else
{
s.top=s.top+1;
s.xy[s.top][0]=x;
s.xy[s.top][1]=y;
}
} 4、出棧操作 popxy(int *x,int *y)
{
if(s.top<0)
{
printf(「underflow!」);
exit(1);
}
else
{
*x=s.xy[s.top][0];
*y=s.xy[s.top][1];
s.top=s.top－1;
}
} 5、堆棧非空 s.top!=－1 或者 s.top>=0 掃描線種子填充演算法偽代碼 scanline_seed_fill(int x,int y,int boundarycolor,int newcolor)
{
int savex,xleft,xright,pflag,xenter;
//初始化堆棧；
pushxy(x,y); /*種子壓入堆棧*/
while(堆棧非空)
{
popxy(&x,&y); /*棧頂象素出棧*/
savex=x; /*保存種子坐標x分量的值*/
while(getpixel(x,y)!=boundarycolor) /*獲取該點的顏色值*/
{
putpixel(x,y, newcolor ); /*填充種子右側的象素*/
x++;
}
xright=x－1; /*得到種子區段的右端點*/
x=savex－1; /*准備向種子左側填充*/
while(getpixel(x,y)!=boundarycolor) /*獲取該點的顏色值*/
{
putpixel(x,y, newcolor ); /*填充種子左側的象素*/
x--;
}
xleft=x+1; /*得到種子區段的左端點*/
x=xleft;
y=y+1; /*考慮種子相鄰的上掃描線*/
while(x<=xright)
{
pflag=0; /*找到新種子的標志：0為假；1為真*/
while(getpixel(x,y)!=boundarycolor && getpixel(x,y)!=newcolor&& x<xright)
{
if(pflag= =0)
pflag=1;
x++;
}
if(pflag= =1)
{
if((x= =xright)&&(getpixel(x,y)!=boundarycolor)&&(getpixel(x,y)!=newcolor))
pushxy(x,y); /*新區間超過xright,將代表該區段的象素進棧*/
else
pushxy(x－1,y); /*新區段右端點作為種子進棧*/
pflag=0;
}
xenter=x;
while((getpixel(x,y)==boundarycolor||getpixel(x,y)==newcolor)&&x<xright)
{
x++;/*向右跳過分隔帶*/
}
if(xenter==x) x++;/*處理特殊情況,以退出while(x<=xright)循環*/
}
x=xleft; /*為下掃描線的處理作準備*/
y=y－2;
/*檢查相鄰的下掃描線,找新區段,並將每個新區段右端的象素作為種子
入棧,其方法與上掃描線的處理一樣,這里省略。要求同學補充完整。*/
}
} 邊相關多邊形掃描線填充思想
邊相關掃描線填充演算法的實現需要建立兩個表：邊表（ET）和活動邊表（AET）。
ET用來對除水平邊外的所有邊進行登記,即建立邊的記錄。
AET則是在ET建立的基礎上進行掃描轉換。對不同的掃描線,與之相交的邊線也是不同的,當對某一條掃描線進行掃描轉換時,我們只需要考慮與它相交的那些邊線,為此AET建立了只與當前掃描線相交的邊記錄鏈表,以提供對當前掃描線上的區段進行填充。
邊相關多邊形掃描線填充演算法步驟
1、根據給出的頂點坐標建ET表；並求出頂點坐標中最大y值ymax和最小y值ymin。
2、定義AET指針,並使它為空。
3、使用掃描線的yj值作為循環變數,使其初值為ymin。
4、對於循環變數yj的每一整數值,重復作以下事情,直到yj大於ymax,或ET與AET表都為空為止：
① 如果ET中yj桶非空,則將yj桶中的全部記錄合並到AET中。
② 對AET鏈中的記錄按x的大小從小到大排序。
③ 依次取出AET各記錄中的xi坐標值,兩兩配對,對每對xi之間的象素填上所要求的顏色。
④ 如果AET中某記錄的ymax=yj,則刪除該記錄。
⑤ 對於仍留在AET中的每個記錄,用xi+1/m代替xi,這就是該記錄邊線與下一條掃描線yj+1的交點。
⑥ 使yj加1,以便進入下一輪循環。
邊相關多邊形掃描線填充為偽代碼 #include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#define round(x) ((x>0)?(int)(x+0.5):(int)(x-0.5)) /*求舍入的宏*/
struct edge{ /*邊記錄結構*/
int ymax;
float xi;
float m;
struct edge *next;
};
void poly_fill(int,int *,int);
void main()
{
int polypoints[]={ /*多邊形頂點坐標: x0,y0,x1,y1,... */
100,300, 200,200, 300,200, 300,350,
400,250, 450,300, 300,50, 100,150};
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,);
poly_fill(8,polypoints,4); /*用紅色填充*/
getch();
closegraph();
}
/*將一條邊記錄插入邊記錄構成的鏈表的表頭*/
void insert_et(struct edge *anedge,struct edge **p_edges)
{
struct edge *p;
p=*p_edges;
*p_edges=anedge;
anedge->next=p;
}
/*復制一條邊記錄插入有效邊表,維持有效邊表的有序性*/
short insert_aet(struct edge *p,struct edge **p_aet)
{
struct edge *q,*k,*l;
if(!(q=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN INSERTING EDGE RECORD TO AET );
return(0);
}
q->ymax=p->ymax; q->xi=p->xi;
q->m=p->m; q->next=NULL;
if(!(*p_aet)||((*p_aet)->xi>q->xi)||(((*p_aet)->xi==q->xi)&&((*p_aet)->m>q->m)))
{
l=*p_aet; *p_aet=q; q->next=l;
}
else
{
l=*p_aet;
k=l->next;
while(k&&(k->xi<q->xi))
{
l=k;
k=k->next;
}
if(k&&(k->xi==q->xi)&&(k->m<q->m))
{
l=k;
k=k->next;
}
l->next=q;
q->next=k;
}
return(1);
}
/*從（x1,y）到（x2,y）用color色繪水平直線*/
void draw_line(int x1,int x2,int y,int color)
{
int i;
y=getmaxy()-y; /*進行坐標變換*/
for(i=x1;i<=x2;i++)putpixel(i,y,color);
}
/*多邊形掃描線填充:
numpoint是多邊形頂點個數；
points存放多邊形頂點坐標（x0,y0,x1,y1,...);
color是填充色*/
void poly_fill(int numpoint,int *points,int color)
{
struct edge **et=NULL,*aet,*anedge,*p,*q;
int i,j,maxy,miny,x1,y1,x2,y2,yi,znum;
maxy=miny=points[1];
znum=2*numpoint;
for(i=3;i<znum;i++)
{
if(maxy<points[i]) maxy=points[i];
else if(miny>points[i])miny=points[i];
i++;
}
if(!(et=(struct edge **)malloc((maxy-miny+1)*sizeof(struct edge *))))
{ /*建立邊表ET */
printf( OUT MEMORY IN CONSTRUCTING ET );
return;
}
for(i=0;i<maxy-miny+1;i++) et[i]=NULL;
x1=points[znum-2]; y1=points[znum-1];
for(i=0;i<znum;i+=2)
{ /*處理多邊形所有邊,為每條非水平邊建立一個邊記錄,並將其插到ET表中的合適位置 */
x2=points[i]; y2=points[i+1];
if(y1!=y2) /*只考慮非水平邊*/
{
if(!(anedge=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN CONSTRUCTING EDGE RECORD. );
goto quit;
}
anedge->m=(float)(x2-x1)/(y2-y1);
anedge->next=NULL;
if(y2>y1) /*處理奇異點*/
{
j=i+1;
do{ /*向後劃過所有水平邊*/
if((j+=2)>=znum)j-=znum;
}while(points[j]==y2);
if(points[j]>y2) anedge->ymax=y2-1;
/*若(x2,y2)不是局部極值點,邊記錄的ymax域為y2-1,這樣處理
掃描線y=y2時此邊記錄將不在AET中,從而不會產生交點 */
else anedge->ymax=y2; /*若(x2,y2)是局部極值點,邊記錄的ymax域為y2,
這樣處理掃描線y=y2時此邊記錄將在AET中,從而會產生一個交點 */
anedge->xi=x1;
insert_et(anedge,&et[y1-miny]);
}
else
{
j=i+1; /*向前劃過所有水平邊*/
do{
if((j-=2)<0)j+=znum;
}while(points[j]==y1);
if(points[j]>y1) anedge->ymax=y1-1;
/*若(x1,y1)不是局部極值點,邊記錄的ymax域為y1-1,這樣處理
掃描線y=y1時此邊記錄將不在AET中,從而不會產生交點 */
else anedge->ymax=y1; /*若(x1,y1)是局部極值點,邊記錄的ymax
域為y1,這樣處理掃描線y=y1時此邊記
錄將在AET中,從而會產生一個交點 */
anedge->xi=x2;
insert_et(anedge,&et[y2-miny]);
}
}
x1=x2;
y1=y2;
}
aet=NULL; /*初始化有效邊表AET*/
for(yi=miny;yi<=maxy;yi++) /*從低到高逐條處理掃描線*/
{ /*將ET表中與yi對應的邊記錄鏈表中的全部邊記錄
p=et[yi-miny]; 都按序並入AET中*/
while(p)
{
if(!insert_aet(p,&aet)) goto quit;
p=p->next;
}
p=aet;
while(p) /*依次取出AET各記錄中的xi坐標值,兩兩配對,*/
{/*對每對xi之間的象素填上所要求的顏色*/
draw_line(round(p->xi),round(p->next->xi),yi,color);
p=p->next->next;
}
p=aet;
while(p&&(p->ymax==yi)) /*對AET中的每個記錄,若它的ymax==yi, */
{/*則刪除該記錄,否則用xi+1/m代替xi,這就是該記錄所對應的*/
aet=p->next; /*邊線與下一條掃描線y=yi+1的交點 */
free(p);
p=aet;
}
while(p)
{
if(p->ymax==yi)
{
q->next=p->next;
free(p);
p=q->next;
}
else
{
p->xi+=p->m;
q=p;
p=p->next;
}
}
}
quit:
if(et) /*釋放動態申請的內存*/
{
for(yi=miny;yi<=maxy;yi++)
{
q=p=et[yi-miny];
while(p)
{
q=p->next;
free(p);
p=q;
}
}
free(et);
}
} 邊標志填充演算法思想
掃描線具有連貫性,這種連貫性只有在掃描線與多邊形相交處才會發生變化,而每次的變化結果：無非是在前景色和背景色之間相互「切換」。
邊標志填充演算法正是基於這一發現,先在屏幕上生成多邊形輪廓線,然後逐條掃描線處理。處理中：逐點讀取象素值,若為邊界色,則對該象素值進行顏色切換。
邊標志填充演算法步驟 1、用邊界色畫出多邊形輪廓線,也就是將多邊形邊界所經過的象素打上邊標志。
2、為了縮小范圍,加快填充速度,須找出多邊形的最小包圍盒：xmin、ymin、xmax、ymax。
3、逐條掃描線進行處理,初始時標志為假,對每條掃描線依從左往右的順序,逐個訪問該掃描線上的象素。每遇到邊界象素,標志取反。然後,按照標志是否為真決定象素是否為填充色。
邊標志填充演算法偽代碼 EdgeMarkFill(int p[][2],int n,int boundarycolor,int newcolor)
{
int i,x,y,flag,xmin,xmax,ymin,ymax;
setcolor(boundarycolor); /*設置畫筆色*/
for(i=0 ;i<n;i++)/*畫出多邊形的n條邊*/
line(p[i][0], p[i][1], p[(i+1)%n][0], p[(i+1)%n][1]);
/*用求極值的演算法,從多邊形頂點數組p中,求出xmin,xmax,ymin,ymax*/
for(y=ymin;y<=ymax;y++)
{
flag=－1;
for(x=xmin;x<=xmax;x++)
{
if(getpixel(x,y)= = boundarycolor) flag=－flag;
if(flag= =1)putpixel(x,y, newcolor);
}
}
}