রেখা AB-এর জন্য বিন্দু A এবং B এবং রেখা PQ-এর জন্য বিন্দু P এবং Q দেওয়া আছে; এই দুটি রেখার মধ্যে ছেদবিন্দু খুঁজে বের করা হবে।
দ্রষ্টব্য - বিন্দুগুলো ২D সমতলে X এবং Y 좌표-এ দেওয়া আছে।
এখানে A(a1, a2), B(b1, b2) এবং C(c1, c2), D(d1, d2) হলো দুটি স্বতন্ত্র রেখা গঠনকারী 좌표 এবং P(p1, p2) হলো ছেদবিন্দু (শুধুমাত্র চিত্রানুসারে ব্যাখ্যা)।
ছেদবিন্দু খুঁজে বের করার পদ্ধতি
উপরোক্ত চিত্রটিকে বিবেচনা করি -
উদাহরণ
তাই (a1, a2), (b1, b2), (c1, c2), (d1, d2) ব্যবহার করে আমরা গণনা করব: A1 = b2 - a2 B1 = a1 - b1 C1 = (A1 * a1) + (B1 * a1) A2 = d2 - c2 B2 = c1 - d1 C2 = (A2 * c1) + (B2 * c2) দেওয়া দুটি রেখা হচ্ছে: 1. A1x + B1y = C1 2. A2x + B2y = C2 এখন, ছেদবিন্দু খুঁজে বের করতে হলে এই ২টি সমীকরণ সমাধান করতে হবে। আমরা ১কে B1 দিয়ে এবং ২কে B2 দিয়ে গুণ করব, তাহলে পাব: A1B2x + B1B2y = C1B2 A1B1x + B2B1y = C1B1 এগুলো বিয়োগ করলে পাব, (A1B2 - A2B1)x = C1B2 - C2B1
এটি আমাদের x-এর মান দেবে, এবং একইভাবে y-এর মান পাওয়া যাবে যা ছেদবিন্দু p1 (x) এবং p2 (y) হবে।
দ্রষ্টব্য - উপরের সূত্রটি দুটি রেখার ছেদবিন্দু দেবে, কিন্তু যদি রেখাংশ (segments) দেওয়া থাকে, তবে আমাদের আবার চেক করতে হবে যে গণনা করা বিন্দুটি রেখাংশের ওপর অবস্থিত কিনা।
- min(x1, x2) <= x <= max(x1, x2)
- min(y1, y2) <= y <= max(y1, y2)
সমস্যা সমাধানের পদ্ধতি -
- ইনপুট মানগুলো নেওয়া।
- নির্ণায়ক (determinant) খুঁজে বের করা যা হলো a1 * b2 - a2 * b1
- যদি নির্ণায়ক = 0 হয়, তবে রেখাগুলো সমান্তরাল।
- যদি নির্ণায়ক শূন্য না হয়, তবে x = (c1 * b2 - c2 * b1) এবং y = (a1 * c2 - a2 * c1)
- ফলাফল রিটার্ন এবং প্রিন্ট করা।
অ্যালগরিদম
শুরু
ধাপ ১ -> x এবং y 좌표 প্রিন্ট করার ফাংশন ঘোষণা
void display(mk_pair par)
par.first এবং par.second প্রিন্ট
ধাপ ২ -> ছেদবিন্দু গণনার ফাংশন ঘোষণা
mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D)
double a = B.second - A.second ঘোষণা
double b = A.first - B.first ঘোষণা
double c = a*(A.first) + b*(A.second) ঘোষণা
double a1 = D.second - C.second ঘোষণা
double b1 = C.first - D.first ঘোষণা
double c1 = a1*(C.first)+ b1*(C.second) ঘোষণা
double det = a*b1 - a1*b ঘোষণা
যদি (det == 0)
return make_pair(FLT_MAX, FLT_MAX)
শেষ
অন্যথায়
double x = (b1*c - b*c1)/det ঘোষণা
double y = (a*c1 - a1*c)/det ঘোষণা
return make_pair(x, y)
শেষ
ধাপ ৩ -> main()-এ
পয়েন্টের জন্য mk_pair q = make_pair(2, 1) ঘোষণা এবং কল
যদি (inter.first == FLT_MAX এবং inter.second == FLT_MAX)
"given lines are parallel" প্রিন্ট
শেষ
অন্যথায়
display(inter) কল
শেষ
শেষ
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define mk_pair pair<double, double>
// x এবং y 좌표 প্রদর্শন
void display(mk_pair par) {
cout << "(" << par.first << ", " << par.second << ")" << endl;
}
mk_pair intersection(mk_pair A, mk_pair B, mk_pair C, mk_pair D) {
// রেখা ABকে a1x + b1y = c1 আকারে প্রকাশ
double a = B.second - A.second;
double b = A.first - B.first;
double c = a*(A.first) + b*(A.second);
// রেখা CDকে a2x + b2y = c2 আকারে প্রকাশ
double a1 = D.second - C.second;
double b1 = C.first - D.first;
double c1 = a1*(C.first)+ b1*(C.second);
double det = a*b1 - a1*b;
if (det == 0) {
return make_pair(FLT_MAX, FLT_MAX);
} else {
double x = (b1*c - b*c1)/det;
double y = (a*c1 - a1*c)/det;
return make_pair(x, y);
}
}
int main() {
mk_pair q = make_pair(2, 1);
mk_pair r = make_pair(2, 7);
mk_pair s = make_pair(4, 4);
mk_pair t = make_pair(6, 4);
mk_pair inter = intersection(q, r, s, t);
if (inter.first == FLT_MAX && inter.second==FLT_MAX) {
cout << "The given lines AB and CD are parallel.\n";
} else {
cout << "The intersection of the given lines AB and CD is: ";
display(inter);
}
return 0;
}
আউটপুট
The intersection of the given lines AB and CD is: (2, 4)
