So how do we go about calculating the Delaunay triangulation then? One way to do it is using the Bowyer-Watson algorithm. That is why if we have a ready Delaunay triangulation, we just need to find the edges of our Voronoi graph by forming an edge from each neighboring triangle’s circumcenter to its own circumcenter. Furthermore, every triangle circumcircle that we draw over actually corresponds to a vertex in the Voronoi graph. Let’s see why this is the case by comparing the Voronoi diagram at our first set of 40 points with its Delaunay triangulation side by side:īy closely comparing the two graphs visually, and imaging a circle around each triangle on the right, we can see a connection with the resulting Voronoi diagram on the left. We also denote the origin of each circumcircle with a green dot, as it’s an important detail that will help us with finding the Voronoi diagram. Here we have 10 points in black, and it’s easy to see that no other point lies within the drawn circumcircles. For example, here’s an illustration of one such structure: No triangle’s vertex should lie inside the circumcircle of other triangles in the formation.
Many algorithms will do the job however, the easiest one to understand actually requires us not to compute the Voronoi diagram directly, but rather to first compute the Delaunay triangulation of our set of points.īut what is the Delaunay triangulation exactly, and how does it help us with finding the Voronoi diagram? It’s a collection of triangles built using our original set of points as vertices. Now that we have a clear definition of what the Voronoi diagram is, we can set out to compute it.
0 kommentar(er)
