J2ME 上任意多邊形填充算法.doc

精品論文推薦j2me 上任意多邊形填充算法劉勝云 1，楊俊 1，董洪毅 21 北京郵電大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系，北京 (100876)2 山東省科學(xué)院激光研究所，濟(jì)南 (272017)e-mail: 摘要：本論文主要對(duì) j2me 平臺(tái)進(jìn)行介紹，簡(jiǎn)要的介紹了 j2me 的體系結(jié)構(gòu)，提出了此多邊形填充算法的應(yīng)用環(huán)境，在此基礎(chǔ)上詳細(xì)的介紹此填充算法，從理論和實(shí)現(xiàn) 2 層上分析此 算法的優(yōu)缺點(diǎn)，并在算法的缺點(diǎn)之上提出一個(gè)修正的方案，最終實(shí)現(xiàn)一個(gè)基于 j2me 規(guī)范的任意多邊形填充之掃描線填充算法，來(lái)實(shí)現(xiàn)對(duì) j2me 上圖形圖像的渲染，并加入對(duì)曲線多邊 形填充的一些補(bǔ)充說(shuō)明,并就此算法在基于 j2me 平臺(tái)的手機(jī)上運(yùn)行，給出其運(yùn)行結(jié)果和結(jié)果分析，并證明了此算法在 j2me 平臺(tái)上的可行性。 關(guān)鍵字：j2me；像素；掃描線中圖分類號(hào)：tp311.11. 引言j2me 作為嵌入式系統(tǒng)應(yīng)用平臺(tái)得到了迅速的發(fā)展，java 語(yǔ)言固有的平臺(tái)無(wú)關(guān)性使得基 于 j2me 平臺(tái)的嵌入式應(yīng)用系統(tǒng)具有廣闊的前景1。隨著手機(jī)為主的移動(dòng)手持設(shè)備的增加， 手持設(shè)備上的應(yīng)用開(kāi)發(fā)需求穩(wěn)步上升。j2me 作為手持設(shè)備的主流開(kāi)發(fā)平臺(tái)之一，是實(shí)現(xiàn)手 持設(shè)備各種綜合應(yīng)用的一個(gè)重要途徑。手持設(shè)備上圖形圖像的處理是各種應(yīng)用中最基本應(yīng)用 之一，所以對(duì) j2me 上多邊形填充算法的研究日益重要。本文就 j2me 上任意多邊形填充算 法之掃描線填充做簡(jiǎn)單分析和介紹。2. j2me 介紹j2me（java 2 platform micro edition）是為無(wú)線電子市場(chǎng)所設(shè)計(jì)的 java 平臺(tái)，包括 jvm 規(guī)范和 api 規(guī)范2。j2me 定義了一套類庫(kù)和虛擬機(jī)技術(shù)，這些技術(shù)可以使用戶、服務(wù)提供 商和設(shè)備制造商通過(guò)物理（有線）連接或無(wú)線連接，按照需要隨時(shí)使用豐富的應(yīng)用程序。j2me 同時(shí)提供了 java 語(yǔ)言一貫的跨平臺(tái)性和安全性。為了支持用戶和嵌入式市場(chǎng)提出的靈活性和可定制性要求，j2me 被設(shè)計(jì)得更加模塊化 和可縮放化。j2me 在設(shè)備原有的操作系統(tǒng)上建造了 3 層軟件來(lái)實(shí)現(xiàn)這種要求：jvm 層：這層基于宿主操作系統(tǒng)，按照某一種 j2me 的配置實(shí)現(xiàn)了 jvm。 配置層：這層對(duì)于用戶可見(jiàn)度要低一些，但對(duì)簡(jiǎn)表層非常重要。它針對(duì)不同市場(chǎng)的需求，定義了 java 虛擬機(jī)的最小功能集合和 java 類庫(kù)的最小集合。在 j2me 設(shè)備中，jvm 與配置 層緊密相連，它們體現(xiàn)了每一類設(shè)備的基本功能。簡(jiǎn)表層：這層對(duì)于用戶和應(yīng)用程序提供者來(lái)說(shuō)是最常見(jiàn)的。它針對(duì)特定市場(chǎng)的需求，定 義了 java 虛擬機(jī)的最小功能集合和 java 類庫(kù)的最小集合。j2me 組件都圍繞一個(gè)中心，這些中心被稱為 configuration（配置），它們中間的每一個(gè)都是用于消費(fèi)電子和嵌入設(shè)備的特別的類。目前配置分為 cldc 和 cdc 兩種。connected limited device configuration( 有限連接設(shè)備配置，簡(jiǎn)稱 cldc) 定義支持 “devices that you hold in your hand（握在手中的設(shè)備）”的應(yīng)用程序接口和技術(shù)，這類設(shè)備的 代表是 pda。connected device configuration(連接設(shè)備配置 cdc )定義支持“devices that you plug into plug into the wall（插入墻的設(shè)備）”的應(yīng)用程序接口和技術(shù)，這類設(shè)備的代表是機(jī)- 5 -頂盒。這兩種配置不同的地方就在于它們應(yīng)用于的裝置的能力，cldc 設(shè)備的處理器能力有限 (與臺(tái)式機(jī)系統(tǒng)比較 )，并且存儲(chǔ)器大小一般也只在 128 kb 到 512 kb 之間。cdc 系統(tǒng)不同， 它可能有 32 位或 64 位處理器，以及有限的存儲(chǔ)容量，不過(guò)它的下限也得超過(guò) 512k。圖 1 配置和簡(jiǎn)表的體系結(jié)構(gòu)上圖解釋配置和簡(jiǎn)表的體系結(jié)構(gòu)。j2me 的體系結(jié)構(gòu)被橫向地分成三層，縱向分成兩部 分。配置包括一個(gè)控制配置核心類的虛擬機(jī)，具體的簡(jiǎn)表位于每個(gè)配置之上3。3. 多邊形掃描線填充算法3.1 理論分析midp2.0 中 graphics 提供的圖形填充算法支持的有圓弧，三角形，長(zhǎng)方形和圓角長(zhǎng)方 形，任意多邊形可以分解為多個(gè)三角形進(jìn)行填充，這里介紹另一種填充算法，通過(guò)掃描線進(jìn) 行多邊形填充。如下圖所示。圖 2 掃描線填充基于 j2me 平臺(tái) midp2.0 只支持對(duì)整數(shù)級(jí)像素填充，而且手持設(shè)備的屏幕較小，因此基 于 y 軸或 x 軸的掃描線數(shù)目有限，從而在處理能力和內(nèi)存有限的手持設(shè)備上使得掃描線算 法成為可能。首先計(jì)算出此多邊形在 x 軸或 y 軸的最大值 a 和最小值 b，并新建（a-b+1）個(gè)整形數(shù) 組來(lái)保存相交的點(diǎn)，然后用多邊形的邊去切掃描線，在對(duì)應(yīng)交點(diǎn)值的數(shù)組中保存交點(diǎn)的 x 值或 y 值。最終按照掃描線填充算法的基本原理，奇數(shù)的交點(diǎn)為進(jìn)入此多邊形，偶數(shù)的交 點(diǎn)為離開(kāi)此多邊形，調(diào)用 graphics 的 drawline 方法進(jìn)行繪制。3.2 算法分析優(yōu)點(diǎn)：簡(jiǎn)單實(shí)用，對(duì)于邊數(shù)不多，面積不是很大的任意多邊形來(lái)說(shuō)，算法的時(shí)間和空間 復(fù)雜度是可以接受的缺點(diǎn)：效率不高是主要問(wèn)題，同時(shí)多邊形中存在奇異點(diǎn)的情況，存在和掃描線重疊的 情況，因而需要加入特殊處理。特殊情況：1）多邊形有凸多邊形和凹多邊形，對(duì)于凸多邊形過(guò)極值點(diǎn)時(shí)滿足奇數(shù)點(diǎn)進(jìn)入多邊形， 偶數(shù)點(diǎn)離開(kāi)多邊形，凹多邊形則相反，因而此為一相異情況，如圖 2 中的 c 和 d 掃描線。2） 多邊形的頂點(diǎn)為一特殊情況，有極值點(diǎn)和非極值點(diǎn)，極值點(diǎn)時(shí)既為多邊形進(jìn)入點(diǎn)，又是多邊 形離開(kāi)點(diǎn)，非極值點(diǎn)則相反，如圖 2 中的 a 和 d 掃描線。3）采用 x 軸或 y 軸掃描線填充存 在邊與 x 軸或 y 軸重疊的情況，如圖 2 中的 b 掃描線。3.3 改進(jìn)算法為了消除填充算法存在的奇異情況，提出一個(gè)修正的方案，假設(shè)采用 x 軸作為掃描線， 多邊形在 y 軸上的最大值和最小值分別為 a 和 b，新建（a-b+1）個(gè)整形數(shù)組來(lái)保存相交的 點(diǎn)，在用多邊形的邊去切掃描線時(shí)，先判斷此邊是否為與 x 軸平行的直線，如是則將此邊 作一個(gè)標(biāo)記，將此點(diǎn)的 2 個(gè)端點(diǎn)的 x 值存入到對(duì)應(yīng)的數(shù)組中去，在畫(huà)掃描線時(shí)先判斷此數(shù) 組中存的從小到大的 x 值，如果此點(diǎn)前面沒(méi)有比它小的 x 值，則此直線的左端點(diǎn)值為無(wú)效 交點(diǎn)，反之則為有效交點(diǎn)。如果此邊不是與 x 軸平行的直線，則判斷此邊的 2 個(gè)端點(diǎn)是否 為極值點(diǎn)，極值點(diǎn)則在相應(yīng)的數(shù)組中存入 2 個(gè)一樣的 x 值，否則存入一個(gè) x 值。3.4 算法實(shí)現(xiàn)遍歷各邊，得到在 y 軸上的最大值 ymax 和最小值 ymin int ymax = -1;int ymin = 1000000;for(int i=0;i ymax)ymax = c;if(c ymax)ymax = c;if(c ymin)ymin = c;按 j2me 上像素單位為一的特征，創(chuàng)建 ymax-ymin+1 個(gè)整形數(shù)組來(lái)保存交點(diǎn)值int count = ymax-ymin+1;vector y = new vectorcount;for(int i=0;icount;i+)yi = new vector();遍歷各邊進(jìn)行掃描，按照改進(jìn)算法的判斷順序進(jìn)行操作，就奇異點(diǎn)的坐標(biāo)保存在一個(gè)數(shù) 組當(dāng)中，供畫(huà)掃描線所用，并將掃描得到的各交點(diǎn)值按從小到大的順序插入到對(duì)應(yīng)的交點(diǎn)數(shù)組當(dāng)中。for(int i=0;iedges.size();i+)edge curr = (edge)edges.elementat(i); if(curr.startp.gety()=curr.endp.gety()/平行 x 軸/奇異邊保存add(ycurr.startp.gety()-ymin,curr.startp.getx();/向數(shù)組中按順序插入 x 值else/取下一條邊，如果 i=edges.size()-1 則取第 0 條邊/判斷當(dāng)前邊的末端點(diǎn)是否為極值點(diǎn)if(極值點(diǎn))/極值點(diǎn)保存/向數(shù)組中按從小到大的順序插入 x 值按照奇異點(diǎn)和奇異邊的不同，分別從掃描線數(shù)組中按不同的處理繪制直線，并按需要的 顏色進(jìn)行著色，完成填充。3.5 算法擴(kuò)展對(duì)于曲線多邊形，可以將曲線看做是多條短邊的集合，從而使此掃描線填充算法也能很 好的適應(yīng)曲線多邊形，形成的曲線的邊的數(shù)目越大，曲線越精確，但是開(kāi)銷越大，算法的時(shí) 間復(fù)雜度和邊的數(shù)目和長(zhǎng)度相關(guān)的.3.6 運(yùn)行結(jié)果圖 3 填充結(jié)果可以看出本算法的效果不是特別的理想，在線條上沒(méi)有加入像素補(bǔ)充算法，從而使多邊形的邊存在粗糙的地方。4. 結(jié)束語(yǔ)圖形的效果直接影響到手持設(shè)備的受歡迎度，而多邊形填充是圖形的一個(gè)基本元素，因 而加強(qiáng)對(duì)基于 j2me 平臺(tái)的多邊形填充算法的研究，有助于手持設(shè)備上應(yīng)用軟件的質(zhì)量提高。 該算法是基于 j2me 平臺(tái)的實(shí)際情況來(lái)實(shí)現(xiàn)的，希望其它類似項(xiàng)目能從中受益。參考文獻(xiàn)1 黃聰明. java 移動(dòng)通信程序設(shè)計(jì)m. 北京: 清華大學(xué)出版社, 2002.2.2 陳昊鵬，饒若楠等. bruce eckel.java 編程思想m.北京:機(jī)械工業(yè)出版社, 2005 3 詹建飛. j2me 開(kāi)發(fā)精解m. 北京: 電子工業(yè)出版社, 2006a filling algorithm for arbitrary polygon based on j2meliu shengyun1, yang jun1, dong hongyi21department of computer science and technology, beijing university of posts andtelecommunications, beijing (100876)2laser institute of the shandong academy of sciences, jinan (272017)abstractthis thesis mainly introduces the j2me platform, about the architecture of j2me in brief.it puts forward the application environment of this polygon filling algorithm,based on this detailedly introduces thealgorithm and analyses the merits and drawbacks of the algorithm in theory and realization level.over the defects of the algorithm it brings forward an amendatory blue print for the algorithm,at last implements the scanning beam filling algorithm for arbitrary polygon based on the j2me criterion to render the graphics and image drawing and make an additional explanation for arbitrary curve polygon.in the en