Efficient Voronoi diagram construction for planar freeform spiral curves

Jaewook Lee, Yong-Jun Kim, Myung-Soo Kim, Gershon Elber

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


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.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)131-142
عدد الصفحات12
دوريةComputer Aided Geometric Design
مستوى الصوت43
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - مارس 2016

All Science Journal Classification (ASJC) codes

  • !!Modeling and Simulation
  • !!Automotive Engineering
  • !!Aerospace Engineering
  • !!Computer Graphics and Computer-Aided Design


أدرس بدقة موضوعات البحث “Efficient Voronoi diagram construction for planar freeform spiral curves'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا