मैं वोरोनोई आरेख को अपने पॉइंट सेट और इसके डेल्यूने त्रिभुज को कैसे प्राप्त करूं?

Question

मैं ऐसे गेम पर काम कर रहा हूं जहां मैं प्रांतों का एक यादृच्छिक मानचित्र (एक ला जोखिम या कूटनीति) बना रहा हूं। उस मानचित्र को बनाने के लिए, मैं सबसे पहले सेमी-यादृच्छिक बिंदुओं की एक श्रृंखला उत्पन्न कर रहा हूं, फिर उन बिंदुओं के डेलाउने त्रिकोणों को समझ रहा हूं।

ऐसा करने के साथ, अब मैं प्रांत सीमाओं के लिए प्रारंभिक बिंदु के रूप में कार्य करने के लिए बिंदुओं का वोरोनोई आरेख तैयार करना चाहता हूं। इस बिंदु पर मेरा डेटा (कोई इरादा नहीं है) में अंक की मूल श्रृंखला और डेलाउन त्रिभुजों का संग्रह शामिल है।

मैंने वेब पर ऐसा करने के कई तरीके देखे हैं, लेकिन उनमें से अधिकतर डेलाउने व्युत्पन्न हुए हैं। मुझे ऐसा कुछ ढूंढना अच्छा लगेगा जिसे Delaunay में एकीकृत करने की आवश्यकता नहीं है, लेकिन अकेले डेटा के आधार पर काम कर सकते हैं। यह विफल होने के कारण, मैं इष्टतम गति के विपरीत, एक सापेक्ष ज्यामिति नौसिखिया के लिए समझदार कुछ ढूंढ रहा हूं। धन्यवाद!

Answer 1

Voronoi आरेख सिर्फ डेलॉनाय ट्राईऐन्ग्युलेशंस की दोहरी ग्राफ है उत्पन्न कर सकते हैं कर रहा हूँ।

• तो, Voronoi चित्र के किनारों डेलॉनाय ट्राईऐन्ग्युलेशंस के किनारों का सीधा समद्विभाजक साथ हैं, इसलिए उन पंक्तियों की गणना।
• फिर, आसन्न किनारों के चौराहे को ढूंढकर वोरोनोई आरेख के शिखर की गणना करें।
• अंत में, किनारों की गणना की जाने वाली रेखाओं के उप-समूह होते हैं जो संबंधित शीर्षकों के बीच स्थित होते हैं।

ध्यान दें कि सटीक कोड आंतरिक चित्रण पर निर्भर करता है जो आप दो आरेखों के लिए उपयोग कर रहे हैं।

Answer 2

मैं बहुत यकीन है कि 'त्रिकोण' http://www.cs.cmu.edu/~quake/triangle.html voronoi

Answer 3

वैसे कारण चीजें एक साथ बंधी हुई हैं क्योंकि डेलाउने त्रिकोण और वोरोनोई आरेख दोहरी संरचनाएं हैं। मतलब यह voronoi से delaunay और इसके विपरीत जाने के लिए कोई ब्रेनर नहीं है।

मतलब यह है कि यदि आपके पास वोरोनोई आरेख है, तो आपको केवल किनारों को साझा करने वाले बिंदुओं को जोड़ना होगा और आपके पास डेल्यूने त्रिकोण (और इसके विपरीत) होगा।

Answer 4

इष्टतम गति एक विचार नहीं है, तो निम्न छद्म कोड उत्पन्न एक Voronoi मुश्किल तरीके से आरेख होगा

for yloop = 0 to height-1 
    for xloop = 0 to width-1 

    // Generate maximal value 
    closest_distance = width * height 

    for point = 0 to number_of_points-1 
     // calls function to calc distance 
     point_distance = distance(point, xloop, yloop) 

     if point_distance < closest_distance 
     closest_point = point 
     end if 
    next 

    // place result in array of point types 
    points[xloop, yloop] = point 

    next 
next 

मान लें कि आप एक 'बिंदु' वर्ग या संरचना है अगर आप उन्हें यादृच्छिक रंग आवंटित तब आप आउटपुट प्रदर्शित करते समय परिचित voronoi पैटर्न देखेंगे।

Answer 5

आपके प्रत्येक डेलाउन त्रिभुज में वोरोनोई आरेख का एक बिंदु होता है।

आप प्रत्येक त्रिकोण के लिए तीन perpendicular bisectors के चौराहे को ढूंढकर इस बिंदु की गणना कर सकते हैं।

आपका वोरोनोई आरेख इस बिंदु के सेट को जोड़ देगा, प्रत्येक के निकटतम तीन पड़ोसियों के साथ। (प्रत्येक पड़ोसी Delaunay त्रिकोण का एक पक्ष साझा करता है)

किनारे के मामलों के करीब आने की योजना कैसे बनाते हैं?

Answer 6

इस धागे को अपने स्वयं के इसी तरह के प्रश्न के उत्तर के स्रोत के रूप में उपयोग करने का प्रयास करने के बाद, मैंने पाया कि फॉर्च्यून का एल्गोरिदम - संभवतः यह सबसे लोकप्रिय & है इसलिए अधिकांश दस्तावेज - समझने में सबसे आसान था।

The Wikipedia article on Fortune's algorithm सी, सी #, और जावास्क्रिप्ट में स्रोत कोड के नए लिंक रखता है। वे सभी शीर्ष पायदान थे और सुंदर उदाहरणों के साथ आए थे।