The Delaunay triangulation algorithm I’m using is called the Bowyer-Watson algorithm.
TERRAIN GENERATOR ALGORITHM GENERATOR
Then I use a random number generator to pick some random points. I pick a range to work in, say x = (0, 800) and y = (0, 400). If the Delaunay triangulation algorithm suffices, I encourage you to try your own implementation, as it isn’t too difficult or math intensive. It’s important to note that this algorithm still theoretically has floating-point issues if two points are randomly generated extremely close together.Īside: Also, for those in C++, I believe Boost recently added a comprehensive Voronoi library. My implementation only started slowing down in the thousands of points. However, since I only need at most a few dozen for tectonic plates, the simpler algorithm is fine. If I were using Voronoi cells as the tiles for a polygonal tile map, then the algorithmic runtime might be important.
I originally tried to implement this version, but it is far more complex and has a greater potential for floating-point arithmetic issues. This algorithm is where n is the number of points (or cells in the Voronoi diagram).Īside: For those interested, there is an algorithm called Fortune’s algorithm which uses a clever sweep-line approach to directly and efficiently generate Voronoi diagrams.
TERRAIN GENERATOR ALGORITHM CODE
That means if you find one, you can easily convert it into the other.Īlso, it turns out that while Voronoi diagrams are easier to understand (in my opinion) than Delaunay triangulations, Delaunay triangulations are much more intuitive to code (not my opinion, that’s just true). Why are we even looking at Delaunay triangulations? It turns out that Voronoi diagrams and Delaunay triangulations are dual graphs of each other. Tries to make the triangles as equilateral as possible (avoiding long skinny triangles).Connects the points in such a way that you get triangles.
Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation they tend to avoid sliver triangles.”Ī triangulation is a graph (a set of points and edges) such that no more edges can be added without crossing existing edges. Thank you WikipediaĪccording to Wikipedia: “A Delaunay triangulation … is a triangulation such that no point P is inside the circumcircle of any of any triangle. All points lie on the edge or outside of all circles. No matter how hard you try, you won’t find a point lying inside a circle.
Each intersection of edges is equidistant from at least 3 points. That is, all edges are equidistant from the nearest two cells. The edges (of the cells) in a Voronoi diagram delineate the “halfway boundaries” between each pair of points. Although my teachers always said it’s best to explain it in your own words, I’m pretty sure the best way to explain something is with someone else’s picture. Each cell consists of all the space closest to the given cell. A Voronoi diagram splits divides a space into cells based on a set of points, where each point gets a cell.
0 kommentar(er)
