Small bug in Koch's Snowflake Implementation

Question

So I'm programming a recursive program that is supposed to draw Koch's snowflake using OpenGL, and I've got the program basically working except one tiny issue. The deeper the recursion, the weirder 2 particular vertices get. Pictures at the bottom.

EDIT: I don't really care about the OpenGL aspect, I've got that part down. If you don't know OpenGL, all that the glVertex does is draw a line between the two vertices specified in the 2 method calls. Pretend its drawLine(v1,v2). Same difference.

I suspect that my method for finding points is to blame, but I can't find anything that looks incorrect.

I'm following the basically standard drawing method, here are the relevant code snips

(V is for vertex V1 is the bottom left corner, v2 is the bottom right corner, v3 is the top corner):

        double dir = Math.PI;
        recurse(V2,V1,n);

        dir=Math.PI/3;
        recurse(V1,V3,n);

        dir= (5./3.)* Math.PI ;
        recurse(V3,V2,n);

Recursive method:

public void recurse(Point2D v1, Point2D v2, int n){
    double newLength = v1.distance(v2)/3.;
    if(n == 0){
        gl.glVertex2d(v1.getX(),v1.getY());
        gl.glVertex2d(v2.getX(),v2.getY());

    }else{

        Point2D p1 = getPointViaRotation(v1, dir, newLength);
        recurse(v1,p1,n-1);
        dir+=(Math.PI/3.);

        Point2D p2 = getPointViaRotation(p1,dir,newLength);
        recurse(p1,p2,n-1);
        dir-=(Math.PI*(2./3.));

        Point2D p3 = getPointViaRotation(p2, dir, newLength);
        recurse(p2,p3,n-1);
        dir+=(Math.PI/3.);

        recurse(p3,v2,n-1);
    }

}

I really suspect my math is the problem, but this looks correct to me:

public static Point2D getPointViaRotation(Point2D p1, double rotation, double length){
    double xLength = length * Math.cos(rotation);
    double yLength = length * Math.sin(rotation);
    return new Point2D.Double(xLength + p1.getX(), yLength + p1.getY());
}

N = 0 (All is well):

N = 1 (Perhaps a little bendy, maybe)

N = 5 (WAT)

Eat

Without knowing the algorithm: This could be a double precision problem. – Licketysplit

Answer 1

So, it turns out I am the dumbest man alive.

Thanks everyone for trying, I appreciate the help.

This code is meant to handle an equilateral triangle, its very specific about that (You can tell by the angles).

I put in a triangle with the height equal to the base (not equilateral). When I fixed the input triangle, everything works great.

Eat

Answer 2

I can't see any obvious problem code-wise. I do however have a theory about what happens.

It seems like all points in the graph are based on the locations of the points that came before it. As such, any rounding errors that occurs during this process eventually start accumulating, eventually ending with it going haywire and being way off.

What I would do for starters is calculating the start and end points of each segment before recursing, as to limit the impact of the rounding errors of the inner calls.

Tameika

Well, the start end endpoints of an entire curve are provided by the user, they are the V1, V2, V3 (the initial triangle). It's impossible to calculate the inner points before hand, thats all the recursion does. – Eat

To alter my own suggestion a bit and be more specific: The way I would render this is to divide this into what "pieces" to draw. The initial level consists of three pieces, represented as lines if n=0. For n>0, each piece would instead do the following: Get start points A and end point B (presumably passed as parameters). Calculate points AB' and AB'' for the points 1/3 and 2/3 of the way in. Define A-AB' and AB''-B as two new pieces, then calculate the point AB* of the "spike" and define AB'-AB* and AB*-AB'' as new pieces. Recurse. Doing it this way would prevent large-scale rounding errors. – Tameika

Answer 3

One thing about Koch's snowflake is, that the algorithm will lead to a rounding issue one time (it is recursive and all rounding errors add up). The trick is, to keep it going as long as possible. There're three things you can do:

• If you want to get more detailed, the only way is to expand the possibilities of Double. You will need to use your own range of coordinates and transform them, every time you actually paint on the screen, to screen coordinates. Your own coordinates should zoom and show the last recursion step (the last triangle) in a coordination system of e.g. 100x100. Then calculate the three new triangles on top of that, transform into screen coordinates and paint.
• The line dir=Math.PI/3; divides by 3 instead of (double) 3. Add the . after the 3
• Make sure you use Point2D.Double anywhere. Your code should do so, but I would explicitely write it everywhere.

You won the game, when you still have a nice snowflake but get a Stackoverflow.

Thromboembolism

I had to do this little joke with Stackoverflow. I was forced to by my genes ;-) – Thromboembolism

The compiler will convert the 3 to 3.0; no action needed. – Superstition

Probably yes. these things always make me nervous, when I see them. The most important point is the first one. – Thromboembolism

If it's that big an issue, I'd recommend BigDecimal. Yet you persist in suggesting that the user add the decimal point, even though we agree that it's not necessary. – Superstition

I'm also usually paranoid about that, which is why I did it everywhere else in my code. Either way, I've done it now, and it didn't help :( – Eat

It was worth a try and helps focusing on the real helpful things. The third point is the one that should do it. It's a quite complicated thing to describe. Is it understandable? – Thromboembolism

The third point? The one about using Point2D.Double? I've tried that, it makes no difference, the compiler does that automatically. I think you meant the first point, but I'm not sure exactly what you mean by it. – Eat

Upps, after I edited the answer it is the first one now. About the own coordination system. – Thromboembolism