采用 Java 绘制递归Hilbert曲线

本文的算法思想参考了《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

核心算法:

plot()

从当前点到指定点画线

setpolt()

设置指定点为当前点

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

用于绘图的缓冲区类

初始化模块init()

设置画布缓冲区和显示各控件

行为响应函数actionPerformed()

点击按钮时进行不同的操作响应

行为响应函数itemStateChanged()

点击复选框时进行不同的操作响应

行为响应函数stateChanged()

拖动速度滚动条时计算速度

绘图线程run()

延时函数delay()

recordAction()

在列表中记录操作内容

算法实现算法实现只列出了绘制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);

{

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);

{

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);

}

} 运行结果