JAVA中怎么实现一个扫描线算法

JAVA中怎么实现一个扫描线算法,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

创新互联坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都网站建设、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的城中网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!

对于扫描线的实现过程,我只在这里大概讲下书本上的内容(自己去看),主要还是讲一下自己实现时算法的改动和实现方法。

扫描线算法:顾名思义,就是从Ymin开始扫描,然后构建出NET,之后根据NET建立AET。

贴个图:

实现的时候首先是构造NET,因为对于java来说不能像c++一样直接用指针所以我用对象数组和Node类(如下代码)构造了类似数组+指针的数据结构。在实现了NET后开始通过NET实现AET,在这里我改变了一种实现方式,教科书上是一次次遍历扫描线,然后将NET插入AET后进行排序等一系列操作,而我因为是自己写的数据结构,如果说再建个表按书上的方式来最后还得自己实现链表排序等一系列操作。所以我这里直接用一个包含Arraylist的对象数组代替了。我的方法是:直接从NET开始遍历每个节点,得到节点后将它以及它自己之后会引申出的插入AET的节点(比如当前扫描线y=0 节点 X:1 dx:-1 Ymax:3 那之后会插入AET的就是 0 -1 1 和 -1 -1 2 )将这些节点不论顺序的先插入AET对应扫描线位置的对象数组的list中,将NET中节点全部遍历完之后再最后对AET中每个对象数组的list进行排序。最后得到了NET在进行打印。

贴个代码(仅供参考学习交流):

package PolygonScanningAndFilling;public class Node {    //新编表记录x,dx,yMax  public int x;  public float dx;  public int yMax;  public Node next;  public int ymin;  public Node(int x, int dx, int yMax){    this.x=x;    this.dx=dx;    this.yMax=yMax;  }  public void getYmin(int Ymin){    this.ymin=Ymin;  }}package PolygonScanningAndFilling;import java.util.ArrayList;import java.util.Collections;import java.util.List;public class classAndArray {  public List list = new ArrayList();  public classAndArray(){  }  public void listSort() {    Collections.sort(list);  }}package PolygonScanningAndFilling;import java.util.Iterator;import java.util.Timer;import java.util.TimerTask;import javax.swing.*;import java.awt.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.KeyEvent;import java.awt.event.KeyListener;import java.awt.event.MouseAdapter;import java.awt.event.MouseEvent;import java.io.IOException;public class PolygonScanning extends JPanel {  static int X0;  static int Y0;  static int X1;  static int Y1;  static int a[]=new int [10];    //保存点击的10个x坐标  static int b[]=new int [10];    //保存点击的10个y坐标  static int index=0;  static int time=0;    @Override  protected void paintComponent(Graphics g) {    super.paintComponent(g);    this.addMouseListener(new MouseAdapter() {           public void mouseExited(MouseEvent e) {          time++;          repaint();        }     });    Graphics2D g2d = (Graphics2D)g;    int Ymax=0;    for(int i=0;i0)       {  if(b[0]b[i]&&b[i]!=0)        YMIN=b[i];    }    classAndArray [] ca=new classAndArray [Ymax];    for(int i=YMIN;i

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注创新互联行业资讯频道,感谢您对创新互联的支持。


文章题目:JAVA中怎么实现一个扫描线算法
标题URL:http://scyanting.com/article/ihhhgi.html