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

精品论文推荐j2me 上任意多边形填充算法刘胜云 1，杨俊 1，董洪毅 21 北京邮电大学计算机科学技术系，北京 (100876)2 山东省科学院激光研究所，济南 (272017)e-mail: 摘要：本论文主要对 j2me 平台进行介绍，简要的介绍了 j2me 的体系结构，提出了此多边形填充算法的应用环境，在此基础上详细的介绍此填充算法，从理论和实现 2 层上分析此 算法的优缺点，并在算法的缺点之上提出一个修正的方案，最终实现一个基于 j2me 规范的任意多边形填充之扫描线填充算法，来实现对 j2me 上图形图像的渲染，并加入对曲线多边 形填充的一些补充说明,并就此算法在基于 j2me 平台的手机上运行，给出其运行结果和结果分析，并证明了此算法在 j2me 平台上的可行性。 关键字：j2me；像素；扫描线中图分类号：tp311.11. 引言j2me 作为嵌入式系统应用平台得到了迅速的发展，java 语言固有的平台无关性使得基 于 j2me 平台的嵌入式应用系统具有广阔的前景1。随着手机为主的移动手持设备的增加， 手持设备上的应用开发需求稳步上升。j2me 作为手持设备的主流开发平台之一，是实现手 持设备各种综合应用的一个重要途径。手持设备上图形图像的处理是各种应用中最基本应用 之一，所以对 j2me 上多边形填充算法的研究日益重要。本文就 j2me 上任意多边形填充算 法之扫描线填充做简单分析和介绍。2. j2me 介绍j2me（java 2 platform micro edition）是为无线电子市场所设计的 java 平台，包括 jvm 规范和 api 规范2。j2me 定义了一套类库和虚拟机技术，这些技术可以使用户、服务提供 商和设备制造商通过物理（有线）连接或无线连接，按照需要随时使用丰富的应用程序。j2me 同时提供了 java 语言一贯的跨平台性和安全性。为了支持用户和嵌入式市场提出的灵活性和可定制性要求，j2me 被设计得更加模块化 和可缩放化。j2me 在设备原有的操作系统上建造了 3 层软件来实现这种要求：jvm 层：这层基于宿主操作系统，按照某一种 j2me 的配置实现了 jvm。 配置层：这层对于用户可见度要低一些，但对简表层非常重要。它针对不同市场的需求，定义了 java 虚拟机的最小功能集合和 java 类库的最小集合。在 j2me 设备中，jvm 与配置 层紧密相连，它们体现了每一类设备的基本功能。简表层：这层对于用户和应用程序提供者来说是最常见的。它针对特定市场的需求，定 义了 java 虚拟机的最小功能集合和 java 类库的最小集合。j2me 组件都围绕一个中心，这些中心被称为 configuration（配置），它们中间的每一个都是用于消费电子和嵌入设备的特别的类。目前配置分为 cldc 和 cdc 两种。connected limited device configuration( 有限连接设备配置，简称 cldc) 定义支持 “devices that you hold in your hand（握在手中的设备）”的应用程序接口和技术，这类设备的 代表是 pda。connected device configuration(连接设备配置 cdc )定义支持“devices that you plug into plug into the wall（插入墙的设备）”的应用程序接口和技术，这类设备的代表是机- 5 -顶盒。这两种配置不同的地方就在于它们应用于的装置的能力，cldc 设备的处理器能力有限 (与台式机系统比较 )，并且存储器大小一般也只在 128 kb 到 512 kb 之间。cdc 系统不同， 它可能有 32 位或 64 位处理器，以及有限的存储容量，不过它的下限也得超过 512k。图 1 配置和简表的体系结构上图解释配置和简表的体系结构。j2me 的体系结构被横向地分成三层，纵向分成两部 分。配置包括一个控制配置核心类的虚拟机，具体的简表位于每个配置之上3。3. 多边形扫描线填充算法3.1 理论分析midp2.0 中 graphics 提供的图形填充算法支持的有圆弧，三角形，长方形和圆角长方 形，任意多边形可以分解为多个三角形进行填充，这里介绍另一种填充算法，通过扫描线进 行多边形填充。如下图所示。图 2 扫描线填充基于 j2me 平台 midp2.0 只支持对整数级像素填充，而且手持设备的屏幕较小，因此基 于 y 轴或 x 轴的扫描线数目有限，从而在处理能力和内存有限的手持设备上使得扫描线算 法成为可能。首先计算出此多边形在 x 轴或 y 轴的最大值 a 和最小值 b，并新建（a-b+1）个整形数 组来保存相交的点，然后用多边形的边去切扫描线，在对应交点值的数组中保存交点的 x 值或 y 值。最终按照扫描线填充算法的基本原理，奇数的交点为进入此多边形，偶数的交 点为离开此多边形，调用 graphics 的 drawline 方法进行绘制。3.2 算法分析优点：简单实用，对于边数不多，面积不是很大的任意多边形来说，算法的时间和空间 复杂度是可以接受的缺点：效率不高是主要问题，同时多边形中存在奇异点的情况，存在和扫描线重叠的 情况，因而需要加入特殊处理。特殊情况：1）多边形有凸多边形和凹多边形，对于凸多边形过极值点时满足奇数点进入多边形， 偶数点离开多边形，凹多边形则相反，因而此为一相异情况，如图 2 中的 c 和 d 扫描线。2） 多边形的顶点为一特殊情况，有极值点和非极值点，极值点时既为多边形进入点，又是多边 形离开点，非极值点则相反，如图 2 中的 a 和 d 扫描线。3）采用 x 轴或 y 轴扫描线填充存 在边与 x 轴或 y 轴重叠的情况，如图 2 中的 b 扫描线。3.3 改进算法为了消除填充算法存在的奇异情况，提出一个修正的方案，假设采用 x 轴作为扫描线， 多边形在 y 轴上的最大值和最小值分别为 a 和 b，新建（a-b+1）个整形数组来保存相交的 点，在用多边形的边去切扫描线时，先判断此边是否为与 x 轴平行的直线，如是则将此边 作一个标记，将此点的 2 个端点的 x 值存入到对应的数组中去，在画扫描线时先判断此数 组中存的从小到大的 x 值，如果此点前面没有比它小的 x 值，则此直线的左端点值为无效 交点，反之则为有效交点。如果此边不是与 x 轴平行的直线，则判断此边的 2 个端点是否 为极值点，极值点则在相应的数组中存入 2 个一样的 x 值，否则存入一个 x 值。3.4 算法实现遍历各边，得到在 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 上像素单位为一的特征，创建 ymax-ymin+1 个整形数组来保存交点值int count = ymax-ymin+1;vector y = new vectorcount;for(int i=0;icount;i+)yi = new vector();遍历各边进行扫描，按照改进算法的判断顺序进行操作，就奇异点的坐标保存在一个数 组当中，供画扫描线所用，并将扫描得到的各交点值按从小到大的顺序插入到对应的交点数组当中。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();/向数组中按顺序插入 x 值else/取下一条边，如果 i=edges.size()-1 则取第 0 条边/判断当前边的末端点是否为极值点if(极值点)/极值点保存/向数组中按从小到大的顺序插入 x 值按照奇异点和奇异边的不同，分别从扫描线数组中按不同的处理绘制直线，并按需要的 颜色进行着色，完成填充。3.5 算法扩展对于曲线多边形，可以将曲线看做是多条短边的集合，从而使此扫描线填充算法也能很 好的适应曲线多边形，形成的曲线的边的数目越大，曲线越精确，但是开销越大，算法的时 间复杂度和边的数目和长度相关的.3.6 运行结果图 3 填充结果可以看出本算法的效果不是特别的理想，在线条上没有加入像素补充算法，从而使多边形的边存在粗糙的地方。4. 结束语图形的效果直接影响到手持设备的受欢迎度，而多边形填充是图形的一个基本元素，因 而加强对基于 j2me 平台的多边形填充算法的研究，有助于手持设备上应用软件的质量提高。 该算法是基于 j2me 平台的实际情况来实现的，希望其它类似项目能从中受益。参考文献1 黄聪明. java 移动通信程序设计m. 北京: 清华大学出版社, 2002.2.2 陈昊鹏，饶若楠等. bruce eckel.java 编程思想m.北京:机械工业出版社, 2005 3 詹建飞. j2me 开发精解m. 北京: 电子工业出版社, 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