|
首页>电脑常识>算法技术> |
采用Java绘制递归Hilbert曲线 |
|
Visited times , Welcome to Data Mining Forum & Data Mining Expert & Data Mining Tools |
|
|
|
|
本文的算法思想参考了《ALGORITHMS+DATA STRUCTURES=PROGRAMS》P130-P137: TWO EXAMPLE OF RECURSIVE PROGRAMS.
《ALGORITHMS+DATA STRUCTURES=PROGRAMS》Niklaus Wirth 著 Prentice-Hall出版
问题描述 下图所示的是由D.Hilbert发明的Hilbert曲线。其中曲线Hi+1是由Hi递归而成的。当各个级别(Level)的曲线叠加在一起的时候，就形成了Hilbert曲线。例如下图的三个曲线叠加在一起形成3-level Hilbert 曲线。
递归Hilbert问题就是要寻找用递归算法绘制Hilbert的方法。
算法思想左上图所示的Hi+1是由四个1/2大小的Hi组成的。其中一些Hi进行了旋转，并且有3条线段对其进行了连接。H1可以理解为由4个空的H0组成，而H1的3条线段连接了这4个空的H0。
因此可以很自然的想到绘制Hi的函数由四部分组成，每部分都绘制一半大小和特定方向的Hi-1。
如果把4个部分分为A、B、C、D，而连接线用箭头表示则可得出以下递归方案： 数据挖掘实验室
如果单位长度的线段用h表示，则绘制A部分的代码可写为: |
public void A(int i)
{
if(i>0)
{
D(i-1); x=x-h; plot();
A(i-1); y=y+h; plot();
A(i-1); x=x+h; plot();
B(i-1);
}
}
数据挖掘交友 |
其中plot()函数从当前画笔位置到(x,y)处绘制一条直线，然后设置当前画笔位置到(x,y)
由于屏幕坐标系统的Y轴是由上向下生长的，对于上图向下的黄箭头应用增大y值表示，即y=y+h |
| 与此类似的还可写出B、C、D部分的代码（参照递归方案图示） |
算法设计 递归Hilbert算法按照Niklaus Wirth《Algorithms + Data Structures = Program》一书的介绍进行设计。plot和setplot模块分别完成从当前点到指定点画线和设置指定点为当前点的操作。A、B、C、D四个模块决定了画笔的轨迹，此外需要一个启动函数设置起始画笔位置，并进行指定层数的循环操作。整个曲线的绘制是由A、B、C、D和启动函数共同完成，可见同时修改这5个模块可改变曲线的形状，因此算法演示中的程序提供了两种曲线的绘制：Hilbert曲线和Sierpinski曲线。
整个程序的结构如下所示： | | | | | | |
| KnightTour.java |
|
核心算法:
|
 |
