Multiple line segment intersection
গণনামূলক জ্যামিতিতে, একাধিক লাইন সেগমেন্ট ছেদ সমস্যা ইউক্লিডীয় সমতলে লাইন বিভাগগুলির একটি তালিকা সরবরাহ করে এবং জিজ্ঞাসা করে যে তাদের মধ্যে কোনও দুটি ছেদ (ক্রস) করে কিনা। সহজ অ্যালগরিদমগুলি প্রতিটি জোড়া বিভাগ পরীক্ষা করে। যাইহোক, যদি সম্ভবত ছেদকারী অংশগুলির একটি বড় সংখ্যা পরীক্ষা করতে হয়, তবে এটি ক্রমবর্ধমান অকার্যকর হয়ে ওঠে কারণ বেশিরভাগ জোড়া বিভাগগুলি একটি সাধারণ ইনপুট ক্রমে একে অপরের কাছাকাছি থাকে না। উচ্চ সংখ্যক সেগমেন্টের জন্য এই সমস্যা সমাধানের সবচেয়ে সাধারণ এবং আরও কার্যকর উপায় হল একটি সুইপ লাইন অ্যালগরিদম ব্যবহার করা, যেখানে আমরা লাইন সেগমেন্টগুলি জুড়ে একটি লাইন স্লাইডিং কল্পনা করি এবং আমরা ট্র্যাক করি যে এটি প্রতিটি সময়ে কোন লাইন সেগমেন্টগুলিকে ছেদ করে বাইনারি অনুসন্ধান গাছের উপর ভিত্তি করে একটি গতিশীল ডেটা কাঠামো ব্যবহার করে। শামোস-হোয়ে অ্যালগরিদম লাইন সেগমেন্ট ছেদ সনাক্তকরণ সমস্যা সমাধানের জন্য এই নীতিটি প্রয়োগ করে, যেমনটি উপরে বলা হয়েছে, লাইন সেগমেন্টগুলির একটি সেটের ছেদ রয়েছে কিনা তা নির্ধারণ করার জন্য; বেন্টলি-অটম্যান অ্যালগরিদম প্রতি ছেদ লগারিদমিক সময়ে সমস্ত ছেদ তালিকাভুক্ত করার জন্য একই নীতি দ্বারা কাজ করে। আরও দেখুন বেন্টলি-অটম্যান অ্যালগরিদম রেফারেন্স অধ্যায় 2ঃ লাইন সেগমেন্ট ইন্টারসেকশন, পৃ. 19-44। টমাস এইচ. করমেন, চার্লস ই. লেইসারসন, রোনাল্ড এল. রিভেস্ট এবং ক্লিফোর্ড স্টেইন। অ্যালগরিদমের ভূমিকা, দ্বিতীয় সংস্করণ। এমআইটি প্রেস এবং ম্যাকগ্রা-হিল, 1990। ধারা 33.2: কোনও জোড়া অংশ ছেদ করে কিনা তা নির্ধারণ করা, পৃ. 934-947। জে. এল. বেন্টলি এবং টি. ওটমান., জ্যামিতিক ছেদগুলির রিপোর্টিং এবং গণনার জন্য অ্যালগরিদম, আই. ই. ই. ই ট্রান্স। গণনা করুন। সি28 (1979), 643-647। বাহ্যিক লিঙ্ক লাইন এবং প্লেনের ছেদ অ্যালগরিদম এবং ড্যান সানডে রবার্ট প্লেসের নমুনা কোড। বক্তৃতা 4 টি নোট। সেন্ট লুইসের ওয়াশিংটন বিশ্ববিদ্যালয়, সিএস 506: গণনামূলক জ্যামিতি (ক্যাশে করা অনুলিপি)। সিজিএএল-এ লাইন সেগমেন্ট ছেদ, জেফ এরিকসনের কম্পিউটশনাল জ্যামিতি অ্যালগরিদম লাইব্রেরি "লাইন সেগমেন্ট ইন্টারসেকশন" বক্তৃতা নোট। লাইন-লাইন ছেদ পদ্ধতি সি কোডের সাথে নমুনা ডেরেল রেক্স ফিনলি জ্যামিতিক অ্যালগরিদম জ্যামিতিক ছেদ গণনামূলক জ্যামিতি