मान लीजिए हमारे पास y = mx + c के रूप में रेखाओं का एक समूह है। इस रेखा और ऊर्ध्वाधर खंड द्वारा खंड बनाए गए हैं। हमें दिए गए खंड में मौजूद प्रतिच्छेदन बिंदु को ढूंढना है या नहीं। मान लीजिए रेखाएं इस प्रकार हैं -
L1 = y = x + 2
L2 = y = -x + 7
L3 = y = -3
L4 = y = 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
