C++ 旋转卡尺

用于解决各种计算几何问题（尤其是涉及凸形的问题）的一种几何方法是使用旋转卡尺。该方法通常用于计算凸多边形的附加凸包属性，例如其直径或最小包围矩形。

旋转卡尺是一种计算几何方法，用于解决凸形问题，尤其是在确定距离和最大化特征时。它通常涉及使用 Andrew 的单调链和 Graham 扫描等方法来确定一组点的凸包，这些点位于 C++ 中。在构建完凸包后，旋转卡尺使用两个 指针 来有效地计算凸包上点之间的最大距离，这可以用来表示 多边形 的直径。该方法在需要凸多边形的情况下提高了算法性能，并降低了计算复杂度。它对各种几何应用都有益。

旋转卡尺的特性

旋转卡尺的几个特性如下：

1. 凸包计算：确定一组点的凸包后，可以使用旋转卡尺方法。它能够有效地研究凸包的顶点。
2. 极端点查询：该算法能够找到凸多边形的极端点，例如在特定方向上的最远点，这对于各种计算几何问题非常有用。
3. 最小包围矩形：通过围绕凸包旋转卡尺，可以确定可以包含该多边形的最小矩形。这通常被称为最小面积矩形问题。
4. 最远点对：在空间分析和聚类中，该过程可用于查找一组点中最远的点对。
5. 点在多边形测试：利用其特性，旋转卡尺可以有效地确定一个点是否在凸多边形内部。
6. 角度和方向计算：该方法通过计算凸多边形顶点形成的直线的角度和方向，有助于图形应用程序。
7. 效率：对于大型数据集，旋转卡尺方法效率很高，因为它在计算凸包花费 O(n log n) 时间后，通常每个查询只需要 O(n) 时间。

旋转卡尺的优点

旋转卡尺的几个优点如下：

1. 降低二维几何计算的复杂度：该算法降低了需要复杂蛮力方法的任务的复杂度。例如，与 O(n²) 的蛮力方法相比，可以更有效地计算凸包中两点之间的最大距离。
2. 与凸包算法配合良好：常用的凸包方法，如 Jarvis March 和 Graham 扫描，可以与旋转卡尺无缝集成。一旦计算出凸包，就可以直接应用，无需进行重大调整，从而简化了问题解决方法。
3. 最优时间复杂度：与 Andrew 的单调链或 Graham 扫描等需要 O(n log n) 时间的算法结合使用时，旋转卡尺在凸包上运行时间为 O(n)。这使其在需要凸多边形或点集的问题中非常高效。

旋转卡尺的缺点

旋转卡尺的几个缺点如下：

1. 实现复杂度：旋转卡尺方法在理论上可能难以使用，尤其是在处理退化多边形（例如，具有共线点的多边形）等边缘情况时。这些情况需要开发人员仔细处理，这可能会导致代码更加复杂。
2. 凸包要求：该过程只能用于凸形。通常必须先计算输入点的凸包，然后才能应用旋转卡尺。凸包计算（例如，Jarvis March 或 Graham 扫描）会增加编码工作量和处理开销。
3. 数值精度问题：计算几何中依赖于浮点计算的算法，例如处理斜率或角度的算法，容易出现精度问题。计算旋转卡尺的常见任务是点之间的斜率、距离和角度。这可能导致舍入错误，尤其是在处理较大的坐标值或近共线点时。

旋转卡尺的应用

旋转卡尺的几个应用如下：

1. 求凸多边形的直径（最远点对）

算法接收一个凸多边形，并确定其直径，即距离最远的点对。通过围绕一个 n 边形旋转一对卡尺，可以在 O(n) 时间内计算出对径点之间的距离。

2. 求凸多边形内矩形的最小或最大面积/周长

在确定可以内接于凸多边形的矩形的最小或最大面积或周长时，可以应用该过程。通过使用旋转卡尺测量矩形的宽度和高度，可以“旋转”该多边形并有效地计算出相应的值。

3. 计算最小包围盒（定向包围盒）

可以使用旋转卡尺找到一组点周围的最小面积包围盒。通过围绕点集的凸包旋转卡尺，可以找到包含所有点的最小矩形。

4. 求两个凸多边形之间的最小距离

旋转卡尺可用于快速确定两个凸多边形之间的最小欧几里得距离。通过使一个多边形相对于另一个多边形旋转，可以确定两个多边形之间任何点对的最小距离。

5. 求凸多边形的宽度（两个平行支撑线之间的最小距离）

接触凸多边形两侧的两个平行线之间的最小距离称为其宽度。通过沿着多边形的边移动卡尺并测量垂直距离，旋转卡尺可以确定此宽度。

6. 查找所有对径点

连接它们的线段平行于凸包边的顶点对称为对径点。通过旋转卡尺，可以在线性时间内找到所有这些对，这可以应用于各种几何优化问题。

示例

让我们以一个例子来说明 C++ 中的旋转卡尺。

输出

 
The maximum distance (diameter) between points in the convex polygon is: 3.16228   

说明

随附的 C++ 代码实现了用于确定凸多边形中点之间最大距离（直径）的旋转卡尺方法。为了表示 2D 坐标，首先定义了一个 Point 结构，然后重载了 < 运算符进行排序。cross 函数 计算交叉积，以帮助确定点的方向。Andrew 的单调链方法用于 convexHull 函数，从一组点构建凸包。squaredDistance 函数确定两点之间的平方距离，避免了不必要的平方根计算。旋转卡尺函数使用两个指针在凸包上循环，以有效地确定最大距离。然后，main 函数计算一组点的凸包，初始化它们，并显示最大距离。此实现有效地演示了旋转卡尺在计算几何中的应用。