JAVA如何实现扫描线算法

这篇文章给大家分享的是有关JAVA如何实现扫描线算法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

我们提供的服务有:网站制作、成都网站设计、微信公众号开发、网站优化、网站认证、山阳ssl等。为1000+企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的山阳网站制作公司

首先说一下,教科书上的扫描线算法确实是用c++很好实现,而且网上有很多源码,而java实现的基本没有(可能是我没看到),所以肖先生还是打算自己码(实验作业写这个而自己又个是写java的猿0.0)。

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

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

贴个图:

JAVA如何实现扫描线算法JAVA如何实现扫描线算法

实现的时候首先是构造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如何实现扫描线算法

JAVA如何实现扫描线算法

感谢各位的阅读!关于“JAVA如何实现扫描线算法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!


新闻名称:JAVA如何实现扫描线算法
分享URL:http://scyanting.com/article/jidsgg.html