软件工程

本类阅读TOP10

·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八): CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
采用 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  
    核心算法:
    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);
    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);
    }
    }
    运行结果



    相关文章

    相关软件