JAVA中怎么實(shí)現(xiàn)一個(gè)掃描線算法

JAVA中怎么實(shí)現(xiàn)一個(gè)掃描線算法，很多新手對此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

對于掃描線的實(shí)現(xiàn)過程，我只在這里大概講下書本上的內(nèi)容（自己去看），主要還是講一下自己實(shí)現(xiàn)時(shí)算法的改動(dòng)和實(shí)現(xiàn)方法。

掃描線算法：顧名思義，就是從Ymin開始掃描，然后構(gòu)建出NET，之后根據(jù)NET建立AET。

貼個(gè)圖：

實(shí)現(xiàn)的時(shí)候首先是構(gòu)造NET，因?yàn)閷τ趈ava來說不能像c++一樣直接用指針?biāo)晕矣脤ο髷?shù)組和Node類（如下代碼）構(gòu)造了類似數(shù)組+指針的數(shù)據(jù)結(jié)構(gòu)。在實(shí)現(xiàn)了NET后開始通過NET實(shí)現(xiàn)AET，在這里我改變了一種實(shí)現(xiàn)方式，教科書上是一次次遍歷掃描線，然后將NET插入AET后進(jìn)行排序等一系列操作，而我因?yàn)槭亲约簩懙臄?shù)據(jù)結(jié)構(gòu)，如果說再建個(gè)表按書上的方式來最后還得自己實(shí)現(xiàn)鏈表排序等一系列操作。所以我這里直接用一個(gè)包含Arraylist的對象數(shù)組代替了。我的方法是：直接從NET開始遍歷每個(gè)節(jié)點(diǎn)，得到節(jié)點(diǎn)后將它以及它自己之后會(huì)引申出的插入AET的節(jié)點(diǎn)（比如當(dāng)前掃描線y=0 節(jié)點(diǎn) X:1 dx:-1 Ymax:3 那之后會(huì)插入AET的就是 0 -1 1 和 -1 -1 2 ）將這些節(jié)點(diǎn)不論順序的先插入AET對應(yīng)掃描線位置的對象數(shù)組的list中，將NET中節(jié)點(diǎn)全部遍歷完之后再最后對AET中每個(gè)對象數(shù)組的list進(jìn)行排序。最后得到了NET在進(jìn)行打印。

