JAVA如何實現掃描線算法

這篇文章給大家分享的是有關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: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<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];    //保存點擊的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;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];    //建立對應掃描邊數的鏈表長度
       for(int i=0;i<index-1;i++)
       {
         if(b[i]<b[i+1])          //從第一個點開始若前一個點小于后一個點
         {
           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)    //該點是第一個插入的節點
               {  
                 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為后一點的y
               }
             else {                //該點不是第一個插入的節點
                   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)  //當前插入x比之前存在的節點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)    //該點是第一個插入的節點
           {  
             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為后一點的y
           }
           else {                //該點不是第一個插入的節點
               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)  //當前插入x比之前存在的節點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])          //從第一個點到最后一個點
         {
           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)    //該點是第一個插入的節點
               {  
                 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為后一點的y
               }
             else {                //該點不是第一個插入的節點
                 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)  //當前插入x比之前存在的節點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)    //該點是第一個插入的節點
           {  
             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為后一點的y
           }
           else {                //該點不是第一個插入的節點
               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)  //當前插入x比之前存在的節點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();
    //一個點一個點的全裝入ca中再排序打印出點
      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("坐標為("+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();
  }
}

 效果截圖（先在面板里點擊點，右鍵出現所需填充的輪廓，鼠標移出面板填充）

感謝各位的閱讀！關于“JAVA如何實現掃描線算法”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！