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

精品論文推薦j2me 上任意多邊形填充算法劉勝云 1，楊俊 1，董洪毅 21 北京郵電大學(xué)計算機(jī)科學(xué)技術(shù)系，北京 (100876)2 山東省科學(xué)院激光研究所，濟(jì)南 (272017)e-mail: 摘要：本論文主要對 j2me 平臺進(jìn)行介紹，簡要的介紹了 j2me 的體系結(jié)構(gòu)，提出了此多邊形填充算法的應(yīng)用環(huán)境，在此基礎(chǔ)上詳細(xì)的介紹此填充算法，從理論和實(shí)現(xiàn) 2 層上分析此 算法的優(yōu)缺點(diǎn)，并在算法的缺點(diǎn)之上提出一個修正的方案，最終實(shí)現(xiàn)一個基于 j2me 規(guī)范的任意多邊形填充之掃描線填充算法，來實(shí)現(xiàn)對 j2me 上圖形圖像的渲染，并加入對曲線多邊 形填充的一些補(bǔ)充說明,并就此算法在基于 j2me 平臺的手機(jī)上運(yùn)行，給出其運(yùn)行結(jié)果和結(jié)果分析，并證明了此算法在 j2me 平臺上的可行性。 關(guān)鍵字：j2me；像素；掃描線中圖分類號：tp311.11. 引言j2me 作為嵌入式系統(tǒng)應(yīng)用平臺得到了迅速的發(fā)展，java 語言固有的平臺無關(guān)性使得基 于 j2me 平臺的嵌入式應(yīng)用系統(tǒng)具有廣闊的前景1。隨著手機(jī)為主的移動手持設(shè)備的增加， 手持設(shè)備上的應(yīng)用開發(fā)需求穩(wěn)步上升。j2me 作為手持設(shè)備的主流開發(fā)平臺之一，是實(shí)現(xiàn)手 持設(shè)備各種綜合應(yīng)用的一個重要途徑。手持設(shè)備上圖形圖像的處理是各種應(yīng)用中最基本應(yīng)用 之一，所以對 j2me 上多邊形填充算法的研究日益重要。本文就 j2me 上任意多邊形填充算 法之掃描線填充做簡單分析和介紹。2. j2me 介紹j2me（java 2 platform micro edition）是為無線電子市場所設(shè)計的 java 平臺，包括 jvm 規(guī)范和 api 規(guī)范2。j2me 定義了一套類庫和虛擬機(jī)技術(shù)，這些技術(shù)可以使用戶、服務(wù)提供 商和設(shè)備制造商通過物理（有線）連接或無線連接，按照需要隨時使用豐富的應(yīng)用程序。j2me 同時提供了 java 語言一貫的跨平臺性和安全性。為了支持用戶和嵌入式市場提出的靈活性和可定制性要求，j2me 被設(shè)計得更加模塊化 和可縮放化。j2me 在設(shè)備原有的操作系統(tǒng)上建造了 3 層軟件來實(shí)現(xiàn)這種要求：jvm 層：這層基于宿主操作系統(tǒng)，按照某一種 j2me 的配置實(shí)現(xiàn)了 jvm。 配置層：這層對于用戶可見度要低一些，但對簡表層非常重要。它針對不同市場的需求，定義了 java 虛擬機(jī)的最小功能集合和 java 類庫的最小集合。在 j2me 設(shè)備中，jvm 與配置 層緊密相連，它們體現(xiàn)了每一類設(shè)備的基本功能。簡表層：這層對于用戶和應(yīng)用程序提供者來說是最常見的。它針對特定市場的需求，定 義了 java 虛擬機(jī)的最小功能集合和 java 類庫的最小集合。j2me 組件都圍繞一個中心，這些中心被稱為 configuration（配置），它們中間的每一個都是用于消費(fèi)電子和嵌入設(shè)備的特別的類。目前配置分為 cldc 和 cdc 兩種。connected limited device configuration( 有限連接設(shè)備配置，簡稱 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è)備的處理器能力有限 (與臺式機(jī)系統(tǒng)比較 )，并且存儲器大小一般也只在 128 kb 到 512 kb 之間。cdc 系統(tǒng)不同， 它可能有 32 位或 64 位處理器，以及有限的存儲容量，不過它的下限也得超過 512k。圖 1 配置和簡表的體系結(jié)構(gòu)上圖解釋配置和簡表的體系結(jié)構(gòu)。j2me 的體系結(jié)構(gòu)被橫向地分成三層，縱向分成兩部 分。配置包括一個控制配置核心類的虛擬機(jī)，具體的簡表位于每個配置之上3。3. 多邊形掃描線填充算法3.1 理論分析midp2.0 中 graphics 提供的圖形填充算法支持的有圓弧，三角形，長方形和圓角長方 形，任意多邊形可以分解為多個三角形進(jìn)行填充，這里介紹另一種填充算法，通過掃描線進(jìn) 行多邊形填充。如下圖所示。圖 2 掃描線填充基于 j2me 平臺 midp2.0 只支持對整數(shù)級像素填充，而且手持設(shè)備的屏幕較小，因此基 于 y 軸或 x 軸的掃描線數(shù)目有限，從而在處理能力和內(nèi)存有限的手持設(shè)備上使得掃描線算 法成為可能。首先計算出此多邊形在 x 軸或 y 軸的最大值 a 和最小值 b，并新建（a-b+1）個整形數(shù) 組來保存相交的點(diǎn)，然后用多邊形的邊去切掃描線，在對應(yīng)交點(diǎn)值的數(shù)組中保存交點(diǎn)的 x 值或 y 值。最終按照掃描線填充算法的基本原理，奇數(shù)的交點(diǎn)為進(jìn)入此多邊形，偶數(shù)的交 點(diǎn)為離開此多邊形，調(diào)用 graphics 的 drawline 方法進(jìn)行繪制。3.2 算法分析優(yōu)點(diǎn)：簡單實(shí)用，對于邊數(shù)不多，面積不是很大的任意多邊形來說，算法的時間和空間 復(fù)雜度是可以接受的缺點(diǎn)：效率不高是主要問題，同時多邊形中存在奇異點(diǎn)的情況，存在和掃描線重疊的 情況，因而需要加入特殊處理。特殊情況：1）多邊形有凸多邊形和凹多邊形，對于凸多邊形過極值點(diǎn)時滿足奇數(shù)點(diǎn)進(jìn)入多邊形， 偶數(shù)點(diǎn)離開多邊形，凹多邊形則相反，因而此為一相異情況，如圖 2 中的 c 和 d 掃描線。2） 多邊形的頂點(diǎn)為一特殊情況，有極值點(diǎn)和非極值點(diǎn)，極值點(diǎn)時既為多邊形進(jìn)入點(diǎn)，又是多邊 形離開點(diǎn)，非極值點(diǎn)則相反，如圖 2 中的 a 和 d 掃描線。3）采用 x 軸或 y 軸掃描線填充存 在邊與 x 軸或 y 軸重疊的情況，如圖 2 中的 b 掃描線。3.3 改進(jìn)算法為了消除填充算法存在的奇異情況，提出一個修正的方案，假設(shè)采用 x 軸作為掃描線， 多邊形在 y 軸上的最大值和最小值分別為 a 和 b，新建（a-b+1）個整形數(shù)組來保存相交的 點(diǎn)，在用多邊形的邊去切掃描線時，先判斷此邊是否為與 x 軸平行的直線，如是則將此邊 作一個標(biāo)記，將此點(diǎn)的 2 個端點(diǎn)的 x 值存入到對應(yīng)的數(shù)組中去，在畫掃描線時先判斷此數(shù) 組中存的從小到大的 x 值，如果此點(diǎn)前面沒有比它小的 x 值，則此直線的左端點(diǎn)值為無效 交點(diǎn)，反之則為有效交點(diǎn)。如果此邊不是與 x 軸平行的直線，則判斷此邊的 2 個端點(diǎn)是否 為極值點(diǎn)，極值點(diǎn)則在相應(yīng)的數(shù)組中存入 2 個一樣的 x 值，否則存入一個 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 個整形數(shù)組來保存交點(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)保存在一個數(shù) 組當(dāng)中，供畫掃描線所用，并將掃描得到的各交點(diǎn)值按從小到大的順序插入到對應(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ò)展對于曲線多邊形，可以將曲線看做是多條短邊的集合，從而使此掃描線填充算法也能很 好的適應(yīng)曲線多邊形，形成的曲線的邊的數(shù)目越大，曲線越精確，但是開銷越大，算法的時 間復(fù)雜度和邊的數(shù)目和長度相關(guān)的.3.6 運(yùn)行結(jié)果圖 3 填充結(jié)果可以看出本算法的效果不是特別的理想，在線條上沒有加入像素補(bǔ)充算法，從而使多邊形的邊存在粗糙的地方。4. 結(jié)束語圖形的效果直接影響到手持設(shè)備的受歡迎度，而多邊形填充是圖形的一個基本元素，因 而加強(qiáng)對基于 j2me 平臺的多邊形填充算法的研究，有助于手持設(shè)備上應(yīng)用軟件的質(zhì)量提高。 該算法是基于 j2me 平臺的實(shí)際情況來實(shí)現(xiàn)的，希望其它類似項(xiàng)目能從中受益。參考文獻(xiàn)1 黃聰明. java 移動通信程序設(shè)計m. 北京: 清華大學(xué)出版社, 2002.2.2 陳昊鵬，饒若楠等. bruce eckel.java 編程思想m.北京:機(jī)械工業(yè)出版社, 2005 3 詹建飛. j2me 開發(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