JAVA实现扫描线算法(超详细)
首先说一下,教科书上的扫描线算法确实是用c++很好实现,而且网上有很多源码,而java实现的基本没有(可能是我没看到),所以肖先生还是打算自己码(实验作业写这个而自己又个是写java的猿0.0)。
对于扫描线的实现过程,我只在这里大概讲下书本上的内容(自己去看),主要还是讲一下自己实现时算法的改动和实现方法。
扫描线算法:顾名思义,就是从Ymin开始扫描,然后构建出NET,之后根据NET建立AET。
贴个图:
实现的时候首先是构造NET,因为对于java来说不能像c++一样直接用指针所以我用对象数组和Node类(如下代码)构造了类似数组+指针的数据结构。在实现了NET后开始通过NET实现AET,在这里我改变了一种实现方式,教科书上是一次次遍历扫描线,然后将NET插入AET后进行排序等一系列操作,而我因为是自己写的数据结构,如果说再建个表按书上的方式来最后还得自己实现链表排序等一系列操作。所以我这里直接用一个包含Arraylist的对象数组代替了。我的方法是:直接从NET开始遍历每个节点,得到节点后将它以及它自己之后会引申出的插入AET的节点(比如当前扫描线y=0节点 X:1dx:-1 Ymax:3那之后会插入AET的就是0-11 和 -1 -1 2)将这些节点不论顺序的先插入AET对应扫描线位置的对象数组的list中,将NET中节点全部遍历完之后再最后对AET中每个对象数组的list进行排序。最后得到了NET在进行打印。
贴个代码(仅供参考学习交流):
packagePolygonScanningAndFilling; publicclassNode{//新编表记录x,dx,yMax publicintx; publicfloatdx; publicintyMax; publicNodenext; publicintymin; publicNode(intx,intdx,intyMax){ this.x=x; this.dx=dx; this.yMax=yMax; } publicvoidgetYmin(intYmin){ this.ymin=Ymin; } } packagePolygonScanningAndFilling; importjava.util.ArrayList; importjava.util.Collections; importjava.util.List; publicclassclassAndArray{ publicListlist=newArrayList (); publicclassAndArray(){ } publicvoidlistSort(){ Collections.sort(list); } } packagePolygonScanningAndFilling; importjava.util.Iterator; importjava.util.Timer; importjava.util.TimerTask; importjavax.swing.*; importjava.awt.*; importjava.awt.event.ActionEvent; importjava.awt.event.ActionListener; importjava.awt.event.KeyEvent; importjava.awt.event.KeyListener; importjava.awt.event.MouseAdapter; importjava.awt.event.MouseEvent; importjava.io.IOException; publicclassPolygonScanningextendsJPanel{ staticintX0; staticintY0; staticintX1; staticintY1; staticinta[]=newint[10];//保存点击的10个x坐标 staticintb[]=newint[10];//保存点击的10个y坐标 staticintindex=0; staticinttime=0; @Override protectedvoidpaintComponent(Graphicsg){ super.paintComponent(g); this.addMouseListener(newMouseAdapter(){ publicvoidmouseExited(MouseEvente){ time++; repaint(); } }); Graphics2Dg2d=(Graphics2D)g; intYmax=0; for(inti=0;i 0) {if(b[0]b[i]&&b[i]!=0) YMIN=b[i]; } classAndArray[]ca=newclassAndArray[Ymax]; for(inti=YMIN;i 效果截图(先在面板里点击点,右键出现所需填充的轮廓,鼠标移出面板填充)
总结
以上所述是小编给大家介绍的JAVA实现扫描线算法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。