What is so special about Koch curve or Koch snowflake?
This is one of the oldest fractals which was found as an example of a continuous functions which is not differentiable.
The difference between Koch curve and Koch snowflake is that snowflake implies that curve is built among the lines of a equilateral triangle.
Further description here is focused only on drawing the curve itself.
Usually the algorithm of drawing this curve is implemented as a recursive process.
But instead of drawing it recursively we can perform much better by building the fractal first and then drawing it in any given interval.
The idea comes from the fact that curve repeats the same pattern infinite number of times until the process is stopped by reaching the maximum number of iterations.
So one can observe that there are only six different lines which are required to produce any iteration. Everything else can be made by scaling and rotating.
Now suppose we encode these lines by letters from a to f.
Note that there are only 6 patterns which replace each of the 6 segments.
Thus we can build encoded representation of the fractal as a string for any given iteration.
Building such string is an iterative process which simply replaces each “a” in initial string
with “abca”, “b” with “bdab”, etc.
The starting point which can be named as iteration 0 is a string which contains only “a”.
That’s it, we have only straight line before building the curve.
At some step after N iterations we get something like:
"abcabdab...".
Now we only have to draw the graph on a plane.
This process can be relatively light if we first calculate x and y offsets for each line from “a” to “f”.
Such offsets are computed only once for any given interval where our graph must be drawn.
Finally the code which builds and draws the curve would look something like:
//helper function which builds one iteration of the pattern
void KochCurve::BuildOnce(const std::string & init, std::string & result, int iterations)
{
std::string tmp = init;
while(iterations){
result.clear();
result.reserve(init.size() * 4);
for(std::string::const_iterator it = tmp.begin(), end = tmp.end(); it!=end; ++it)
{
switch(*it)
{
case('a'):
result.append("abca");
break;
case('b'):
result.append("bdab");
break;
case('c'):
result.append("caec");
break;
case('d'):
result.append("dfbd");
break;
case('e'):
result.append("ecfe");
break;
case('f'):
result.append("fedf");
break;
default:
assert(!"wrong symbol found in sequence");
}
}
--iterations;
tmp = result;
}
}
//draw pattern of specified iteration among the given line
void KochCurve::Draw(float x1, float y1, float x2, float y2, int iteration)
{
if (m_patterns.size() < (std::vector<std::string>::size_type) iteration)
{
Build(iteration);
}
const std::string & str = m_patterns[iteration - 1];
//rotation and scaling
float tmp1 = (x2-x1);
float tmp2 = (y2-y1);
float r = sqrt(tmp1 * tmp1 + tmp2 * tmp2);
float tmpsin = tmp2 / r;
float tmpcos = tmp1 / r;
float seg = r / (float) pow(3, iteration);
float seg_halve = seg / 2;
float seg_up = seg * 0.866025405f;
//calculate offset for each segment of the curve
float x_offsets[6] = {seg, seg_halve, seg_halve, -seg_halve, -seg_halve, -seg};
float y_offsets[6] = {0, seg_up, -seg_up, seg_up, -seg_up, 0};
float tmp = x_offsets[0];
x_offsets[0] = tmp * tmpcos - y_offsets[0] * tmpsin;
y_offsets[0] = tmp * tmpsin + y_offsets[0] * tmpcos;
tmp = x_offsets[1];
x_offsets[1] = tmp * tmpcos - y_offsets[1] * tmpsin;
y_offsets[1] = tmp * tmpsin + y_offsets[1] * tmpcos;
tmp = x_offsets[2];
x_offsets[2] = tmp * tmpcos - y_offsets[2] * tmpsin;
y_offsets[2] = tmp * tmpsin + y_offsets[2] * tmpcos;
tmp = x_offsets[3];
x_offsets[3] = tmp * tmpcos - y_offsets[3] * tmpsin;
y_offsets[3] = tmp * tmpsin + y_offsets[3] * tmpcos;
tmp = x_offsets[4];
x_offsets[4] = tmp * tmpcos - y_offsets[4] * tmpsin;
y_offsets[4] = tmp * tmpsin + y_offsets[4] * tmpcos;
tmp = x_offsets[5];
x_offsets[5] = tmp * tmpcos - y_offsets[5] * tmpsin;
y_offsets[5] = tmp * tmpsin + y_offsets[5] * tmpcos;
//forget about the interval
x2 = x1;
y2 = y1;
//walk through all segments and apply offsets
for(std::string::const_iterator it = str.begin(), end = str.end(); it!=end; ++it)
{
assert(*it >= 'a' && *it <= 'f');
x1 = x2;
y1 = y2;
x2+=x_offsets[*it - 'a'];
y2+=y_offsets[*it - 'a'];
glVertex2f(x1, y1);
glVertex2f(x2, y2);
}
}
There is Koch snowflake source code as a VS solution.
Still there is a lot of things to optimize.
Note that in sequences like “abca” last and first symbols are equal, std::strings are not as fast as preallocated C arrays, I used too many float variables for drawing… etc.