JAVA實現掃描線演算法
- 2019 年 10 月 30 日
- 筆記
首先說一下，教科書上的掃描線演算法確實是用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(); } }
效果截圖（先在面板里點擊點，右鍵出現所需填充的輪廓，滑鼠移出面板填充）
