使用旋转卡钳法求坐标平面中两点之间的最大距离

在 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

结论

我们学习了旋转卡钳法的概念，通过计算两点之间的最大距离。这种方法的实际应用，例如孔径角优化和机器学习分类。

更新于：2023-07-24

140 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告