Fortune’s Algorithm से Voronoi Diagram बनाना

• Fortune’s Algorithm Voronoi Diagram को O(n log n) समय में बना सकता है, लेकिन इसे लागू करना कठिन है; इसलिए जब तक बड़े पैमाने के diagrams को बार-बार generate करने की जरूरत न हो, O(n²) implementation या कोई library ज्यादा व्यावहारिक है
• Voronoi Diagram कई site के आधार पर plane को सबसे नजदीकी क्षेत्रों में बांटता है, और boundaries उन points से बनती हैं जो दो sites से समान दूरी पर होते हैं
• algorithm बाएं से दाएं चलने वाली sweep line और parabolic arcs की front line, यानी beachline, को maintain करता है, और केवल site event व circle event को process करता है
• site event नया arc insert करके मौजूदा arc को divide करता है और incomplete edge बनाता है, जबकि circle event बीच वाले arc को हटाते हुए Voronoi Vertex और half edge को complete करता है
• practical implementation में event queue, beachline, incomplete edge map और DCEL को साथ संभालना पड़ता है; invalid circle events हटाना और बचे हुए edges को साफ करना complexity को काफी बढ़ा देता है

---

Implementation की कठिनाई और scope

• Fortune’s Algorithm Voronoi Diagram को O(n log n) समय में generate करने वाला algorithm है
• अगर मकसद real-world use है, तो सीधे implement करने के बजाय पहले required scale पर विचार करना बेहतर है
  • अगर हर सेकंड कई बड़े diagrams generate करने की जरूरत नहीं है, तो O(n²) implementation आसान विकल्प हो सकता है
  • और ज्यादा practical alternative मौजूदा library का उपयोग है
• algorithm का visual output दिलचस्प होता है, लेकिन implementation process कठिन और काफी frustrating हो सकता है

Voronoi Diagram का basic concept

• Voronoi Diagram plane को कई regions में बांटने का तरीका है, और procedural map generation में अक्सर इस्तेमाल होता है
• input के रूप में चुने गए points को site या seed कहा जाता है
• हर site से जुड़ा cell plane पर उन points का set है जो उस site के सबसे नजदीक होते हैं
• cells की boundary उन points से बनी होती है जो दो sites से समान दूरी पर होते हैं
• cells के edges जहां मिलते हैं, वह Voronoi Vertex तीन sites से समान दूरी वाला point होता है

sweep line, beachline, event

• Fortune’s Algorithm बाएं से दाएं move करने वाली vertical line, यानी sweep line, का इस्तेमाल करता है
• जब sweep line किसी site से मिलती है, तो उस site को focus मानकर parabolic arc बनता है, और sweep line दूर जाने पर arc बड़ा होता जाता है
• अलग-अलग sites के दो arcs जहां मिलते हैं, वह point दोनों sites से समान दूरी पर होता है, इसलिए cell boundary बनता है
• जब दो boundaries मिलती हैं, तो diagram का vertex बनता है
• active arcs की front line को beachline कहा जाता है
• actual implementation में sweep line को pixel-by-pixel move नहीं किया जाता; केवल calculable specific points यानी event process किए जाते हैं
  • site event: पहले से ज्ञात site coordinates से defined होता है, और process होने पर beachline में नया arc add होता है
  • circle event: beachline के तीन arcs से defined होता है, और process होने पर एक arc हटता है तथा Voronoi Vertex और half edge बनते हैं

parabola से boundary ढूंढना

• algorithm में parabola को सामान्य y = ax^2 + bx + c form के बजाय locus definition से handle किया जाता है
• parabola एक focus point और एक directrix से defined होता है
  • focus point site होता है
  • directrix sweep line होती है
• same sweep line को directrix के रूप में इस्तेमाल करने वाले दो parabolas का intersection दो sites से समान दूरी पर होता है
• इसलिए दो parabolas का intersection निकालने पर दो sites के बीच का equiedge मिल सकता है
• parabola का x coordinate calculate करने का pseudocode, और sweep line की position बदलने पर दो parabolas का intersection boundary के साथ कैसे move करता है, इसका example इस्तेमाल किया गया है

beachline representation और site event processing

• beachline का हर arc केवल संबंधित site के coordinates से represent किया जा सकता है
  • sweep line सभी arcs पर common रूप से लागू होती है
  • implementation में arc को अलग object नहीं, बल्कि 2D coordinate के रूप में handle किया जाता है
• beachline को simple points के order के रूप में represent किया जा सकता है
  • उदाहरण: [arc1, arc2], [arc1, arc2, arc3]
  • same site का arc beachline में कई बार appear हो सकता है
  • उदाहरण: [arc1, arc3, arc1, arc2]
• site event होने पर, नए site से बाईं ओर line खींचने पर beachline का जो arc मिलता है, उसे ढूंढा जाता है, और नया arc उस arc को split करता है
• नया site L अगर existing beachline [.., i, j, k, ..] के j को split करे, तो structure [.., i, j, L, j, k, ..] बन जाता है
• sites x-coordinate order में queue में जाते हैं, और process होने पर beachline व event candidates update होते हैं

