As said before and before, I've spent some time learning an area called Computational Geometry. One of the algorithms I learned was how to make a Voronoi diagram. The algorithm I implemented suffered from floating point precision issues, so sometimes the Voronoi diagram lost some edges. The reason was that the algorithm was cutting lines to create the diagram, but the more the lines were cut, the worse the precision of the lines became (because of floating point precision issues) and in the end the algorithm removed lines it shouldn't have removed.
A better way to generate a Voronoi diagram is to use a Delaunay triangulation algorithm. This algorithm doesn't suffer from floating point precision issues and is easier to implement if you know how to implement the Delaunay triangulation algorithm. To create a Voronoi diagram from a Delaunay triangulation you need just 150 lines of code, while the older algorithm needed 600 lines of code.
This is the result. You can also see the Delaunay triangulation (the black lines).
One other area I struggled with last time I studied the area was how to cut triangles in the best way. You may think that there are many algorithms that can cut connected triangles in 2d space in a simple way, but not a single one can be found when searching on Google. The answers on Stack Overflow consists of solutions where you have cases. For example, if a line-segment of one triangle is intersecting two line-segments of the other triangle we want to cut, then we need to create 2 new triangles depending on which lines are intersecting, and the solution becomes more and more complicated.
Perhaps a more elegant way is to use what we used to create a Voronoi diagram: the Delaunay triangulation. But in this case we force the triangulation to include some triangles we want to cut from the triangulation, and we get a Constrained Delaunay triangulation, which looks like this:
You can also use the Constrained Delaunay triangulation if you for example want to make a navigation mesh for your game.
A better way to generate a Voronoi diagram is to use a Delaunay triangulation algorithm. This algorithm doesn't suffer from floating point precision issues and is easier to implement if you know how to implement the Delaunay triangulation algorithm. To create a Voronoi diagram from a Delaunay triangulation you need just 150 lines of code, while the older algorithm needed 600 lines of code.
This is the result. You can also see the Delaunay triangulation (the black lines).
One other area I struggled with last time I studied the area was how to cut triangles in the best way. You may think that there are many algorithms that can cut connected triangles in 2d space in a simple way, but not a single one can be found when searching on Google. The answers on Stack Overflow consists of solutions where you have cases. For example, if a line-segment of one triangle is intersecting two line-segments of the other triangle we want to cut, then we need to create 2 new triangles depending on which lines are intersecting, and the solution becomes more and more complicated.
Perhaps a more elegant way is to use what we used to create a Voronoi diagram: the Delaunay triangulation. But in this case we force the triangulation to include some triangles we want to cut from the triangulation, and we get a Constrained Delaunay triangulation, which looks like this:
You can also use the Constrained Delaunay triangulation if you for example want to make a navigation mesh for your game.
Comments
Post a Comment