सभी रेखाखंडों

Question

रेखा खंडों की एक सूची को देखते हुए की चौराहे अंक का पता लगाएं, सबसे आसान तरीका चौराहे अंक खोजने के लिए रेखा खंड सूची, जाँच करें कि क्या वे काटते हुए कर रहे हैं और प्रतिच्छेदन बिंदु रिकॉर्ड अगर वे करते हैं लूप करने के लिए है।

लेकिन इस विधि का रनटाइम O(n^2) है, जो बहुत अक्षम है। क्या कोई अन्य एल्गोरिदम है जो इस प्रक्रिया को तेज कर सकता है?

Answer 1

Bentley-Ottmann Algorithm जो भी आप खोज रहे हैं हो सकता है।