Reputation: 51
I'm seeking advice on the implementation of incremental updates on a bounded voronoi diagram. Specifically, I have an interactive application where users can drag the sites of a voronoi diagram and it updates in real time. I use the incremental Bowyer-Watson algorithm to first make changes in voronoi's dual Delaunay triangulation and then translate those changes to voronoi diagram updates. The entire sequence is fairly complex but works well for the most part. The problem is the boundary. Since my diagrams are bounded, they contain extra edges that represent the boundary. Furthermore, vertices and edges external to that boundary are pruned and no longer part of the diagram, and edges that intersect the boundary are altered to coincide with an artificial boundary vertex. These boundary-based updates break the translation of changes from the Delaunay triangulation to the voronoi diagram when dragging sites on or near the boundary. Wondering if anyone has come across this problem and what they've done to solve it.
Upvotes: 1
Views: 34