A function to find the minimum bounding pie slice to enclose a set of points

Question

I have a set of points S that I need to sort based on their angles around a point P. However, I want to avoid specifying a particular starting angle for sorting. My goal is to obtain an ordered set where the angle between the first and last points has the smallest possible value among all potential starting angles.

In essence, I am not concerned with the final sorted set of points; instead, I am seeking the angle of the smallest pie slice that can encompass all the points in the set.

How can I achieve this efficiently in C++? I would appreciate any insights or suggestions on the most effective approach to tackle this problem.

Answer 1

1. Bring all angles into the range 0 to 2PI
2. Sort angles
3. Find the minimum covering angle over all pairs of adjacent angles.

The covering angle is defined as the angle of the traversal between two adjacent angles that would cover all other angles.

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;
}

Test cases and verification.

https://godbolt.org/z/v9vdWzbGK (c++23 is used for test cases because of range support but the implementation of AngleSpan itself is c++17 )