बेंटले-ओटमैन एल्गोरिदम का सामान्यीकरण

Question

बेंटले-ओटमैन एल्गोरिदम का उपयोग लाइनों की सूची के चौराहे बिंदु को निर्धारित करने के लिए किया जाता है।

एल्गोरिथ्म है कि रेखा क्षेत्रों खड़ी नहीं कर रहे हैं मानता है कि लाइन खंड अंतिमबिंदुओं अन्य रेखा खंड पर झूठ नहीं है कि क्रॉसिंग केवल द्वारा गठित कर रहे हैं, हालांकि यहाँ उल्लेख किया in Wiki, कुछ कमियां हैं दो लाइन सेगमेंट, और कि कोई भी दो ईवेंट पॉइंट समान एक्स-समन्वय नहीं है। हालांकि, इन सामान्य स्थिति अनुमान लाइन सेगमेंट चौराहे के अधिकांश अनुप्रयोगों के लिए उचित नहीं हैं।

मेरा प्रश्न यह है कि इस एल्गोरिदम का एक सामान्यीकरण उपरोक्त कठिनाइयों को दूर/दूर कर सकता है?

Answer 1

विकिपीडिया लेख आप से जुड़ा हुआ handling these special positions पर एक अनुभाग है, जो बुनियादी एल्गोरिथ्म के लिए इन संशोधनों का सुझाव दिया गया है:

• परंपरा के मुताबिक, एक बिंदु पर खड़ी यह ऊपर एक बिंदु के "छोड़" है; इस प्रकार एक लंबवत रेखा का "बायां" अंतराल निचला एंडपॉइंट है।
• घटनाओं में दो या अधिक लाइनों के क्रॉसिंग शामिल हो सकते हैं।
• जब कोई ईवेंट पॉइंट पहुंच जाता है, तो इसकी घटना सेगमेंट स्वीप लाइन में को उलट दिया जाना चाहिए (केवल दोहराया नहीं जा सकता है, क्योंकि दो से अधिक हो सकते हैं)।
• के बाद एक पार नियंत्रित किया जाता है, वहाँ दो से अधिक वर्ष घटना दो से अधिक नई घटना अंक हटा दिया जाना चाहिए अंक या सम्मिलित करने के लिए हो सकता है।

Answer 2

स्कंथक here: द्वारा प्रस्तावित एल्गोरिदम में ये संशोधन हैं।

एल्गोरिदम निम्नानुसार प्राप्त होता है: यह सभी प्रारंभिक और इनपुट सेगमेंट के अंत बिंदुओं के लिए ईवेंट बनाता है। यह   फिर क्रमबद्ध क्रम में सभी घटनाओं को संभालता है।
  प्रत्येक घटना के लिए, यह जुड़े सूची एल उस बिंदु और फाई एनडीएस पर शुरू खंडों के को हासिल करेगा और खोज पेड़ में सभी खंडों कि वर्तमान घटना बिंदु एक दूसरे को काटना निकाल देता है। यह   उन सभी खंडों को उस बिंदु पर चौराहे के रूप में रिपोर्ट करता है। यह   तब वर्तमान घटना के बाद थोड़ा सा होने के लिए FL ag को बदलकर तुलना फ़ंक्शन के क्रम को स्विच करता है। यह   सब पहले से खंडों कि (क्योंकि वे इस बात वैसे भी पर संरचना से हटाया जा करने के लिए है) वर्तमान घटना बिंदु पर अपने अंतिम बिंदु की जरूरत नहीं है और इसके अलावा एल से खंडों को सम्मिलित हटाया reinserts (कि इस बिंदु से शुरू हो रहे हैं)। यह   नए चौराहे के लिए वर्तमान घटना बिंदु के ऊपर और नीचे शीर्ष और निचले पड़ोसियों की जांच करता है और उन्हें   किसी भी इवेंट पॉइंट के रूप में जोड़ता है।
  इस तरह एल्गोरिथ्म degeneracies के सभी प्रकार, खड़ी खंडों और ओवरलैप करने वाले सेगमेंट, के साथ ही उनके अंतिम बिंदुओं पर काटते हुए क्षेत्रों सहित के खिलाफ मजबूत है।

for all segments s do 
    Create events for the endpoints of s 
end for 
while event queue not empty do 
    Remove the smallest event point p from the queue 
    Let L be the set of segments that start at p 
    I ← all segments in the sweep line structure that contain p 
    remove I from sweep line structure 
    if |L| + |I| ≥ 2 then 
    Report intersections of L ∪ I 
    end if 
    C ← {s ∈ I | p is not endpoint of s} 
    Insert C in sweep line structure in reversed order 
    Check for new intersections among segments above and below p 
end while