Updated 2012-01-06 13:09:15 by RLE

MS: This is a version of Recursive curves that avoids floating point operations:

  • as all segments drawn have one of two lengths, these lengths are precomputed, as well as the depth at which a segment is drawn. The depth is hence kept in an integer.
  • as all angles are multiples of $pi/4, the angle is kept by the integer number of $pi/4 rotations
  • the angle-dependent values are precomputed in a table, for the 8 possible values of ($angle%8)

Additional optimisations:

  • the second recursion is tail-optimised using while
  • avoiding variable accesses by reusing returns of set and incr
  • calling lappend with single element to append (bytecompiled)

This does not make for particularly readable code :(

Note that this is a great example of senseless overoptimisation - the extra optimisation is not relevant here; there is not much further improvement from the original version as the app is I/O bound (drawing on the canvas). Even without drawing, the speedup is only about 20%.

Also note that this implementation makes additional assumptions:

  • the initial angle is 0
  • (dragon only) the initial value of s is 1

 proc main {} {
    pack [canvas .c -width 240 -height 280]
    set ::points {150 190}
 # ETFS configurability: uncomment what you want
    set t [time {ccurve .c 120 0 2}]
    #set t [time {dragon .c 160 0 1 2.4}]
    wm title . "[expr {[lindex $t 0]/1000000.}] sec"
    bind . <Return> {exec wish $argv0 &; exit}

# This just sets up the parameters for
# table-based ops; we assume here that 
# the initial angle is 0.
 proc setParams {len angle minlen} {
     global parList
     set maxDepth [expr {(1+floor(2*log($len/$minlen)/log(2)))}]
     set minlen [expr {$len/pow(sqrt(2),$maxDepth)}]
     set minlen0 [expr {$minlen/sqrt(2)}]
     set parList {}
     lappend parList [list  0.0        $minlen ];# 0
     lappend parList [list  $minlen0   $minlen0];# 1
     lappend parList [list  $minlen    0.0     ];# 2
     lappend parList [list  $minlen0  -$minlen0];# 3
     lappend parList [list  0.0       -$minlen ];# 4
     lappend parList [list -$minlen0  -$minlen0];# 5
     lappend parList [list -$minlen    0.0     ];# 6
     lappend parList [list -$minlen0   $minlen0];# 7

     return [expr {int($maxDepth)}]

# C curve drawer: assumes initial angle 0
 proc ccurve {w len angle minlen} {
     set maxDepth [setParams $len $angle $minlen]
     ccurveInt $w [incr maxDepth] $angle

 proc ccurveInt {w depth angle} {
    while {[incr depth -1]} {
        ccurveInt $w $depth [expr {[incr angle -1] + 2}] 
    plotline $w $angle

# Dragon curve drawer: assumes initial angle 0, initial s 1

 proc dragon {w len angle s minlen} {
     set maxDepth [setParams $len $angle $minlen]
     dragonInt $w [incr maxDepth] $angle $s

 proc dragonInt {w depth angle s} {
    while {[incr depth -1]} {
        if {$s == 1} {
            dragonInt $w $depth [expr {[incr angle -1] + 2}] 1
            set s -1
        } else {
            dragonInt $w $depth [expr {[incr angle  1] - 2}] 1
    plotline $w $angle

# Plot a line from last end point in specified direction and length

 proc plotline {w ang} {
     global ::points
     # Note that '$ang % 8' and '$ang & 7' give the same result
     foreach {xadd yadd} [lindex $::parList [expr {$ang & 7}]] {
         lappend points [expr {[lindex $points end-1]-$xadd}]
         lappend points [expr {[lindex $points end-1]-$yadd}]
     if {[llength $points]>200} {
         $w create line $points
         set points [lrange $points end-1 end]
# Let's go!