PVD: A Stable Implementation for Computing Voronoi Diagrams of Polygonal Pockets

摘要: Voronoi diagrams of pockets, i.e. polygons with holes, have a variety important applications but are particularly challenging to compute robustly. We report on an implementation simple algorithm which does not rely exact arithmetic achieve robustness; rather, it achieves its robustness through carefully engineered handling geometric predicates. Although we do give theoretical guarantees for or accuracy, the software has sustained extensive experimentation (on real and simulated data) day-to-day usage real-world data. The is shown experimentally compare favorably in running time prior methods.