Multiple line segment intersection
कम्प्यूटेशनल ज्यामिति में, एकाधिक रेखा खंड प्रतिच्छेदन समस्या यूक्लिडियन तल में रेखा खंडों की एक सूची प्रदान करती है और पूछती है कि क्या उनमें से कोई दो प्रतिच्छेदन (क्रॉस) करते हैं। सरल एल्गोरिदम खंडों की प्रत्येक जोड़ी की जांच करते हैं। हालाँकि, यदि बड़ी संख्या में संभवतः प्रतिच्छेदन खंडों की जाँच की जानी है, तो यह तेजी से अक्षम हो जाता है क्योंकि खंडों के अधिकांश जोड़े एक विशिष्ट इनपुट अनुक्रम में एक दूसरे के करीब नहीं होते हैं। बड़ी संख्या में खंडों के लिए इस समस्या को हल करने का सबसे आम और अधिक कुशल तरीका एक स्वीप लाइन एल्गोरिथ्म का उपयोग करना है, जहां हम रेखा खंडों में एक रेखा के खिसकने की कल्पना करते हैं और हम ट्रैक करते हैं कि यह किस रेखा खंडों को प्रत्येक समय में एक गतिशील डेटा संरचना का उपयोग करके काटता है। शैमोस-होई एल्गोरिथ्म इस सिद्धांत को लाइन सेगमेंट इंटरसेक्शन डिटेक्शन समस्या को हल करने के लिए लागू करता है, जैसा कि ऊपर कहा गया है, यह निर्धारित करने के लिए कि लाइन सेगमेंट के एक सेट में एक इंटरसेक्शन है या नहीं; बेंटले-ऑटमैन एल्गोरिथ्म लॉगरिदमिक समय प्रति इंटरसेक्शन में सभी इंटरसेक्शन को सूचीबद्ध करने के लिए एक ही सिद्धांत से काम करता है। बेंटले-ऑटमैन एल्गोरिथ्म संदर्भ अध्याय 2: लाइन सेगमेंट इंटरसेक्शन, पीपी. 19-44 भी देखें। थॉमस एच. कॉर्मन, चार्ल्स ई. लीसरसन, रोनाल्ड एल. रिवेस्ट और क्लिफोर्ड स्टीन। एल्गोरिदम का परिचय, दूसरा संस्करण। एमआईटी प्रेस और मैकग्रा-हिल, 1990. धारा 33.2: यह निर्धारित करना कि क्या खंडों का कोई जोड़ा प्रतिच्छेद करता है। जे. एल. बेंटले और टी. ओटमैन., ज्यामितीय चौराहों की रिपोर्टिंग और गिनती के लिए एल्गोरिदम, आई. ई. ई. ई. ट्रांस। गणना करें। सी28 (1979), 643-647। बाहरी लिंक लाइनों और विमानों के इंटरसेक्शन एल्गोरिदम और डैन संडे रॉबर्ट प्लेस द्वारा नमूना कोड। व्याख्यान 4 टिप्पणियाँ। सेंट लुइस में वाशिंगटन विश्वविद्यालय, सी. एस. 506: कम्प्यूटेशनल ज्यामिति (कैश की गई प्रति)। सी. जी. ए. एल. में लाइन सेगमेंट इंटरसेक्शन, जेफ एरिकसन द्वारा कम्प्यूटेशनल ज्यामिति एल्गोरिदम लाइब्रेरी "लाइन सेगमेंट इंटरसेक्शन" व्याख्यान नोट्स। सी कोड के साथ लाइन-लाइन इंटरसेक्शन विधि नमूना डेरेल रेक्स फिनले ज्यामितीय एल्गोरिदम ज्यामितीय इंटरसेक्शन कम्प्यूटेशनल ज्यामिति