मान लीजिए हमारे पास y =mx + c के रूप में रेखाओं का समुच्चय है। इस रेखा और ऊर्ध्वाधर खंड द्वारा बनाए गए खंड हैं। हमें दिए गए खंड में मौजूद प्रतिच्छेदन बिंदु ज्ञात करना है या नहीं। मान लीजिए कि रेखाएँ इस प्रकार हैं -
एल1 =वाई =एक्स + 2
L2 =y =-x + 7
एल3 =वाई =-3
एल4 =वाई =2x - 7
और लंबवत खंड x =2 से x =4 तक दिया गया है।
यहाँ L1 और L2 के प्रतिच्छेदन बिंदु इस खंड के अंदर मौजूद हैं, इसलिए उत्तर सत्य होगा।
इस समस्या को हल करने के लिए, हम छँटाई तकनीक पर मुकदमा करेंगे। सबसे पहले, हम ऊर्ध्वाधर खंड की दोनों सीमाओं के साथ प्रत्येक रेखा के प्रतिच्छेदन बिंदु की गणना करेंगे। उसके बाद उसे एक जोड़ी के रूप में स्टोर करें। हमें चौराहों के y-निर्देशांक मानों को एक जोड़े के रूप में संग्रहीत करने की आवश्यकता है क्योंकि x-निर्देशांक स्वयं सीमा के बराबर हैं।
अब हम इन युग्मों को बायीं सीमा के साथ उनके प्रतिच्छेदन के आधार पर छाँटेंगे। उसके बाद, हम इन जोड़ियों पर एक-एक करके लूप करेंगे। यदि किन्हीं दो क्रमागत युग्मों के लिए, वर्तमान जोड़ी का दूसरा मान पिछली जोड़ी के दूसरे मान से कम है तो दिए गए ऊर्ध्वाधर खंड में एक प्रतिच्छेदन होना चाहिए।
उदाहरण
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
class line {
public:
int slope, intercept;
line(){
}
line(int slope, int intercept) : slope(slope), intercept(intercept) {
}
};
int getYCoordinate(line l, int x) {
return (l.slope * x + l.intercept);
}
bool hasIntersectionPoint(line lines[], int left_range, int right_range, int N) {
pair<int, int> y_border[N];
for (int i = 0; i < N; i++)
y_border[i] = make_pair(getYCoordinate(lines[i], left_range), getYCoordinate(lines[i], right_range));
sort(y_border, y_border + N);
for (int i = 1; i < N; i++) {
if (y_border[i].second < y_border[i - 1].second)
return true;
}
return false;
}
int main() {
int N = 4;
int slope[] = { 1, -1, 0, 2 };
int intercept[] = { 2, 7, -3, -7 };
line lines[N];
for (int i = 0; i < N; i++)
lines[i] = line(slope[i], intercept[i]);
int left_range = 2;
int right_range = 4;
if (hasIntersectionPoint(lines, left_range, right_range, N)) {
cout << "The intersection point is lies between " << left_range << " and " << right_range;
} else {
cout << "No intersection point is present in between " << left_range << " and " << right_range;
}
} आउटपुट
The intersection point is lies between 2 and 4