資料結構
網路
關係資料庫管理系統 (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
廣告