circle event और circumcircle

• beachline के तीन arcs [.., i, j, k, ..] में जब दो boundaries मिलती हैं, तो बीच वाला arc j गायब हो जाता है
• उस समय तीन sites से गुजरने वाला circumcircle मौजूद होता है, और circle का center तीनों sites से समान दूरी पर होता है
• circumcircle का center Voronoi Vertex बनता है
• circle event को circle के right endpoint, यानी circle point, के आधार पर event queue में रखा जाता है
• अगर कोई नया site circle point तक पहुंचने से पहले circle के अंदर मिल जाए, तो existing circle event invalid हो जाता है
  • क्योंकि नया site बीच वाले arc को पहले split कर देता है, इसलिए तीन arcs का combination अब बना नहीं रहता
  • existing triple i, j, k गायब हो जाता है और i, j, L, L, j, k जैसे नए triples को check करना पड़ता है

incomplete edge और half edge

• incomplete edge ऐसी line है जिसका एक endpoint fixed है, लेकिन दूसरा endpoint दो parabolic arcs के intersection से defined होता है
• site event में नया arc insert होने पर दो incomplete edges बनते हैं
  • fixed point वह coordinate है जहां नया arc existing beachline से मिला था
  • अगर नया arc j existing arc i को split करे, तो [i, j], [j, i] intersections से संबंधित edges बनते हैं
• circle event में जब दो incomplete edges collide करते हैं, तो collision point Voronoi Vertex बनता है
• existing incomplete edge इस point पर half edge के रूप में complete हो जाता है, और नए adjacent हुए दो arcs के बीच नया incomplete edge बनता है

केवल counterclockwise circles ही circle event बनते हैं

• जब beachline में [i, j, k, j, i] हो, तो ijk और kji दोनों circle बना सकते हैं, लेकिन दोनों valid circle event नहीं होते
• middle arc तभी गायब होता है जब boundaries वास्तव में converge करने वाली दिशा में हों
• program में तीन points की orientation determinant से तय की जाती है
  • determinant negative हो तो counterclockwise direction है और circle event बनता है
  • determinant positive हो तो clockwise direction है और circle event नहीं बनता
  • determinant 0 हो तो तीनों points collinear हैं, इसलिए circle नहीं है

पूरा algorithm flow

• input sites को x-coordinate के आधार पर sort करके site event के रूप में queue में डाला जाता है
• queue खाली होने तक next event निकालकर process किया जाता है
• site event processing:
  • आगे बचे हुए circle events में से वे events हटाए जाते हैं जिनके circle के अंदर नया site आ जाता है
  • beachline में वह arc ढूंढा जाता है जिसे नया site split करेगा
  • नया arc insert करके existing arc को split किया जाता है
  • दो incomplete edges add किए जाते हैं
  • नए बने triples circle event बना सकते हैं या नहीं, यह check किया जाता है
• circle event processing:
  • circumcircle center को Voronoi Vertex के रूप में add किया जाता है
  • middle arc को beachline से हटाया जाता है
  • हटाए गए arc के कारण invalid होने वाले future circle events हटाए जाते हैं
  • नए adjacent हुए arcs के triples check करके circle event add किया जाता है
• queue खाली होने पर बचे हुए incomplete edges को diagram boundary तक extend किया जाता है, और boundary से मिलने वाली जगह पर Voronoi Vertex बनाया जाता है

Odin implementation के data structures

• example implementation C alternative language Odin में लिखा गया है
• पूरा code RedPenguin101/voronoi repository में है
• basic types:
  • V2: [2]int form वाला 2D point
  • PointPair: दो V2 का pair
  • Event: {site: bool, a, b, c: V2} struct
• Event का अर्थ type के अनुसार बदलता है
  • site event में a site coordinate होता है और b, c इस्तेमाल नहीं होते
  • circle event में a, b, c event बनाने वाले beachline के तीन arcs होते हैं
• Fortune struct यह state manage करता है
  • beachline: V2 array
  • queue: Event array
  • incomplete_edges: PointPair -> V2 map
  • vd: Voronoi Diagram store करने वाला DCEL

Implementation में छोड़े गए या simplify किए गए हिस्से

• beachline को vector से represent किया गया है, लेकिन efficiency बढ़ाने के लिए binary tree ज्यादा suitable है
• event queue conceptually priority queue है, लेकिन example implementation में इसे array में sorted insertion तरीके से handle किया गया है
• circle event invalidation future events को iterate करके check करने का तरीका अपनाता है, और इसमें faster method की जरूरत का TODO है
• clean_beachline_edges beachline के दोनों ends से unnecessary arcs काटने की procedure है
• implementation में same x-coordinate वाले sites, circle point और site के same होने, reference point collisions जैसी edge cases शामिल हैं
• queue खाली होने के बाद बचे हुए incomplete edges, twin के बिना half edges और vertices को clean up करने वाला final step केवल simple math processing के रूप में handle किया गया है

