Procedural road generation ?

[Lowercase]

the algorithm i used come's from this page :

http://www.cse.yorku.ca/~aaw/Hang/qu...Algorithm.html

in pseudo code :

Input = a set S of n points
    Assume that there are at least 2 points in the input set S of points

QuickHull (S)
{
    // Find convex hull from the set S of n points

    Convex Hull := {}
    Find left and right most points, say A & B, and add A & B to convex hull
    Segment AB divides the remaining (n-2) points into 2 groups S1 and S2
        where S1 are points in S that are on the right side of the oriented line from A to B,
        and S2 are points in S that are on the right side of the oriented line from B to A
    FindHull (S1, A, B)
    FindHull (S2, B, A)
}

FindHull (Sk, P, Q)
{
    // Find points on convex hull from the set Sk of points
    // that are on the right side of the oriented line from P to Q

   If Sk has no point,
        then  return.
    From the given set of points in Sk, find farthest point, say C, from segment PQ
    Add point C to convex hull at the location between P and Q
    Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2
        where S0 are points inside triangle PCQ, S1are points on the right side of the oriented
        line from  P to C, and S2 are points on the right side of the oriented line from C to Q.
    FindHull(S1, P, C)
    FindHull(S2, C, Q)
}

Output = convex hull

the result is not convex

[chronozphere]

You should make a "step" function in your program so you can execute the algorithm step by step. I expirimented with that approach and it works pretty good when you are implementing algorithm's or developing them.

In your case, you might want to render some lines and debug info to your canvas, before the next "FindHull" call. You could make a "Draw" routine, which draws all points and lines (PQ) and is called at the end of the FindHull function. Then you could add a Sleep(1000) call, and run your app.

You will see your algorithm compute the convex hull, step by step. You could also let the user decide when to execute the next step (by pressing some key).

It can be hard to debug algo's like these, but with this debug trick, i'm sure it will be alot easier.

Good luck.

[Lowercase]

after a little nap here is the result of quickhull :



it seems to work fine now