JAVA實(shí)現(xiàn)掃描線算法(超詳細(xì))
更新時(shí)間：2019年10月30日 09:18:27 作者：肖先生的博客
掃描線算法就是從Ymin開(kāi)始掃描，然后構(gòu)建出NET，之后根據(jù)NET建立AET。接下來(lái)本文通過(guò)代碼給大家介紹JAVA實(shí)現(xiàn)掃描線算法，感興趣的朋友一起看看吧
首先說(shuō)一下，教科書上的掃描線算法確實(shí)是用c++很好實(shí)現(xiàn)，而且網(wǎng)上有很多源碼，而java實(shí)現(xiàn)的基本沒(méi)有（可能是我沒(méi)看到），所以肖先生還是打算自己碼（實(shí)驗(yàn)作業(yè)寫這個(gè)而自己又個(gè)是寫java的猿0.0）。
對(duì)于掃描線的實(shí)現(xiàn)過(guò)程，我只在這里大概講下書本上的內(nèi)容（自己去看），主要還是講一下自己實(shí)現(xiàn)時(shí)算法的改動(dòng)和實(shí)現(xiàn)方法。
掃描線算法：顧名思義，就是從Ymin開(kāi)始掃描，然后構(gòu)建出NET，之后根據(jù)NET建立AET。
貼個(gè)圖：
實(shí)現(xiàn)的時(shí)候首先是構(gòu)造NET，因?yàn)閷?duì)于java來(lái)說(shuō)不能像c++一樣直接用指針?biāo)晕矣脤?duì)象數(shù)組和Node類（如下代碼）構(gòu)造了類似數(shù)組+指針的數(shù)據(jù)結(jié)構(gòu)。在實(shí)現(xiàn)了NET后開(kāi)始通過(guò)NET實(shí)現(xiàn)AET，在這里我改變了一種實(shí)現(xiàn)方式，教科書上是一次次遍歷掃描線，然后將NET插入AET后進(jìn)行排序等一系列操作，而我因?yàn)槭亲约簩懙臄?shù)據(jù)結(jié)構(gòu)，如果說(shuō)再建個(gè)表按書上的方式來(lái)最后還得自己實(shí)現(xiàn)鏈表排序等一系列操作。所以我這里直接用一個(gè)包含Arraylist的對(duì)象數(shù)組代替了。我的方法是：直接從NET開(kāi)始遍歷每個(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對(duì)應(yīng)掃描線位置的對(duì)象數(shù)組的list中，將NET中節(jié)點(diǎn)全部遍歷完之后再最后對(duì)AET中每個(gè)對(duì)象數(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]; //建立對(duì)應(yīng)掃描邊數(shù)的鏈表長(zhǎng)度
for(int i=0;i<index-1;i++)
{
if(b[i]<b[i+1]) //從第一個(gè)點(diǎn)開(kāi)始若前一個(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();
}
}
效果截圖（先在面板里點(diǎn)擊點(diǎn)，右鍵出現(xiàn)所需填充的輪廓，鼠標(biāo)移出面板填充）
總結(jié)
以上所述是小編給大家介紹的JAVA實(shí)現(xiàn)掃描線算法,希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺(jué)得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！
相關(guān)文章
這篇文章主要介紹了Java設(shè)計(jì)模式中的裝飾者模式，裝飾者模式即Decorator?Pattern，裝飾模式是在不必改變?cè)愇募褪褂美^承的情況下，動(dòng)態(tài)地?cái)U(kuò)展一個(gè)對(duì)象的功能，裝飾模式又名包裝模式。裝飾器模式以對(duì)客戶端透明的方式拓展對(duì)象的功能，是繼承關(guān)系的一種替代方案2022-07-07
這篇文章主要介紹了Messges Queue消息隊(duì)列詳解,消息隊(duì)列一般簡(jiǎn)稱為 MQ,是指利用高效可靠的消息傳遞機(jī)制進(jìn)行與平臺(tái)無(wú)關(guān)的數(shù)據(jù)交流,并基于數(shù)據(jù)通信來(lái)進(jìn)行分布式系統(tǒng)的集成,是在消息的傳輸過(guò)程中保存消息的容器,需要的朋友可以參考下2023-07-07
springboot項(xiàng)目使用SchedulingConfigurer實(shí)現(xiàn)多個(gè)定時(shí)任務(wù)的案例代碼
這篇文章主要介紹了springboot項(xiàng)目使用SchedulingConfigurer實(shí)現(xiàn)多個(gè)定時(shí)任務(wù),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-01-01
spring boot啟動(dòng)加載數(shù)據(jù)原理分析
實(shí)際應(yīng)用中，我們會(huì)有在項(xiàng)目服務(wù)啟動(dòng)的時(shí)候就去加載一些數(shù)據(jù)或做一些事情這樣的需求。這時(shí)spring Boot 為我們提供了一個(gè)方法，通過(guò)實(shí)現(xiàn)接口 CommandLineRunner 來(lái)實(shí)現(xiàn)。下面給大家詳細(xì)介紹下，需要的的朋友參考下吧2017-04-04
spring boot validation參數(shù)校驗(yàn)實(shí)例分析
這篇文章主要介紹了spring boot validation參數(shù)校驗(yàn),結(jié)合實(shí)例形式分析了spring boot validation進(jìn)行數(shù)據(jù)有效性驗(yàn)證的相關(guān)操作技巧,需要的朋友可以參考下2019-11-11
Struts2之Action接收請(qǐng)求參數(shù)和攔截器詳解
這篇文章主要介紹了Struts2之Action接收請(qǐng)求參數(shù)和攔截器詳解，非常具有實(shí)用價(jià)值，需要的朋友可以參考下2017-05-05
在程序開(kāi)發(fā)的過(guò)程之中一共會(huì)存在有三種程序邏輯：順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，對(duì)于之前所編寫的代碼大部分都是順序結(jié)構(gòu)的定義，即：所有的程序?qū)凑斩x的代碼順序依次執(zhí)行2021-11-11
Java日常練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)(40)
下面小編就為大家?guī)?lái)一篇Java基礎(chǔ)的幾道練習(xí)題(分享)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧，希望可以幫到你2021-07-07
SpringMVC整合SSM實(shí)現(xiàn)表現(xiàn)層數(shù)據(jù)封裝詳解
這篇文章主要介紹了SpringMVC整合SSM實(shí)現(xiàn)表現(xiàn)層數(shù)據(jù)封裝，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-10-10
這篇文章主要為大家詳細(xì)介紹了微信跳一跳輔助的Java代碼實(shí)現(xiàn)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01