在C ++中查找段内的线的交点
假设我们以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