দুটি লাইন-সেগমেন্ট দেওয়া যাক। প্রথম লাইন সেগমেন্ট থেকে পয়েন্ট 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) সমরেখা হয়।
ইনপুট এবং আউটপুট
Input: Points of two line-segments Line-segment 1: (0, 0) to (5, 5) Line-segment 2: (2, -10) to (3, 10) Output: Lines are intersecting
অ্যালগরিদম
দিক (a, b, c)
ইনপুট: তিন পয়েন্ট।
আউটপুট: এগুলি সমরেখার কিনা বা ঘড়ির কাঁটার বিপরীতে বা ঘড়ির কাঁটার দিকের দিকে তা পরীক্ষা করুন৷
Begin val := (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y) if val = 0, then return collinear else if val < 0, then return anti-clockwise return clockwise End
ইন্টারসেক্ট(l1, l2)
ইনপুট: দুটি লাইন সেগমেন্ট, প্রতিটি লাইনে দুটি বিন্দু p1 এবং p2 আছে।
আউটপুট: সত্য, যখন তারা ছেদ করছে।
Begin 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); if dir1 ≠ dir2 and dir3 ≠ dir4, then return true if dir1 =0 and l2.p1 on the line l1, then return true if dir2 = 0 and l2.p2 on the line l1, then return true if dir3 = 0 and l1.p1 on the line l2, then return true if dir4 = 0 and l1.p2 on the line l2, then return true return false End
উদাহরণ
#include<iostream>
using namespace std;
struct Point {
int x, y;
};
struct line {
Point p1, p2;
};
bool onLine(line l1, Point p) { //check whether p is on the line or not
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; //colinear
else if(val < 0)
return 2; //anti-clockwise direction
return 1; //clockwise direction
}
bool isIntersect(line l1, line l2) {
//four direction for two lines and points of other line
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; //they are intersecting
if(dir1==0 && onLine(l1, l2.p1)) //when p2 of line2 are on the line1
return true;
if(dir2==0 && onLine(l1, l2.p2)) //when p1 of line2 are on the line1
return true;
if(dir3==0 && onLine(l2, l1.p1)) //when p2 of line1 are on the line2
return true;
if(dir4==0 && onLine(l2, l1.p2)) //when p1 of line1 are on the line2
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
