資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用旋轉卡鉗法求座標平面中兩點之間的最大距離
在 C++ 中，我們有一個預定義函式 sqrt，它返回任何數字的平方根。旋轉卡鉗法是用於解決演算法或計算幾何的技術。
旋轉卡鉗法的視覺表示
指標旋轉展示了旋轉卡鉗圖的真實示例，指標旋轉時會顯示垂直方向。我們也可以使用多邊形形狀來理解這個概念。
在本文中，我們將使用旋轉卡鉗法找到兩個座標點之間的最大距離。
語法
程式中使用的以下語法：
vector<datatype> name
引數
vector - 在 C++ 中初始化向量時，我們以關鍵字 vector 開始。
datatype - 向量表示的資料元素的型別。
name - 向量的名稱。
演算法
我們將從名為iostream、vector和cmath的標頭檔案開始程式。
我們正在建立名為 point 的結構，它將儲存x和y的座標。
我們正在定義一個雙資料型別的函式定義distance()來計算兩點之間的距離。這裡，Points p1和Point p2是接受座標值並使用預定義函式 sqrt 和距離公式返回距離的引數。
我們正在定義一個名為CP()的雙資料型別的函式定義，它接受引數Point p1、Point p2和Point p3，計算叉積向量，即關於 x 和 y 座標的p2-p1和p3-p1。
現在，我們正在建立雙資料型別的函式定義rotatingCaliper()，它將點向量作為引數，並最大化任意兩個座標平面之間的距離。
我們將變數 result 初始化為0，它將跟蹤滿足最大距離計算的要求。為了找到點的數量，它將使用名為 size() 的預定義函式，並將結果儲存在變數 n 中。
我們將兩個變數j和k初始化為 1，並執行以下操作：
我們將j移動到多邊形中的下一個點，並且當前邊'points[i]，points[i+1] % n'和下一條邊'points[j]'的叉積CP小於當前邊'points[i]，points[(i + 1) % n]'和下一條邊'points[(j + 1) % n]'的叉積 CP。這驗證了當前邊垂直於下一條邊。
我們將k移動到多邊形中的下一個點，直到當前點'point[i]'和下一個點'point[k]'之間的距離小於當前點'point[i]'和下一個點之後的點'points[(k+1)%n]'之間的距離。這驗證了下一個點距離當前點最遠。
現在，我們正在計算點j、k和當前點'point[i]'之間的距離，將所有這些點乘在一起，我們將在result變數中獲得最大值。
我們開始主函式並將座標平面的值應用於'vector <point> points'變數。
最後，我們呼叫函式名rotatingCaliper()並將'points'值作為引數傳遞，以獲取旋轉卡鉗圖的最大距離。
示例
在這個程式中，我們將執行使用旋轉卡鉗法求座標平面中兩點之間的最大距離。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct Point {
double x, y;
};
// In this function we are calculating the distance between two coordinate point.
double distance(Point p1, Point p2) {
return sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
}
// In this function we are calculating the cross-product of two vector
double CP(Point p1, Point p2, Point p3) // CP: cross-product {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
// In this function we are calculating the Rotating Caliper
double rotatingCalipers(vector<Point> points) {
double result = 0;
int n = points.size();
int j = 1, k = 1;
for (int i = 0; i < n; i++) {
while (CP(points[i], points[(i + 1) % n], points[j]) < CP(points[i], points[(i + 1) % n], points[(j + 1) % n]))
{
j = (j + 1) % n;
}
while (distance(points[i], points[k]) < distance(points[i], points[(k + 1) % n])) {
k = (k + 1) % n;
}
// calculate the max distance
result = max(result, distance(points[i], points[j]) * distance(points[i], points[k]));
}
return result;
}
int main() {
vector<Point> points = {{0, 0}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}, {4, 5}, {5, 5},{5,6}};
cout << "Maximum distance between two coordinate points: "<<rotatingCalipers(points) << endl;
return 0;
}
輸出
Maximum distance between two coordinate points: 39.0512
結論
我們學習了旋轉卡鉗法的概念，透過計算兩點之間的最大距離。這種方法的實際應用，例如孔徑角最佳化和機器學習分類。
140 次檢視