DCEL से Voronoi Diagram store करना

• Voronoi Diagram आमतौर पर Doubly Connected Edge List(DCEL) में store किया जाता है
• DCEL vertex और edge से बने cell-complex को आसानी से manipulate करने के लिए represent करने वाला data structure है
• यह edge-centric representation है, लेकिन vertex और face information भी साथ store करता है
• सामान्य edge directionless होता है, लेकिन DCEL में हर edge को दोनों directions के दो half edge के रूप में store किया जाता है
• Voronoi Diagram में DCEL में store होने वाला vertex site नहीं, बल्कि Voronoi Vertex होता है
• edge E का destination E.twin.origin से मिलता है, और right face E.twin.left से मिलता है

[GN⁺]

Hacker News की टिप्पणियां

• कुछ समय पहले मैंने ClojureScript में Fortune algorithm के चलते हुए process को animation के रूप में दिखाने वाला implementation बनाया था: https://voronoi.ajwerner.net/#/app-diagrams
  यह सचमुच एक खूबसूरत algorithm है
  हालांकि उस project के बाद मुझे Fortune algorithm से थोड़ी चिढ़ हो गई, क्योंकि इसकी floating-point numerical stability अच्छी नहीं है
  अगर points एक ही सीधी रेखा पर हों, या floating-point के हिसाब से लगभग सीधी रेखा पर हों, तो यह टूट सकता है
  अगर मुझे सही याद है, तो इस मामले में delaunator बेहतर है: https://github.com/mapbox/delaunator

  • animation अब तक देखे गए सबसे अच्छे animations में से है
    reference page पर “old” implementation का link दिख रहा है; जानना चाहूंगा कि मौजूदा animation version को भी open source के रूप में जारी करने की कोई संभावना है या नहीं

• कुछ साल पहले मैंने ऐसी 3D visualization बनाई थी: https://x.com/KangarooPhysics/status/1253336959755251716

• uBlock Origin के लिए मशहूर Raymond Hill का JavaScript implementation है: https://github.com/gorhill/Javascript-Voronoi
  यहां मैंने इसे थोड़ा बदलकर move करने लायक बनाया है: https://animations.adgent.com/voronoi.html

  • यह animation A Scanner Darkly(2006) की style की याद दिलाता है
    सोचता हूं कि क्या video को input के रूप में लेकर उसे Voronoi तरीके से दिखाने वाले algorithm में डाला जा सकता है
    उस point पर शायद वह strictly Voronoi diagram न रहे, लेकिन काफी शानदार दिखेगा

• D3.js में एक नया implementation है: https://github.com/d3/d3-delaunay
  उस page के नीचे इस्तेमाल किए गए sweep algorithm की explanation और JavaScript के अलावा दूसरी languages में implementations की list है
  पुराना d3-voronoi deprecated होने वाला है, लेकिन यहां देखा जा सकता है: https://github.com/d3/d3-voronoi

• अगर edges में दिलचस्पी नहीं है और बस हर point को अलग रंग से रंगना है, तो seed points से शुरू होने वाला flood fill variant इस्तेमाल किया जा सकता है
  pixel को stack में तभी डालें जब उस color की दूरी उस pixel पर पहले से लगे color से कम हो

  • 2D plane के हर vertex पर apex वाले, अलग-अलग रंगों के right circular cones से 3D scene बना दें, और axis को plane के perpendicular रखें
    apex के ऊपर से 2D orthographic projection में render करने पर z-buffer सबसे नजदीकी vertex का pixel सुरक्षित रखेगा
    shader से भी करने का तरीका होगा, लेकिन classic 3D cone demo समझने और implement करने में बहुत आसान है

• दिलचस्प है कि D3, Fortune algorithm से https://mapbox.github.io/delaunator/ पर चला गया
  वजह यह बताई गई है कि “Delaunay triangulation या Voronoi diagram बनाते समय यह d3-voronoi से 5~10 गुना तेज, numerically ज्यादा robust है, इसमें Canvas rendering built-in है, और यह Delaunay graph traversal तथा कई improvements देता है”

  • अगर D3 ऐसे effects के लिए delaunator को best मानता है, तो अब मेरी canvas library में इसे न जोड़ने का बहाना सिर्फ मेरी स्वाभाविक टालमटोल की आदत ही बचती है
    अभी tiles calculate करने वाला code दर्दनाक रूप से naive है
    नई discussion: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

• इस article की वजह से मैंने ढूंढा कि Steve आजकल कहां हैं
  मैं उन्हें कई दशक पहले जानता था

• संबंधित पढ़ने लायक पोस्ट: https://news.ycombinator.com/item?id=37998923 - Fortune algorithm से O(n log n) में Voronoi diagram और Delaunay triangulation बनाना (2020)
  पिछली पोस्ट और discussion में दूसरे algorithms के छोटे summaries भी हैं
  निजी तौर पर मुझे अभी भी Jump Flooding Algorithm सबसे ज्यादा पसंद है: https://en.wikipedia.org/wiki/Jump_flooding_algorithm