फॉर्च्यून के एल्गोरिदम

Question

में ब्रेकपॉइंट अभिसरण मैं वोरोनोई आरेखों की गणना के लिए फॉर्च्यून की स्वीपलाइन एल्गोरिदम लागू कर रहा हूं। मेरा प्राथमिक संदर्भ "कम्प्यूटेशनल जियोमेट्री: एल्गोरिदम एंड एप्लिकेशंस" डी बर्ग एट अल द्वारा है, और जब विषय का कवरेज बहुत स्पष्ट है, तो वे कई छोटे लेकिन महत्वपूर्ण विवरणों को पार करते हैं जिन्हें मुझे खुद को काम करने में परेशानी हो रही है। मैंने मदद के लिए वेब की खोज की है, लेकिन अन्य वेबसाइटें या तो पाठ्यपुस्तक की तुलना में एक उच्च अवलोकन प्रदान करती हैं, या पुस्तक द्वारा प्रदान की गई वही छद्म कोड प्रदान करती हैं।

मैं निर्धारित करने के लिए समुद्र तट रेखा पर आर्क्स की एक ट्रिपल द्वारा निर्धारित breakpoints की एक जोड़ी अभिमुख या diverges, ताकि आगामी चक्र की घटनाओं का पता लगाने के लिए कि क्या कोई तरीका होना चाहिए। ऐसा लगता है कि निर्णय लेने के लिए मुझे वोरोनोई सेल किनारों के आकार के बारे में ज्ञान की आवश्यकता होगी कि फॉर्च्यून के एल्गोरिदम प्रगति के रूप में ब्रेकपॉइंट्स का पता लगाया गया है। उदाहरण के लिए, यदि मुझे ब्रेकपॉइंट द्वारा पता लगाए गए किनारे की ढलान मिल सकती है तो मैं गणना कर सकता हूं कि ब्रेकपॉइंट्स और उनकी संबंधित ढलानों द्वारा बनाई गई दो रेखाएं किस प्रकार गठित होती हैं, और यह तय करती हैं कि वे उस परिणाम के आधार पर अभिसरण करते हैं या नहीं। हालांकि, मुझे नहीं पता कि ढलानों पर जानकारी कैसे प्राप्त करें, केवल ब्रेकपॉइंट्स की वर्तमान स्थिति।

केवल जानकारी मैं के साथ काम करने के लिए है एक्स, तीन साइटों के y स्थान और है वर्तमान sweepline (मैं एक क्षैतिज sweepline उपयोग कर रहा हूँ) की y- निर्देशांक।

असल में, मेरे पास अभिसरण निर्धारित करने का एक विचार है। दो साइटों को देखते हुए, वे समुद्र तट के दो वर्गों के बीच ब्रेकपॉइंट को परिभाषित करते हैं, केवल स्वीप लाइन की वर्तमान स्थिति से ही नियंत्रित होता है। मैंने दो ब्रेकपॉइंट्स की स्थिति रिकॉर्ड करने के बारे में सोचा, अस्थायी रूप से स्वीप लाइन को थोड़ी सी मात्रा में आगे बढ़ाना, और अपनी नई स्थिति रिकॉर्ड करना। चूंकि एक सामान्य वोरोनोई आरेख में किनारों की वक्र नहीं होती है, यदि ब्रेकपॉइंट्स की नई जोड़ी के बीच की दूरी पुरानी जोड़ी के बीच की दूरी से कम है, तो ब्रेकपॉइंट्स अभिसरण होते हैं; अन्यथा, वे अलग हो जाते हैं। लेकिन यह खतरनाक दोनों लगता है (मुझे नहीं पता कि यह हमेशा काम करता है) और बदसूरत। निश्चित रूप से एक बेहतर तरीका होना चाहिए।

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

Answer 1

आपका स्वागत है ड्रेक। मैंने इसे जांचकर कार्यान्वित किया कि क्या ब्रेकपॉइंट्स भौतिक रूप से सर्कल सेंटर पर स्वीकार्य स्थिति की 'कल्पित' वृद्धि में अभिसरण करते हैं। यह वास्तव में खुद को जटिल बनाता है क्योंकि कुछ मामलों में सर्कल सेंटर स्वीपलाइन स्थिति पर लगभग या सटीक हो सकता है, इसलिए स्वीपलाइन वृद्धि को वर्तमान स्वीपलाइन स्थिति और आपके द्वारा अनुशंसित सर्कल सेंटर के बीच के अंतर के अनुपात के समान होना चाहिए।

