สมมติว่าเรามีชุดของเส้นอยู่ในรูปแบบ 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