貼個(gè)代碼（僅供參考學(xué)習(xí)交流）：

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<Integer> list = new ArrayList<Integer>();  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];    //保存點(diǎn)擊的10個(gè)x坐標(biāo)  static int b[]=new int [10];    //保存點(diǎn)擊的10個(gè)y坐標(biāo)  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;i<b.length;i++)    {      if(Ymax<b[i])        Ymax=b[i];      }    // System.out.println("Ymax"+Ymax);    /*     * 畫出多邊形     */       int Sum=0;       for(;Sum<=index;Sum++) {         if(Sum==index-1)          {             g2d.drawLine(a[Sum], b[Sum], a[0],b[0]);             break;          }         else              {            g2d.drawLine(a[Sum], b[Sum], a[Sum+1],b[Sum+1]);            }       }      if(time!=0) {       Node [] head =new Node [Ymax];    //建立對應(yīng)掃描邊數(shù)的鏈表長度       for(int i=0;i<index-1;i++)       {         if(b[i]<b[i+1])          //從第一個(gè)點(diǎn)開始若前一個(gè)點(diǎn)小于后一個(gè)點(diǎn)         {           if(head[b[i]]==null)             head[b[i]]=new Node(0,0,0);             head[b[i]].ymin=b[i];             if(head[b[i]].next==null)    //該點(diǎn)是第一個(gè)插入的節(jié)點(diǎn)               {                   head[b[i]].next=new Node(0,0,0);                 head[b[i]].next.x=a[i];                 head[b[i]].next.dx=(float)(a[i]-a[i+1])/(b[i]-b[i+1]);                 head[b[i]].next.yMax=b[i+1];    //ymax為后一點(diǎn)的y               }             else {                //該點(diǎn)不是第一個(gè)插入的節(jié)點(diǎn)                   if(head[b[i]].next.next==null)                   head[b[i]].next.next=new Node(0,0,0);                   if((float)(a[i]-a[i+1])/(b[i]-b[i+1])<head[b[i]].next.dx)  //當(dāng)前插入x比之前存在的節(jié)點(diǎn)x小                   {                     head[b[i]].next.next.x=head[b[i]].next.x;                     head[b[i]].next.next.dx=head[b[i]].next.dx;                     head[b[i]].next.next.yMax=head[b[i]].next.yMax;                     head[b[i]].next.x=a[i];                     head[b[i]].next.dx=(float)(a[i]-a[i+1])/(b[i]-b[i+1]);                     head[b[i]].next.yMax=b[i+1];                   }                   else                   {                     head[b[i]].next.next.x=a[i];                     head[b[i]].next.next.dx=(float)(a[i]-a[i+1])/(b[i]-b[i+1]);                     head[b[i]].next.next.yMax=b[i+1];                   }               }         }         else         {             if(head[b[i+1]]==null)           head[b[i+1]]=new Node(0,0,0);           head[b[i+1]].ymin=b[i+1];           if(head[b[i+1]].next==null)    //該點(diǎn)是第一個(gè)插入的節(jié)點(diǎn)           {               head[b[i+1]].next=new Node(0,0,0);             head[b[i+1]].next.x=a[i+1];             head[b[i+1]].next.dx=(float)(a[i]-a[i+1])/(b[i]-b[i+1]);             head[b[i+1]].next.yMax=b[i];    //ymax為后一點(diǎn)的y           }           else {                //該點(diǎn)不是第一個(gè)插入的節(jié)點(diǎn)               if(head[b[i+1]].next.next==null)                 head[b[i+1]].next.next=new Node(0,0,0);               if((float)(a[i]-a[i+1])/(b[i]-b[i+1])<head[b[i+1]].next.dx)  //當(dāng)前插入x比之前存在的節(jié)點(diǎn)x小               {                 head[b[i+1]].next.next.x=head[b[i+1]].next.x;                 head[b[i+1]].next.next.dx=(float)head[b[i+1]].next.dx;                 head[b[i+1]].next.next.yMax=head[b[i+1]].next.yMax;                 head[b[i+1]].next.x=a[i+1];                 head[b[i+1]].next.dx=(float)(a[i]-a[i+1])/(b[i]-b[i+1]);                 head[b[i+1]].next.yMax=b[i];               }               else               {                 head[b[i+1]].next.next.x=a[i+1];                 head[b[i+1]].next.next.dx=(float)(a[i]-a[i+1])/(b[i]-b[i+1]);                 head[b[i+1]].next.next.yMax=b[i];               }           }         }       }       if(index>0)       {  if(b[0]<b[index-1])          //從第一個(gè)點(diǎn)到最后一個(gè)點(diǎn)         {           if(head[b[0]]==null)             head[b[0]]=new Node(0,0,0);             head[b[0]].ymin=b[0];             if(head[b[0]].next==null)    //該點(diǎn)是第一個(gè)插入的節(jié)點(diǎn)               {                   head[b[0]].next=new Node(0,0,0);                 head[b[0]].next.x=a[0];                 head[b[0]].next.dx=(float)(a[0]-a[index-1])/(b[0]-b[index-1]);                 head[b[0]].next.yMax=b[index-1];    //ymax為后一點(diǎn)的y               }             else {                //該點(diǎn)不是第一個(gè)插入的節(jié)點(diǎn)                 if(head[b[0]].next.next==null)                   head[b[0]].next.next=new Node(0,0,0);                   if((float)(a[0]-a[index-1])/(b[0]-b[index-1])<head[b[0]].next.dx)  //當(dāng)前插入x比之前存在的節(jié)點(diǎn)x小                   {                     head[b[0]].next.next.x=head[b[0]].next.x;                     head[b[0]].next.next.dx=head[b[0]].next.dx;                     head[b[0]].next.next.yMax=head[b[0]].next.yMax;                     head[b[0]].next.x=a[0];                     head[b[0]].next.dx=(float)(a[0]-a[index-1])/(b[0]-b[index-1]);                     head[b[0]].next.yMax=b[index-1];                   }                   else                   {                     head[b[0]].next.next.x=a[0];                     head[b[0]].next.next.dx=(float)(a[0]-a[index-1])/(b[0]-b[index-1]);                     head[b[0]].next.next.yMax=b[index-1];                   }               }         }         else         {             if(head[b[index-1]]==null)           head[b[index-1]]=new Node(0,0,0);           head[b[index-1]].ymin=b[index-1];           if(head[b[index-1]].next==null)    //該點(diǎn)是第一個(gè)插入的節(jié)點(diǎn)           {               head[b[index-1]].next=new Node(0,0,0);             head[b[index-1]].next.x=a[index-1];             head[b[index-1]].next.dx=(float)(a[0]-a[index-1])/(b[0]-b[index-1]);             head[b[index-1]].next.yMax=b[0];    //ymax為后一點(diǎn)的y           }           else {                //該點(diǎn)不是第一個(gè)插入的節(jié)點(diǎn)               if(head[b[index-1]].next.next==null)               head[b[index-1]].next.next=new Node(0,0,0);               if((float)(a[0]-a[index-1])/(b[0]-b[index-1])<head[b[index-1]].next.dx)  //當(dāng)前插入x比之前存在的節(jié)點(diǎn)x小               {                 head[b[index-1]].next.next.x=head[b[index-1]].next.x;                 head[b[index-1]].next.next.dx=head[b[index-1]].next.dx;                 head[b[index-1]].next.next.yMax=head[b[index-1]].next.yMax;                 head[b[index-1]].next.x=a[index-1];                 head[b[index-1]].next.dx=(float)(a[0]-a[index-1])/(b[0]-b[index-1]);                 head[b[index-1]].next.yMax=b[0];               }               else               {                 head[b[index-1]].next.next.x=a[index-1];                 head[b[index-1]].next.next.dx=(float)(a[0]-a[index-1])/(b[0]-b[index-1]);                 head[b[index-1]].next.next.yMax=b[0];               }           }         }       }     for(int i=0;i<Ymax;i++)       if(head[i]!=null)         while(head[i].next!=null)         {  System.out.println("新編表y"+head[i].ymin+"新編表x"+head[i].next.x+"新編表dx"+head[i].next.dx+"新編表yMax"+head[i].next.yMax);           if(head[i].next.next!=null)           {             System.out.println("多的"+"新編表y"+head[i].ymin+"新編表x"+head[i].next.next.x+"新編表dx"+head[i].next.next.dx+"新編表yMax"+head[i].next.next.yMax);           }           break;         }     int YMIN=b[0];    for(int i=0;i<b.length;i++)    {      if(YMIN>b[i]&&b[i]!=0)        YMIN=b[i];    }    classAndArray [] ca=new classAndArray [Ymax];    for(int i=YMIN;i<Ymax;i++)        ca[i]=new classAndArray();    //一個(gè)點(diǎn)一個(gè)點(diǎn)的全裝入ca中再排序打印出點(diǎn)      for(int i=0;i<Ymax;i++)       {          if(head[i]!=null)           if(head[i].next!=null)           {               //System.out.println("新編表y"+head[i].ymin+"新編表x"+head[i].next.x+"新編表dx"+head[i].next.dx+"新編表yMax"+head[i].next.yMax);               for(int j=head[i].ymin;j<head[i].next.yMax;j++)               {                 ca[i+j-head[i].ymin].list.add(head[i].next.x+(int)(0.5+((j-head[i].ymin)*head[i].next.dx)));                 //System.out.print("ca[i+j-head[i].ymin]為"+(i+j-head[i].ymin)+"值為"+ca[i+j-head[i].ymin].list.toString());                 //System.out.println("Ymin為"+i+" x為"+(head[i].next.x+(j-head[i].ymin)*head[i].next.dx));               }             if(head[i].next.next!=null)             {               for(int j=head[i].ymin;j<head[i].next.next.yMax;j++)               {                 ca[i+j-head[i].ymin].list.add(head[i].next.next.x+(int)(0.5+(j-head[i].ymin)*head[i].next.next.dx));                 //System.out.print("next中ca[i+j-head[i].ymin]為"+(i+j-head[i].ymin)+"值為"+ca[i+j-head[i].ymin].list.toString());                 //System.out.println("Ymin為"+i+" x為"+head[i].next.next.x+(j-head[i].ymin)*head[i].next.next.dx);               }               //System.out.println("多的"+"新編表y"+head[i].ymin+"新編表x"+head[i].next.next.x+"新編表dx"+head[i].next.next.dx+"新編表yMax"+head[i].next.next.yMax);             }           }       }//       for(int i=YMIN;i<Ymax;i++)        {        ca[i].listSort();       for (int j = 0; j < ca[i].list.size(); j++) {             if(j%2==0||(j==0))             {               g2d.drawLine(ca[i].list.get(j), i, ca[i].list.get(j+1), i);             }           }        System.out.println(ca[i].list.toString());      }        }  }    private static void createAndShowGUI() {    JFrame frame = new JFrame();     frame.setLocationRelativeTo(null);    frame.setLayout(null);    JPanel jp=new JPanel();      frame.setContentPane(jp);     frame.setVisible(true);     frame.addMouseListener(new MouseAdapter() {        });    jp.addMouseListener(new MouseAdapter() {        public void mouseClicked(MouseEvent e) {          if(e.getButton() == e.BUTTON1)          {a[index]=e.getX();          b[index]=e.getY();          System.out.println("坐標(biāo)為("+a[index]+","+b[index]+")");          index++;              frame.setVisible(true);          }                    if(e.getButton() == e.BUTTON3)          {                        frame.setContentPane(new PolygonScanning());            frame.setVisible(true);          }        }    }        );   frame.setSize(600, 600);    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);    frame.setLocationRelativeTo(null);    frame.setVisible(true);  }  public static void main(String[] args) throws IOException {    createAndShowGUI();  }}

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。