idiom for iterating a range of angles in a contain

问题:

Suppose I have data of 2D lines in the form

struct Point { int x, y; };
struct Line {
    Point p1, p2;
    double angle() const { return atan2(p2.y-p1.y, p2.x-p1.x); }
};

And I want to store these sorted by angle, which must be in the interval (-PI, PI].

My problem: I want to iterate a range in this container, but allow it to wrap around the ends of the interval. For example "all lines between angles PI*3/4 to -PI*3/4".

To clarify, if I use standard containers like multimap, I can't simply do the usual:

std::multimap<double, Line> lm;

//insert elements...

auto begin = lm.lower_bound(PI*3/4);
auto end = lm.upper_bound(-PI*3/4);
for(auto & i = begin; i != end; ++i) {  //infinite loop: end is before begin!
    //do stuff with i
}

I could hack up a "circularly iterate i" function to take the place of the ++i in the loop, I guess. But this seems like it should be a common problem, so I'm wondering if there's already an existing idiom to address it?

回答1:

There is trigonometric approach to solve problems with circular ranges. For range - normalize its ends (examples here), and get middle angle and half-angle

if range_end < range_start then
   range_end = range_end + 2 * Pi

half = (range_end - range_start) / 2
mid  = (range_end + range_start) / 2
coshalf = Cos(half)

Now compare that difference of angle and range middle is lower then half-angle. Cosine solves potential troubles with periodicity, negative values etc.

if Cos(angle - mid) >= coshalf then
  angle lies in range