Procedural road generation ?

[Lowercase]

I need to practise a little more... here is my result for delaunay's algorithm.


Edit : I found my problem, my formula to compute the center of each triangles is wrong

that's a little better now

[chronozphere]

Ah looking good.

Are you using a sweepline approach now, or something else? I'm very interested in this stuff, and i would like to know more about your implementation and progress.

I still see one little glitch in your second image. One edge is missing (check the middle top of the image). And i see that your polygon is not convex. There are alot of caves who's vertices could be connected to form new triangles. This is no immediate problem, but i still like to know more about your implementation so i might be able to help you with that.

Few day's ago, i implemented delaunay triangulation using the "incremental" approach. Check this page:

http://www.codeguru.com/cpp/cpp/algo...icle.php/c8901

I would like to know about other methods. I know there is a "Divide and conquer" method and maybe a sweepline method. Check the wikipedia page on delaunay triangulation.

[Lowercase]

That's great !

I have a better result now !



Thanks for the source, if only i was able to read a little much better C, it would be great.

I will be away for a couple of days, so I won't update until next week..

[chronozphere]

Hi..

It's not about the C source. It's about the little piece of pseudo-code on that page. It gives you an idea how the algorithm works. I implemented incremental delaunay just with that pseudocode.

Good luck.

[Lowercase]

here's another try..

[NecroDOME]

Looks nice. Looking forward to see more results.

[Lowercase]

I still have problems computing a convex hull, so i'm trying to implement quick hull algorithm.

i think i have some problems with precision.

here's a screenshot :

[Lowercase]

I still have problems computing a convex hull, so i'm trying to implement quick hull algorithm.

i think i have some problems with precision.

here's a screenshot :

[/url]

[chronozphere]

I've found this page on convex hulls:

http://geometryalgorithms.com/Archiv...rithm_0109.htm

There is a nice list of algorithm's listed, and some of them are explained. Hope this helps.

[michalis]

You can take a look at my old implementation of the Jarvis algorithm for convex hull. For description of Jarvis algorithm see e.g. http://en.wikipedia.org/wiki/Gift_wrapping_algorithm, it's probably the simplest and still quite good in many situations convex hull algorithm.