|
|
drawHirbert()
绘制Hirbert曲线的启动函数 |
|
|
|
|
|
|
|
|
A_Hirbert()、B_Hirbert()
C_Hirbert()、D_Hirbert()
绘制Hirbert曲线的递归模块 |
|
|
|
|
|
|
|
|
drawSierpinski() 数据挖掘研究院
绘制Sierpinski曲线的启动函数 |
|
|
|
|
|
|
|
|
A_Sierpinski()、B_Sierpinski()
C_Sierpinski()、D_Sierpinski()
绘制Sierpinski曲线的递归模块 |
|
|
|
| |
其他辅助模块:
|
|
|
|
行为响应函数itemStateChanged()
点击复选框时进行不同的操作响应 |
|
|
|
|
|
|
|
|
行为响应函数stateChanged() 数据挖掘交友
拖动速度滚动条时计算速度 |
|
|
|
|
|
算法实现 算法实现只列出了绘制Hirbert曲线的重要模块。
|
重要成员变量 |
int m_nX0, m_nY0; //画笔当前坐标
int m_nX1, m_nY1; //画笔目的坐标
int m_nHeight; //单位线段长度
数据挖掘交友 |
|
重要算法模块 |
public void drawHirbert()
{
recordAction("START: Hirbert Curves");//记录操作内容
int i=0;
int n=Integer.parseInt(m_txtLevel.getText());//得到用户输入的层数
Dimension dm = m_canvas.getBufferSize(); //得到缓冲画布的尺寸
m_nHeight=dm.height; //原始高度
int x0=m_nHeight/2; //初始化起始坐标
int y0=x0;
m_graphics.clearRect(0,0,dm.width,dm.height); //清空画布
m_graphics.setColor(Color.YELLOW);
do
{
recordAction("LOOP: i="+i+"...");
i=i+1; //从第一层开始循环至第n层
m_nHeight=m_nHeight/2;
x0=x0+(m_nHeight/2);
y0=y0-(m_nHeight/2);
m_nX1=x0;
m_nY1=y0;
setpolt(); //设置当前坐标为(m_nX1,m_nY1)
A_Hirbert(i); //进入递归
}while(i!=n);
recordAction("END: Hirbert Curves"); 数据挖掘研究院
}
public void A_Hirbert(int i)
{
recordAction("IN: A_Hirbert( "+i+" )");
if(i>0)
{
D_Hirbert(i-1);m_nX1=m_nX1-m_nHeight;plot();
A_Hirbert(i-1);m_nY1=m_nY1+m_nHeight;plot();
A_Hirbert(i-1);m_nX1=m_nX1+m_nHeight;plot();
B_Hirbert(i-1);
}
recordAction("OUT: A_Hirbert( "+i+" )");
} B_Hirbert、C_Hirbert、D_Hirbert模块略，详见上面的递归策略图和完整代码 数据挖掘论坛 |
完整代码
/*
* Canvas.java
*
* 作为画布
*
* 王悦 04-14-2022
*/
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
class Canvas extends Panel
{
Image buffer;
public void initBuffer()
{
Dimension dim = getSize();
buffer = createImage(dim.width, dim.height);
}
public Graphics getBufferGraphics()
{
return buffer.getGraphics();
} public Dimension getBufferSize()
{
int wd = buffer.getWidth(this);
int hi = buffer.getHeight(this);
return new Dimension(wd,hi);
} public void paint(Graphics g)
{
update(g);
} public void update(Graphics g)
{
Dimension bd = getBufferSize();
Dimension dim = getSize();
g.drawImage(buffer,dim.width/2-bd.width/2,dim.height/2-bd.height/2,this);
}
} /*
* @(#)Recursion.java
*
*
* 王悦 04-14-2002
*
*/
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.event.*; public class Recursion extends JApplet implements Runnable,ActionListener,ItemListener,ChangeListener 数据挖掘交友
{
int m_nX0, m_nY0; //画笔当前坐标
int m_nX1, m_nY1; //画笔目的坐标
int m_nHeight; //单位线段长度
private JButton m_btnRun;
private JButton m_btnStop;
private ButtonGroup m_bg;
private JRadioButton m_rdoHirbert;
private JRadioButton m_rdoSierpinski;
private JCheckBox m_chkRecordActions;
private JLabel m_lblTitle;
private JLabel m_lblCurves;
private JLabel m_lblSpeed1;
private JLabel m_lblSpeed2;
private JLabel m_lblLevel;
private List m_lstActions;
private JTextField m_txtLevel;
private JSlider m_sldSpeed;
private Thread m_thread;
private Canvas m_canvas;
private Graphics m_graphics;
private int m_nDelay;
private boolean m_bRecordActions;
public void init()
{
Container ct=getContentPane();
ct.setLayout(null);
m_lblTitle= new JLabel("Hirbert and Sierpinski Curves Demo");
m_lblTitle.setBounds(460,2,230, 25);
ct.add(m_lblTitle);
m_lblCurves= new JLabel("Curves:");
m_lblCurves.setBounds(460,30,46, 25);
ct.add(m_lblCurves);
m_rdoHirbert=new JRadioButton("Hirbert",true);
m_rdoHirbert.setBounds(516,31,60, 25);
ct.add(m_rdoHirbert);
m_rdoSierpinski=new JRadioButton("Sierpinski",false);
m_rdoSierpinski.setBounds(580,31,80, 25);
ct.add(m_rdoSierpinski);
m_bg=new ButtonGroup();
m_bg.add(m_rdoHirbert);
m_bg.add(m_rdoSierpinski);
m_lblSpeed1= new JLabel("Speed: Low");
m_lblSpeed1.setBounds(460,60,80, 25);
ct.add(m_lblSpeed1);
m_sldSpeed=new JSlider(Scrollbar.HORIZONTAL,0,600,500);
m_sldSpeed.setBounds(540,63,100, 16);
ct.add(m_sldSpeed);
m_sldSpeed.addChangeListener(this);
m_lblSpeed2= new JLabel("High");
m_lblSpeed2.setBounds(644,60,50, 25);
ct.add(m_lblSpeed2);
m_lblLevel= new JLabel("Curves Level:");
m_lblLevel.setBounds(460,90,100, 25);
ct.add(m_lblLevel);
m_txtLevel= new JTextField("4");
m_txtLevel.setBounds(560,94,40, 20);
ct.add(m_txtLevel);
m_btnRun= new JButton("Start");
m_btnRun.setBounds(606,93,70, 20);
m_btnRun.addActionListener(this);
ct.add(m_btnRun); 数据挖掘实验室
m_btnStop= new JButton("Stop");
m_btnStop.setBounds(606,93,70, 20);
m_btnStop.addActionListener(this);
ct.add(m_btnStop);
m_chkRecordActions= new JCheckBox("Enable Actions Recorder:");
m_chkRecordActions.setBounds(460,120,200, 20);
ct.add(m_chkRecordActions);
m_chkRecordActions.addItemListener(this);
m_lstActions=new List();
m_lstActions.setBounds(460,144,210,290);
ct.add(m_lstActions);
m_btnStop.setVisible(false);
m_canvas = new Canvas();
m_canvas.setBackground(Color.black);
m_canvas.setBounds(2,2,436,436);
ct.add(m_canvas);
validate();
m_canvas.initBuffer();
m_graphics=m_canvas.getBufferGraphics(); }
public void itemStateChanged(ItemEvent e)
{
if(m_chkRecordActions.isSelected())
{
m_bRecordActions=true;
}
else
{
m_bRecordActions=false;
}
}
public void stateChanged(ChangeEvent e)
{
m_nDelay=m_sldSpeed.getMaximum()-m_sldSpeed.getValue();
}
public void actionPerformed(ActionEvent event)
{
if (event.getSource()==m_btnRun) 数据挖掘实验室
{
m_thread = new Thread(this);
m_thread.start();
m_btnRun.setVisible(false);
m_btnStop.setVisible(true);
m_txtLevel.setEnabled(false);
m_rdoHirbert.setEnabled(false);
m_rdoSierpinski.setEnabled(false);
}
else if (event.getSource()==m_btnStop)
{
m_thread.stop();
m_btnRun.setVisible(true);
m_btnStop.setVisible(false);
m_txtLevel.setEnabled(true);
m_rdoHirbert.setEnabled(true);
m_rdoSierpinski.setEnabled(true);
}
}
public void setpolt()
{
m_nX0=m_nX1;
m_nY0=m_nY1;
}
public void plot()
{
m_graphics.drawLine(m_nX0, m_nY0, m_nX1,m_nY1);
m_nX0=m_nX1;
m_nY0=m_nY1;
m_canvas.repaint();
delay(); }
public void A_Hirbert(int i)
{
recordAction("IN: A_Hirbert( "+i+" )");
if(i>0)
{
D_Hirbert(i-1);m_nX1=m_nX1-m_nHeight;plot();
A_Hirbert(i-1);m_nY1=m_nY1+m_nHeight;plot();
A_Hirbert(i-1);m_nX1=m_nX1+m_nHeight;plot();
B_Hirbert(i-1);
}
recordAction("OUT: A_Hirbert( "+i+" )");
}
public void A_Sierpinski(int i) 数据挖掘工具
{
recordAction("IN: A_Sierpinski( "+i+" )");
if(i>0)
{ A_Sierpinski(i-1);m_nX1+=m_nHeight;m_nY1+=m_nHeight;plot();
B_Sierpinski(i-1);m_nX1=m_nX1+2*m_nHeight;plot();
D_Sierpinski(i-1);m_nX1+=m_nHeight;m_nY1-=m_nHeight;plot();
A_Sierpinski(i-1);
}
recordAction("OUT: A_Sierpinski( "+i+" )");
}
public void B_Hirbert(int i)
{
recordAction("IN: B_Hirbert( "+i+" )");
if(i>0)
{
C_Hirbert(i-1);m_nY1=m_nY1-m_nHeight;plot();
B_Hirbert(i-1);m_nX1=m_nX1+m_nHeight;plot();
B_Hirbert(i-1);m_nY1=m_nY1+m_nHeight;plot();
A_Hirbert(i-1);
}
recordAction("OUT: B_Hirbert( "+i+" )");
}
public void B_Sierpinski(int i)
{
recordAction("IN: B_Sierpinski( "+i+" )");
if(i>0)
{
B_Sierpinski(i-1);m_nX1-=m_nHeight;m_nY1+=m_nHeight;plot();
C_Sierpinski(i-1);m_nY1=m_nY1+2*m_nHeight;plot();
A_Sierpinski(i-1);m_nX1+=m_nHeight;m_nY1+=m_nHeight;plot();
B_Sierpinski(i-1);
}
recordAction("OUT: B_Sierpinski( "+i+" )");
}
public void C_Hirbert(int i) 数据挖掘实验室
{
recordAction("IN: C_Hirbert( "+i+" )");
if(i>0)
{
B_Hirbert(i-1);m_nX1=m_nX1+m_nHeight;plot();
C_Hirbert(i-1);m_nY1=m_nY1-m_nHeight;plot();
C_Hirbert(i-1);m_nX1=m_nX1-m_nHeight;plot();
D_Hirbert(i-1);
}
recordAction("OUT: C_Hirbert( "+i+" )");
}
public void C_Sierpinski(int i)
{
recordAction("IN: C_Sierpinski( "+i+" )");
if(i>0)
{
C_Sierpinski(i-1);m_nX1-=m_nHeight;m_nY1-=m_nHeight;plot();
D_Sierpinski(i-1);m_nX1=m_nX1-2*m_nHeight;plot();
B_Sierpinski(i-1);m_nX1-=m_nHeight;m_nY1+=m_nHeight;plot();
C_Sierpinski(i-1);
}
recordAction("OUT: C_Sierpinski( "+i+" )");
}
public void D_Hirbert(int i)
{
recordAction("IN: D_Hirbert( "+i+" )");
if(i>0)
{
A_Hirbert(i-1);m_nY1=m_nY1+m_nHeight;plot();
D_Hirbert(i-1);m_nX1=m_nX1-m_nHeight;plot();
D_Hirbert(i-1);m_nY1=m_nY1-m_nHeight;plot();
C_Hirbert(i-1);
}
recordAction("OUT: D_Hirbert( "+i+" )");
} public void D_Sierpinski(int i)
{
recordAction("IN: D_Sierpinski( "+i+" )"); 数据挖掘实验室
if(i>0)
{
D_Sierpinski(i-1);m_nX1+=m_nHeight;m_nY1-=m_nHeight;plot();
A_Sierpinski(i-1);m_nY1=m_nY1-2*m_nHeight;plot();
C_Sierpinski(i-1);m_nX1-=m_nHeight;m_nY1-=m_nHeight;plot();
D_Sierpinski(i-1);
}
recordAction("OUT: D_Sierpinski( "+i+" )");
}
public void run()
{
m_lstActions.removeAll();
if(m_rdoHirbert.isSelected())
drawHirbert();
else
drawSierpinski();
m_btnRun.setVisible(true);
m_btnStop.setVisible(false);
m_txtLevel.setEnabled(true);
m_rdoHirbert.setEnabled(true);
m_rdoSierpinski.setEnabled(true);
}
public void drawHirbert()
{
//略,见算法实现
}
public void drawSierpinski()
{
recordAction("START: Sierpinski Curves");
int i=0;
int n=Integer.parseInt(m_txtLevel.getText());
Dimension dm = m_canvas.getBufferSize();
m_nHeight=dm.height/4;
int x0=m_nHeight*2;
int y0=m_nHeight;
m_graphics.clearRect(0,0,dm.width,dm.height);
m_graphics.setColor(Color.RED);
do
{
recordAction("LOOP: i="+i+"..."); 数据挖掘实验室
i=i+1;
x0=x0-m_nHeight;
m_nHeight=m_nHeight/2;
y0=y0-m_nHeight;
m_nX1=x0;
m_nY1=y0;
setpolt();
A_Sierpinski(i);m_nX1+=m_nHeight;m_nY1+=m_nHeight;plot();
B_Sierpinski(i);m_nX1-=m_nHeight;m_nY1+=m_nHeight;plot();
C_Sierpinski(i);m_nX1-=m_nHeight;m_nY1-=m_nHeight;plot();
D_Sierpinski(i);m_nX1+=m_nHeight;m_nY1-=m_nHeight;plot();
}while(i!=n);
recordAction("END: Sierpinski Curves");
}
public void delay()
{
try
{
Thread.sleep(m_nDelay);
}
catch(InterruptedException e)
{
};
}
public void recordAction(String action)
{
if(m_bRecordActions)
m_lstActions.addItem(action);
}
}
运行结果
|
|
|
|
|
|
[数据挖掘专家]
[数据挖掘研究院]
[数据挖掘论坛]
[数据挖掘实验室]
|
上一篇：圣经中真的藏有密码吗?摘自台湾权威杂志《科学月刊》
下一篇：Java实现关键路径分析
|
|
|
|
