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实现扫描线算法,希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对呐喊教程网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：notice#nhooo.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
基础教程
- HTML基础教程
- HTML5基础教程
- HTML参考手册
- SVG 教程
- CSS 教程
- CSS 参考手册
- CSS3教程
- Bootstrap3 教程
- Bootstrap4 教程
- Font Awesome图标
- JavaScript 教程
- JavaScript 参考手册
- jQuery 教程
- AJAX 教程
- JSON 教程
- AngularJS 教程
- ReactJS 教程
- NodeJS 教程
- Python 教程
- C++ 教程
- Golang 教程
- C 语言教程
- PHP 教程
- C# 教程
- LINQ 教程
- Lua 教程
- Ruby 教程
- Rust 教程
- Linux 教程
- R 语言教程
- Docker 教程
- Scala 教程
- MatLab 教程
- Erlang 教程
- Pandas教程
- Numpy教程
- Matplotlib教程
- Flask教程
- Java 教程
- SpringBoot 教程
- JDBC 教程
- JSP 教程
- Servlet 教程
- Maven 教程
- Spring 教程
- Django 教程
- Swift 教程
- Kotlin 教程
- SQL 教程
- MongoDB 教程
- SQLite 教程
- PostgreSQL 教程
- MySql 教程
- Redis 教程
- Elasticsearch 教程
猜你喜欢
- CentOS8.0 安装配置ftp服务器的实现方法
- Spring CGLlB动态代理实现过程解析
- 详解基于centos7搭建Nginx网站服务器（包含虚拟web主机的配置）
- vue2.x 通过后端接口代理,获取qq音乐api的数据示例
- Python集合基本概念与相关操作实例分析
- Spring基于ProxyFactoryBean创建AOP代理
- IDEA 连接数据库的实现方法
- MacOS下mysql 8.0.18 安装配置方法图文教程
- vue中更改数组中属性,在页面中不生效的解决方法
- python opencv将表格图片按照表格框线分割和识别
- python 使用pygame工具包实现贪吃蛇游戏(多彩版)
- python常见字符串处理函数与用法汇总
- 基于JavaScript实现单例模式
- vue解决使用$http获取数据时报错的问题
- 茶余饭后聊聊Vue3.0响应式数据那些事儿
- JAVA实现扫描线算法(超详细)
- java连接mysql底层封装详解
- vue请求服务器数据后绑定不上的解决方法
- 简单了解java中静态初始化块的执行顺序
- 详解使用JRebel插件实现SpringBoot应用代码热加载
- Java连接Mysql 8.0.18版本的方法详解
- 微信小程序发送订阅消息的方法(php 为例)
- JavaScript中new运算符的实现过程解析
- oracle实现动态查询前一天早八点到当天早八点的数据功能示例
- vue中的mescroll搜索运用及各种填坑处理