দুটি লাইন-সেগমেন্ট দেওয়া আছে। প্রথম লাইন সেগমেন্ট থেকে p1, p2 বিন্দু এবং দ্বিতীয় লাইন সেগমেন্ট থেকে q1, q2 বিন্দু। আমাদের চেক করতে হবে উভয় লাইন সেগমেন্ট একে অপর ইন্টারসেক্ট করছে কিনা।
আমরা বলতে পারি উভয় লাইন সেগমেন্ট ইন্টারসেক্ট করছে যখন নিচের শর্তগুলো পূরণ হয়:
- যখন (p1, p2, q1) এবং (p1, p2, q2)-এর ওরিয়েন্টেশন ভিন্ন হয় এবং
- (q1, q2, p1) এবং (q1, q2, p2)-এর ওরিয়েন্টেশন ভিন্ন হয়।
একটি অন্য শর্ত হল যখন (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2) কোলিনিয়ার (একই রেখায় আవিষ্ঠ)।
ইনপুট এবং আউটপুট
ইনপুট: দুটি লাইন-সেগমেন্টের বিন্দু লাইন-সেগমেন্ট ১: (0, 0) থেকে (5, 5) লাইন-সেগমেন্ট ২: (2, -10) থেকে (3, 10) আউটপুট: লাইনগুলো ইন্টারসেক্ট করছে
অ্যালগরিদম
direction(a, b, c)
ইনপুট: তিনটি বিন্দু।
আউটপুট: চেক করুন তারা কোলিনিয়ার নাকি অ্যান্টি-ক্লকওয়াইজ নাকি ক্লকওয়াইজ দিক।
শুরু
val := (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y)
যদি val = 0, তবে
কোলিনিয়ার ফেরত দিন
অন্যথায় যদি val < 0, তবে
অ্যান্টি-ক্লকওয়াইজ ফেরত দিন
ক্লকওয়াইজ ফেরত দিন
শেষisIntersect(l1, l2)
ইনপুট: দুটি লাইন সেগমেন্ট, প্রতিটি লাইনের দুটি বিন্দু p1 এবং p2।
আউটপুট: সত্য, যখন তারা ইন্টারসেক্ট করছে।
শুরু
dir1 = direction(l1.p1, l1.p2, l2.p1);
dir2 = direction(l1.p1, l1.p2, l2.p2);
dir3 = direction(l2.p1, l2.p2, l1.p1);
dir4 = direction(l2.p1, l2.p2, l1.p2);
যদি dir1 ≠ dir2 এবং dir3 ≠ dir4, তবে
সত্য ফেরত দিন
যদি dir1 =0 এবং l2.p1 লাইন l1-এ থাকে, তবে
সত্য ফেরত দিন
যদি dir2 = 0 এবং l2.p2 লাইন l1-এ থাকে, তবে
সত্য ফেরত দিন
যদি dir3 = 0 এবং l1.p1 লাইন l2-এ থাকে, তবে
সত্য ফেরত দিন
যদি dir4 = 0 এবং l1.p2 লাইন l2-এ থাকে, তবে
সত্য ফেরত দিন
মিথ্যা ফেরত দিন
শেষউদাহরণ
#include<iostream> using namespace std; struct Point { int x, y; }; struct line { Point p1, p2; }; bool onLine(line l1, Point p) { //চেক করুন p লাইন-এ আছে কিনা if(p.x <= max(l1.p1.x, l1.p2.x) && p.x <= min(l1.p1.x, l1.p2.x) && (p.y <= max(l1.p1.y, l1.p2.y) && p.y <= min(l1.p1.y, l1.p2.y))) return true; return false; } int direction(Point a, Point b, Point c) { int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y); if (val == 0) return 0; //কোলিনিয়ার else if(val < 0) return 2; //অ্যান্টি-ক্লকওয়াইজ দিক return 1; //ক্লকওয়াইজ দিক } bool isIntersect(line l1, line l2) { //দুটি লাইন এবং অন্য লাইনের বিন্দুಗಳಿಗೆ চারটি দিক int dir1 = direction(l1.p1, l1.p2, l2.p1); int dir2 = direction(l1.p1, l1.p2, l2.p2); int dir3 = direction(l2.p1, l2.p2, l1.p1); int dir4 = direction(l2.p1, l2.p2, l1.p2); if(dir1 != dir2 && dir3 != dir4) return true; //তারা ইন্টারসেক্ট করছে if(dir1==0 && onLine(l1, l2.p1)) //যখন লাইন2-এর p2 লাইন1-এ থাকে return true; if(dir2==0 && onLine(l1, l2.p2)) //যখন লাইন2-এর p1 লাইন1-এ থাকে return true; if(dir3==0 && onLine(l2, l1.p1)) //যখন লাইন1-এর p2 লাইন2-এ থাকে return true; if(dir4==0 && onLine(l2, l1.p2)) //যখন লাইন1-এর p1 লাইন2-এ থাকে return true; return false; } int main() { line l1 = {{0,0}, {5, 5}}; line l2 = {{2,-10}, {3, 10}}; if(isIntersect(l1, l2)) cout << "Lines are intersecting"; else cout << "Lines are not intersecting"; }আউটপুট
Lines are intersecting
