找到包围一组点的最小边界饼图切片的函数

Question

我有一组点 S，需要根据它们围绕点 P 的角度进行排序。但是，我想避免指定特定的排序起始角度。我的目标是获得一个有序集，其中第一个点和最后一个点之间的角度在所有潜在的起始角度中具有最小的可能值。

本质上，我并不关心最终排序的点集；相反，我正在寻找可以包含集合中所有点的最小饼图切片的角度。

如何在 C++ 中有效地实现这一点？对于解决此问题的最有效方法的任何见解或建议，我将不胜感激。

Answer 1

1. 将所有角度置于 0 到 2PI 范围内
2. 角度排序
3. 找到所有相邻角对的最小覆盖角。

覆盖角定义为覆盖所有其他角度的两个相邻角之间的遍历角度。

template <typename T>
T AngleSpan(std::vector<T> angles)
{
    // First bring all angles into 0 to 2PI
    for (T angle : angles)
    {
        angle = Wrap2PI(angle);
    }

    if (angles.size() == 0)
        throw std::runtime_error("The number of angles must have at least one angle");

    if(angles.size() == 1)
        return 0.;

    std::sort(angles.begin(), angles.end());
    // Push the start angle shifted forward by 360 degrees
    angles.push_back(angles.front() + 2 * PI);

    double coveringAngle = 2 * PI;
    for (size_t i = 1; i < angles.size(); ++i) {
        double testAngle = 2 * PI - angles[i] + angles[i - 1];
        if (testAngle < coveringAngle) {
            coveringAngle = testAngle;
        }
    }


    return coveringAngle;
}

测试用例和验证。

https://godbolt.org/z/v9vdWzbGK （由于范围支持，c++23 用于测试用例，但 AngleSpan 本身的实现是 c++17 ）