|
|
采用 Java 绘制递归Hilbert曲线 |
|
|
作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站 |
本文的算法思想参考了《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曲线的递归模块 |
 |
|
 |
| |
其他辅助模块:
|
 |
|
 |
Canvas.java extends Panel 用于绘图的缓冲区类 |
 |
|
 |
|
|
 |
|
 |
行为响应函数actionPerformed() 点击按钮时进行不同的操作响应 |
 |
|
 |
|
|
 |
|
 |
行为响应函数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); } }
运行结果

|
|
相关文章:相关软件: |
|