L-systems fractals

[MyndFyre]

So I had some fun the other day with learning about L-systems, a method of generating fractal curves by defining grammar for representing the fractal's components.  For example:

* The Koch Curve
* The Dragon Curve

I write a program (see the screens?) that calculates a curve definition based on the grammar rules.  For example, Koch curve grammar is:
Variable F
F -> F+F-F-F+F
F means "Draw Forward", + means "Turn Left 90 degrees" and - means "Turn Right 90 degrees".
f(0) = F

So, f(1) = F+F-F-F+F
f(2) = (F+F-F-F+F)+(F+F-F-F+F)-(F+F-F-F+F)-(F+F-F-F+F)+(F+F-F-F+F)
Etc.

The Dragon curve is a bit cooler.  It is:
Variable X Y and F
X -> X+YF+
Y -> -FX-Y
F means "Draw Forward", - means "Turn Right 90 degrees", and - means "Turn Left 90 degrees".
X and Y don't correspond to anything to do with drawing; they simply govern the development of the curve.

My program is currently limited in that it has to do all of the following in each iteration:
1.) Calculate the grammar, which is an O(n) operation
2.) Calculate the next drawing operation for each letter in the grammar.  This is an O(kn) operation because there are conditional branches during each iteration, and because we have exponentially increased the size of the grammar.  There may be no drawing operation; it may simply determine the next direction to draw.
3.) Determine the boundaries set by the image.  This is done by looping through every line segment and performing four comparisons.
4.) Normalize each line segment.  This is an O(kn) operation because we now have more line segments than before.  Normalizing means that I need to recalculate the points of the line segment; consider that I may start at (0, 0) and go to (5, 0), then (5, -5), then (0, -5), then (-5, -5).  What do negative coordinates mean?  I also might need to invert the diagram if I'm talking about cartesian (x is positive to the right, y is positive upward) vs. screen coordinates (where y is positive downward).  This is a massive translation.
5.) Finally, I need to draw each line segment.  This is also an O(kn) operation.

I'm unhappy with the system's performance.  Among other things I plan to do is perform the rendering in a background thread; but that's a secondary concern.  If possible I think I could benefit in two ways:
1.) Accurately estimate the size of the graph and the offset of the origin after the grammar is calculated.
2.) Heuristically draw the line segments rather than procedurally draw them.  What I mean is that, rather than calculating each line segment and then drawing it, I would simply start somewhere and draw, eliminating steps 2-4.

Other additions I'd like to make:
1.) Define a way to procedurally define the functionality of a grammar.  Have primitive operations, allow the definition of different angles (other than 90), etc.  Example: Move/Draw, Left/Right/Forward/Back, and an angle component.
2.) Other stuff.

Any thoughts?