Multiple line segment intersection
கணக்கீட்டு வடிவவியலில், பல கோடு பிரிவு குறுக்குவெட்டு சிக்கல் யூக்ளிடியன் தளத்தில் உள்ள கோடு பிரிவுகளின் பட்டியலை வழங்குகிறது மற்றும் அவற்றில் ஏதேனும் இரண்டு வெட்டுகின்றனவா (குறுக்கு) என்று கேட்கிறது. எளிய வழிமுறைகள் ஒவ்வொரு ஜோடி பிரிவுகளையும் ஆராய்கின்றன. இருப்பினும், அதிக எண்ணிக்கையிலான குறுக்குவெட்டு பிரிவுகளை சரிபார்க்க வேண்டுமானால், இது பெருகிய முறையில் திறனற்றதாகிவிடும், ஏனெனில் பெரும்பாலான ஜோடி பிரிவுகள் ஒரு பொதுவான உள்ளீட்டு வரிசையில் ஒன்றுக்கொன்று நெருக்கமாக இல்லை. அதிக எண்ணிக்கையிலான பிரிவுகளுக்கு இந்த சிக்கலைத் தீர்ப்பதற்கான மிகவும் பொதுவான மற்றும் மிகவும் திறமையான வழி, ஒரு ஸ்வீப் லைன் வழிமுறையைப் பயன்படுத்துவதாகும், அங்கு ஒரு கோடு கோடு பிரிவுகளில் சறுக்குவதை நாம் கற்பனை செய்கிறோம், மேலும் ஒவ்வொரு கட்டத்திலும் அது எந்த கோடு பிரிவுகளை வெட்டுகிறது என்பதைக் கண்காணிக்கிறோம் பைனரி தேடல் மரங்களின் அடிப்படையில் ஒரு மாறும் தரவு அமைப்பு. ஷாமோஸ்-ஹோய் வழிமுறையானது, மேலே குறிப்பிட்டுள்ளபடி, கோடு பிரிவு குறுக்குவெட்டு கண்டறிதல் சிக்கலைத் தீர்க்க இந்தக் கொள்கையைப் பயன்படுத்துகிறது, ஒரு கோடு பிரிவுகளின் தொகுப்பு ஒரு குறுக்குவெட்டைக் கொண்டிருக்கிறதா இல்லையா என்பதைத் தீர்மானிக்க; பென்ட்லி-ஒட்மேன் வழிமுறை அனைத்து குறுக்குவெட்டுகளையும் ஒரு குறுக்குவெட்டுக்கு மடக்கை நேரத்தில் பட்டியலிட அதே கொள்கையால் செயல்படுகிறது. பென்ட்லி-ஒட்மேன் வழிமுறை குறிப்புகள் மேலும் வாசிப்பு அத்தியாயம் 2: கோடு பிரிவு குறுக்கீடு, pp. 19-44 ஐப் பார்க்கவும். தாமஸ் எச். கோர்மென், சார்லஸ் ஈ. லெய்சர்சன், ரொனால்ட் எல். ரிவெஸ்ட் மற்றும் கிளிஃபோர்ட் ஸ்டீன். வழிமுறைகளின் அறிமுகம், இரண்டாவது பதிப்பு. எம்ஐடி பிரஸ் மற்றும் மெக்ரா-ஹில், 1990. பிரிவு 33.2: ஏதேனும் ஒரு ஜோடி பிரிவுகள் வெட்டுகின்றனவா என்பதைத் தீர்மானித்தல், pp. 934-947. ஜே. எல். பென்ட்லி மற்றும் டி. Ottmann., வடிவியல் குறுக்குவெட்டுகளைப் புகாரளிப்பதற்கும் எண்ணுவதற்கும் வழிமுறைகள், IEEE டிரான்ஸ். கணக்கிடுங்கள். C28 (1979), 643-647. வெளிப்புற இணைப்புகள் கோடுகள் மற்றும் விமானங்களின் குறுக்கீடுகள் டான் சண்டே ராபர்ட் பிளெஸின் வழிமுறைகள் மற்றும் மாதிரி குறியீடு. விரிவுரை 4 குறிப்புகள். செயின்ட் லூயிஸில் உள்ள வாஷிங்டன் பல்கலைக்கழகம், சிஎஸ் 506: கணக்கீட்டு வடிவியல் (தற்காலிக சேமிப்பு நகல்). சிஜிஏஎல் இல் உள்ள கோடு பிரிவு குறுக்குவெட்டு, கம்ப்யூடேஷனல் வடிவியல் வழிமுறைகள் நூலகம் ஜெஃப் எரிக்சனின் "கோடு பிரிவு குறுக்குவெட்டு" விரிவுரை குறிப்புகள். சி குறியீடு மாதிரி டாரெல் ரெக்ஸ் ஃபின்லி வடிவியல் வழிமுறைகள் வடிவியல் குறுக்குவெட்டு கணக்கீட்டு வடிவவியலுடன் வரி-வரி குறுக்குவெட்டு முறை