دانلود رایگان مقاله ساخت دیاگرام ورونوی کارآمد برای منحنی اسپیرال دووجهی

Abstract

We present a real-time algorithm for computing the Voronoi diagram of planar freeform piecewise-spiral curves. The efficiency and robustness of our algorithm is based on a simple topological structure of Voronoi cells for spirals, which also enables us a direct construction of Voronoi structure without relying on intermediate polygonal or biarc approximations to the given planar curves. Using a Möbius transformation, we provide an efficient search for maximal disks. The correct topology of Voronoi diagram is computed by sampling maximal disks systematically, which entails subdividing spirals until each belongs to a pair/triple of spirals under a certain matching condition. The matching pairs and triples serve as the basic building blocks for bisectors and bifurcations, and their connectivity implies the Voronoi structure. We demonstrate a real-time performance of our algorithm using experimental results including the medial axis computation for planar regions under deformation with non-trivial self-intersections and the Voronoi diagram construction for disconnected planar freeform curves.

7. Conclusion

We have presented an efficient and robust algorithm for computing the Voronoi diagram of planar freeform curves and the medial axis of planar regions bounded by freeform curves. Monotone spiral segmentation of the input freeform curves and the maximal disks computed at the spiral endpoints greatly simplified the Voronoi cell construction algorithm for each spiral. The efficiency and numerical stability of the proposed approach will be useful in many 2D shape processing applications that are based on the medial axis structure such as the recent work of Zhu et al. (2014). In the future work, we plan to extend the Voronoi cell construction of Hanniel and Elber (2009) for planes, spheres, and cylinders to the general Voronoi cell construction for arbitrary freeform surfaces.