• fullscreen
  • hilbert_2D_v1.pde
  • hilbert_2D_v2.pde
  • /*
      // thomas diewald
      // 
      // hilbert curve - quick and short example
      //
      // 16.11.2010
      // last updated: 16.11.2010 (thomas)
    */
    
    int levels = 4; // recursion depth
    
    void setup(){
      size(600,600);
    }
    
    
    
    void draw(){
      levels = mouseX/95;
    
      noStroke(); fill(255, 10); 
      rect(0,0, width, height);
    
      Vector c[] = hilbert(  new Vector(width/2, height/2, 0) , 300.0,    levels,      0, 1, 2, 3); // hilbert(center, side-length, recursion depth, start-indices)
      
      strokeWeight(width/95-levels); stroke(map(mouseX, 0, width, 0, 255), map(mouseY, 0, height, 0, 100), 50);
      for(int i = 0; i < c.length-1; i++)
        line(c[i].x, c[i].y, c[i+1].x, c[i+1].y);
    }
    
    
    
    
    
    Vector[] hilbert( Vector c_,  float side,   int iterations,      int index_a, int index_b, int index_c, int index_d ){ 
      Vector c[] = new Vector[4];
      c[index_a] = new Vector(  c_.x - side/2,   c_.y - side/2, 0  );
      c[index_b] = new Vector(  c_.x + side/2,   c_.y - side/2, 0  );
      c[index_c] = new Vector(  c_.x + side/2,   c_.y + side/2, 0  );
      c[index_d] = new Vector(  c_.x - side/2,   c_.y + side/2, 0  );
    
      if( --iterations >= 0) {
        Vector tmp[] = new Vector[0];
        tmp = (Vector[]) concat(tmp, hilbert ( c[0],  side/2,   iterations,    index_a, index_d, index_c, index_b  ));
        tmp = (Vector[]) concat(tmp, hilbert ( c[1],  side/2,   iterations,    index_a, index_b, index_c, index_d  ));
        tmp = (Vector[]) concat(tmp, hilbert ( c[2],  side/2,   iterations,    index_a, index_b, index_c, index_d  ));
        tmp = (Vector[]) concat(tmp, hilbert ( c[3],  side/2,   iterations,    index_c, index_b, index_a, index_d  ));
        return tmp;
      }
      return c;
    }
    
    
    
    
    
    class Vector{
      float x, y, z;
      Vector( float x, float y, float  z){
        this.x = x; 
        this.y = y; 
        this.z = z; 
      }
    }
    
    //----------------------------------------------------------------------------
    //
    // author: (c) thomas diewald
    // date: 13.01.2012
    //
    // Processing:1.5.1
    // Renderer: P2D
    //
    // Hilbert Curve 2D, fast algorithm
    //
    //----------------------------------------------------------------------------
    
    import java.util.Locale;
    
    int DEPTH, SIZE;          // hilbert curve params
    int IDX;                  // coord index
    float[][] verts;          // curve-coords
    float[][] SXD, SYD;       // quad corners (precomputed for each depth)
    int[] SX = {-1,+1,+1,-1}; // corner directions for x
    int[] SY = {-1,-1,+1,+1}; // corner directions for y
    
    
    @Override
    public void setup() {
      size(512, 512, P2D);
    }
    
    
    @Override
    public void draw() {
      background(255);
      translate(width/2, height/2);
      hilbert2D();
      drawCurve(true, true, true);
      updateWindowTitle();
    }
    
    
    void hilbert2D(){
      SIZE  = width/2;
      DEPTH = (int) map(mouseX, 0, width, 0, 9.99f);
      // DEPTH = 11; 
      
      // create coords array
      int num_verts = (int)Math.pow(4,DEPTH);
      if( verts == null || num_verts != verts.length){
        verts = new float[num_verts][2];
      }
      
      // precompute quad corners for each depth
      SXD = new float[DEPTH][4];
      SYD = new float[DEPTH][4];
      float s = SIZE/2;
      for(int i = DEPTH-1; i >= 0; i--, s /= 2){
        for(int j = 0; j < 4; j++){
          SXD[i][j] = SX[j]*s; 
          SYD[i][j] = SY[j]*s;
        }
      }
    
      // create curve
      IDX = 0;
      hilbert2D(0, 0, DEPTH, 0, 1, 2, 3); 
    }
    
    /**
     * Hilbert Curve: generates 2D-Coordinates in a very fast way.
     * 
     * @param x  x-coord
     * @param y  y-coord
     * @param d  depth
     * @param A  corner index A
     * @param B  corner index B
     * @param C  corner index C
     * @param D  corner index D
     */
    final void hilbert2D(float x, float y, int d, int A, int B, int C, int D) {
      if (d-- == 0)  {
        verts[IDX][0] = x;
        verts[IDX][1] = y;
        IDX++;
      } else {
        final float[] X = SXD[d], Y = SYD[d];  
        hilbert2D(x + X[A], y + Y[A], d, A, D, C, B); 
        hilbert2D(x + X[B], y + Y[B], d, A, B, C, D); 
        hilbert2D(x + X[C], y + Y[C], d, A, B, C, D); 
        hilbert2D(x + X[D], y + Y[D], d, C, B, A, D); 
      }
    }
    
    
    
    void drawCurve(boolean quads, boolean curve, boolean vertices){
      colorMode(HSB, verts.length-1, 100, 100);
      rectMode(CENTER);
      
      float s = SIZE/(float)Math.pow(2, DEPTH);
      
      if(quads){
        float col = 0;
        noStroke();
        float size = s*2;
        for( float[] v : verts) {
          fill(col++, 100,100);
          rect(v[0],v[1], size, size);
        }
      }
      
      if( curve && DEPTH <= 8){
        stroke(0);
        strokeWeight(1);
        float[] a = verts[0];
        for(int i = 1; i < verts.length; i++){
          line(a[0],a[1], (a = verts[i])[0], a[1]);
        }
      }
      
      if( vertices && DEPTH <= 5) {
        noStroke();
        fill(0);
        float size = s*0.3f;
        for( float[] v : verts) {
          rect(v[0]+1,v[1]+1, size, size);
        }
      }
      colorMode(RGB, 255, 255, 255);
    }
    
    
    
    
    void updateWindowTitle(){
      if( online ) 
        return;
      String txt_title = "Hilbert Curve 2D";
      String txt_framerate = String.format(Locale.ENGLISH, "fps %6.2f", frameRate);
      String txt_depth = String.format(Locale.ENGLISH, "depth %2d", DEPTH);
      String txt_num_verts = String.format(Locale.ENGLISH, "verts %3d", verts.length);
      txt_title += " | " + txt_depth;
      txt_title += " | " + txt_num_verts;
      txt_title += " | " + txt_framerate;
      frame.setTitle(txt_title);
    }
    
    
    public void keyPressed(){
      if( key == ESC && online) key = 0;
    }
    public void keyReleased(){
      if (key == 's' && !online ){
        String filename = "screenshot/diewald_hilbertcurve2D.png";
        save(filename);
        System.out.println("saved image: "+filename);
      }
    }
    
    
    

    code

    tweaks (0)

    about this sketch

    This sketch is running as Java applet, exported from Processing.

    license

    advertisement

    Thomas Diewald

    Hilbert Curve 2D

    Add to Faves Me Likey@! 5
    You must login/register to add this sketch to your favorites.

    This applet draws the hilbert-curve (2D).

    My main focus was on making the code very short and simple, and so the actual hilbert-function is really just view lines.



    http://thomasdiewald.com/blog/?p=561


    UPDATES
    13.01.2013: improved algorithm

    You need to login/register to comment.