कहते हैं:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (और हम नीचे की तरफ बढ़ रहे हैं, यानी घटती हुई दिशा में)।

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY)/10.0f (10.0f भाजक मनमाने ढंग से चुना जाता है)।

3. Check new breakpoint positions at new sweepline position।

4. Check distance to circle center।

5. If both distances are less than current distances, the breakpoints converge।

मैं जानता हूँ कि यह शायद बहुत महंगा है, जब से तुम ब्रेकप्वाइंट पदों से अधिक बार की गणना करने के लिए है, लेकिन मुझे विश्वास है कि यह सब संभव मामलों का ख्याल रखता है हूँ।

वैसे भी, मैं चल बिन्दु परिशुद्धता त्रुटि कहीं और एल्गोरिथ्म में साथ गंभीर मुद्दों की खोज कर रहा हूँ। निश्चित रूप से सीधा नहीं है जैसा कि मैंने शुरुआत में सोचा था।

Answer 2

तो यह बल्कि शर्मनाक है, लेकिन समस्या पर सोने के बाद उत्तर स्पष्ट लगता है। मैं उम्मीद कर रहा हूं कि भविष्य में छात्रों को मेरे जैसा ही प्रश्न पूछने में मदद करें।

Voronoi दो साइटों के बीच बढ़त लंबवत साइटों को जोड़ने (काल्पनिक) रेखा खंड दो भागों में बांटती। आप कनेक्टिंग लाइन सेगमेंट की ढलान के लंबवत ले कर किनारे की ढलान प्राप्त कर सकते हैं, और फिर दो किनारों पर एक लाइन चौराहे परीक्षण कर सकते हैं, लेकिन एक आसान तरीका भी है।

जब तक तीन साइटें not collinear होती हैं, तो किनारों को लंबवत रूप से साइट के बीच सेगमेंट को विभाजित करने वाले किनारों को उस सर्कल के स्पर्श भी होते हैं जिनके किनारे में सभी तीन साइटें होती हैं। इसलिए वोरोनोई साइटों के एक तिहाई द्वारा परिभाषित ब्रेकपॉइंट्स को अभिसरण किया जाता है यदि तीन साइटों द्वारा परिभाषित सर्कल का केंद्र मध्य साइट के सामने है, जहां "सामने" और "पीछे" समन्वय प्रणाली और स्वीपलाइन संरेखण पर निर्भर करता है चुन लिया।

मेरे मामले में, मेरे पास एक क्षैतिज स्वीपलाइन है कि मैं न्यूनतम वाई से अधिकतम वाई तक जा रहा हूं, इसलिए ब्रेकपॉइंट्स अभिसरण करते हैं यदि सर्कल के केंद्र का वाई-समन्वय मध्य साइट के वाई-समन्वय से अधिक है , और अन्यथा अलग हो जाओ।

संपादित करें: क्रिस्टियन डी अमाटो हक बताते हैं कि एल्गोरिथ्म ऊपर कुछ अभिसरण मामलों याद करते हैं। अंतिम एल्गोरिदम का उपयोग कर समाप्त हो गया है।बेशक, मुझे विश्वास नहीं है कि यह 100% सही है, लेकिन ऐसा लगता है कि मैंने उन सभी मामलों के लिए काम किया है जिन पर मैंने कोशिश की थी।

Given left, middle, right sites 
    if they are collinear, return false 
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right) 
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center) 

IsRightOfLine(start, end, point) 
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0 

Answer 3

साइटों चक्र के केंद्र के चारों ओर दक्षिणावर्त आदेश दिया रहे हैं, तो चाप converging है। यदि उन्हें सर्कल के केंद्र के चारों ओर घुमावदार आदेश दिया जाता है, तो चाप अलग हो रहा है। (या इसके विपरीत, आपके कार्यान्वयन के आधार पर)। सीडब्ल्यू या सीसीडब्ल्यू के लिए परीक्षण सर्कल के केंद्र को खोजने के लिए उपयोग किए जाने वाले कोड से बाहर आता है।

 Vector2 ba = b - a; 
     Vector2 ca = c - a;  
     float baLength = (ba.x * ba.x) + (ba.y * ba.y); 
     float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
     float denominator = 2f * (ba.x * ca.y - ba.y * ca.x); 
     if (denominator <= 0f) { // Equals 0 for colinear points. Less than zero if points are ccw and arc is diverging. 
      return false; // Don't use this circle event! 
     }; 
     d.x = a.x + (ca.y * baLength - ba.y * caLength)/denominator ; 
     d.y = a.y + (ba.x * caLength - ca.x * baLength)/denominator ;