数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在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
更新于：2020年1月3日
浏览量：121
广告