Fortune algorithm का उपयोग करके Voronoi diagram बनाना

Voronoi diagram बनाना

• Voronoi diagram क्या है?

  • Voronoi diagram समतल को कई क्षेत्रों में विभाजित करने की एक विधि है, जिसका उपयोग मुख्य रूप से प्रक्रियात्मक रूप से maps generate करने में किया जाता है.
  • समतल पर 'sites' कहलाने वाले कई बिंदु चुने जाते हैं, और प्रत्येक site के अनुरूप क्षेत्र में वे सभी बिंदु शामिल होते हैं जो उस site के सबसे निकट होते हैं.
  • प्रत्येक क्षेत्र की सीमा उन बिंदुओं से बनी होती है जो दो sites से समान दूरी पर होते हैं. वह बिंदु जो तीन sites से समान दूरी पर हो, 'Voronoi vertex' कहलाता है.

• Fortune algorithm

  • Fortune algorithm एक sweep line का उपयोग करके diagram बनाने की विधि है, जो समतल पर बाएँ से दाएँ चलती है.
  • जब sweep line किसी site से मिलती है, तो उसके आसपास एक 'bubble' (parabolic arc) बनता है, और sweep line के दूर जाने पर bubble बड़ा होता जाता है.
  • जब दो sites के arcs टकराते हैं, तो उनका टकराव बिंदु cell की सीमा बन जाता है.
  • सभी सक्रिय bubbles की सीमाओं को मिलाकर बनी रेखा 'beachline' कहलाती है.

• शब्दावली

  • site: एक 2D बिंदु, जो Voronoi diagram का आकार निर्धारित करता है.
  • sweep line: क्षेत्र को पार करने वाली एक ऊर्ध्वाधर रेखा, जो event queue के प्रत्येक event को process करती है.
  • beachline: कई arcs से बनी रेखा, जिसमें events process होने पर arcs जोड़े या हटाए जाते हैं.
  • intersection: beachline के दो arcs के मिलने का बिंदु, जो संबंधित sites से समान दूरी पर होता है.
  • event queue: वह स्थान जहाँ site और circle events संग्रहीत होते हैं, और जो x-coordinate के आरोही क्रम में sort होता है.
  • site event: event queue के दो प्रकार के events में से एक, जिसे संबंधित site के coordinates से परिभाषित किया जाता है.
  • circle event: queue का दूसरा प्रकार, जो circle की परिधि पर स्थित तीन arcs से परिभाषित होता है.
  • Voronoi vertex: वह बिंदु जो तीन sites से समान दूरी पर होता है, और cell का कोना बनता है.
  • equidistant boundary: वह रेखा जो दो sites से समान दूरी पर होती है.
  • incomplete boundary: ऐसी रेखा जिसका एक सिरा एक स्थिर बिंदु होता है और दूसरा सिरा दो parabolic foci के intersection से परिभाषित होता है.

• parabola tangent

  • parabola की अवधारणा और गुण इस algorithm में बहुत महत्वपूर्ण हैं.
  • parabola को एक focus point और एक line (directrix) से परिभाषित किया जाता है.
  • यदि दो sites के foci सेट किए जाएँ और sweep line को directrix माना जाए, तो दो parabolas के intersection को खोजकर दो sites से समान दूरी वाली boundary line मिल सकती है.

• beachline पर वापस

  • beachline, sweep line के किसी दिए गए बिंदु पर सभी arcs की 'boundary' होती है.
  • प्रत्येक arc को किसी site के focus point से दर्शाया जा सकता है.
  • beachline को बिंदुओं की एक सरल sequence के रूप में व्यक्त किया जा सकता है.

• नई arc तब बनती है जब sweep line किसी नए site से मिलती है

  • beachline बिंदुओं की एक sequence होती है, और प्रत्येक बिंदु एक site और arc को दर्शाता है.
  • जब sweep line किसी नए site से मिलती है, तो एक नई arc बनती है और sequence में insert की जाती है.

• एक-दूसरे को काटती boundaries और circumcircle

  • जब तीन sites किसी circle की परिधि पर होते हैं, तो circle का केंद्र उन तीनों बिंदुओं से समान दूरी पर होता है.
  • circumcircle का केंद्र Voronoi vertex बन जाता है.

• incomplete boundary

  • incomplete boundary का एक सिरा एक स्थिर बिंदु होता है, और दूसरा सिरा दो arcs के intersection पर होता है.
  • जब दो incomplete boundaries टकराती हैं, तो एक Voronoi vertex बनता है, और incomplete boundaries half-edge में बदल जाती हैं.

• केवल counterclockwise circles ही circle events बनाते हैं

  • circle event तभी बनता है जब तीन arcs को counterclockwise क्रम में पढ़ा जाए.

• सारांश

  • यदि sites का एक set दिया गया हो, तो सभी site points को queue में 'site' events के रूप में डालें और x-value के आधार पर sort करें.
  • जब तक queue खाली न हो, अगला event queue से निकालकर process करें.
  • यदि वह site event हो, तो beachline में नई arc जोड़ें और incomplete boundaries बनाएँ.
  • यदि वह circle event हो, तो Voronoi vertex जोड़ें और beachline से arc हटा दें.