数据结构
网络
关系数据库管理系统
操作系统
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 次查看
