C++ 两点之间的最大距离，使用旋转标定器法在坐标平面上

在C++中，我们有一个预定义的函数sqrt，它返回任意数字的平方根。旋转标定器法是解决算法或计算几何的技术。

旋转标定器法的可视化表示

手的旋转显示旋转标定器图的真实示例，每当手旋转时，垂直方向会显示出来。我们也可以通过使用多边形形状来理解这个概念。

在本文中，我们将使用旋转标定器法来找到两个坐标点之间的最大距离。

语法

程序中使用了以下语法−

vector<datatype> name

参数

• vector − 在C++中初始化向量时，我们从关键字vector开始。

• datatype − 向量表示的数据元素的类型。

• name − 向量的名称。

步骤

• 我们将使用头文件开始程序，头文件分别为： iostream, vector, 和 cmath.

• 我们正在创建名为point的结构，它将存储 x 和 y 的坐标。

• 我们正在定义一个名为distance()的函数，其返回值为double类型，用于计算两个坐标点之间的距离。这里， Point p1 和 Point p2 是接受坐标值的参数，并使用预定义函数sqrt和距离公式返回距离。

• 我们正在定义一个名为CP()的函数，其返回值为double类型，接受参数 Point p1, Point p2, 。

并且 计算点p3的叉积向量，即，p2-p1和p3-p1相对于x和y坐标的值。

• 现在我们正在创建一个函数定义 rotatingCaliper() ，它的数据类型为double，参数为点的向量，并最大化任意两个坐标平面间的距离。

• 我们将变量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]’ 的叉积。这证明了当前边与下一个边垂直。

  • 我们正在将点 k 移动到多边形中的下一个点，直到当前点 ‘point[i]’ 和下一个点 ‘point[k]’ 之间的距离小于当前点 ‘point[i]’ 并且在下一个点后面的点 ‘points[(k+1)%n]’ 。这验证了下一个点离当前点最远。

  • 现在我们正在计算点 j，k， 和当前点 ‘point[i]’ 之间的距离，将这些点相乘，我们将得到 result 变量中的最大值。

• 我们开始主函数并将坐标平面的值应用到 **’vector points’ ** 变量中。

• 最后，我们调用函数名 rotatinCaliper() 并将 ‘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

结论

通过计算两个坐标点之间的最大距离，我们学习了旋转凸包法的概念。该方法的实际应用例如光圈角度优化和机器学习分类。