使用旋轉卡尺法計算座標平面上兩點間的最大距離

在 C 中，我們有一個預定義函數 sqrt，它傳回任何數字的平方根。旋轉卡尺法是用來求解演算法或計算幾何的技術。

旋轉卡尺方法的視覺表示

手部旋轉顯示了旋轉卡尺圖的真實範例，每當手部旋轉時，都會顯示垂直方向。我們也可以透過使用多邊形來理解這個概念。

在本文中，我們將使用旋轉卡尺法求兩個座標點的最大距離。 跨度>

文法

程式中使用以下語法 -

vector<datatype> name

參數

• 向量 - 我們從關鍵字向量開始，同時在 C 中初始化向量。

• datatype - 由向量表示的資料元素的類型。

• name - 向量的名稱。

演算法

• 我們將使用頭檔iostream、vector和cmath來啟動程式。

• #我們正在建立結構名稱點，它將儲存 x 和 y 的座標。

• 我們正在定義一個 double 資料類型的函數定義 distance() 來計算兩個座標點之間的距離。這裡，Points p1和Point p2是接受座標值並使用預先定義函數 sqrt 和距離公式傳回距離的參數。

• 我們正在定義一個名為CP() 的函數定義，其雙精確度資料類型接受參數Point p1、Point p2 和Point p3 b> 計算叉積向量，即p2-p1 和p3-p1 w.r.t x 和y 座標。

• 現在我們正在建立一個雙精確度資料類型的函數定義 rotatingCaliper()，它將參數作為點向量並最大化任意兩個座標平面之間的距離。

• 我們將變數result初始化為0，它將追蹤以滿足最大距離的計算。為了找到點的大小，它將使用名為 size() 的預定義函數並將其儲存在變數 n 中。

• 我們將兩個變數 j 和 k 初始化為 1 並執行以下操作 -

• #我們正在將j 移到多邊形中的下一個點以及當前邊'points[i]、points[ 的叉積CP i 1] % n'且下一條邊'points[j]'小於目前邊'points[i]'的叉積CP，points[ (i 1) % n]' 和下一個點'點[(j 1) % n]'之後的邊緣。這將驗證當前邊緣是否垂直於下一個邊緣。

• 我們將k 移到多邊形中的下一個點，直到當前點'point[i]' 與下一個點' 之間的距離point[k]' 小於目前點'point[i]' 與下一個點'points[(k 1)%n] 之後的點之間的距離'。這將驗證下一個點距離目前點最遠。

• 現在我們正在計算點j, k, 與當前點'point[i]' 之間的距離，將所有這些點相乘，然後我們將會得到result 變數中的最大值。

• 我們啟動主函數並將座標平面的值套用到「向量點」變數。

• 最後，我們呼叫函數名稱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

結論

我們透過計算兩個座標點之間的最大距離來了解旋轉卡尺法的概念。此方法的實際應用如孔徑角優化、機器學習分類等。

以上是使用旋轉卡尺法計算座標平面上兩點間的最大距離的詳細內容。更多資訊請關注PHP中文網其他相關文章！