Idiom zum Iterieren einer Reihe von Winkeln in einem Container?

Question

Angenommen, ich Daten von 2D-Linien in der Form diese durch Winkel sortiert

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

Und ich möchte speichern haben, die (-PI, PI] im Intervall sein muss.

Mein Problem: Ich möchte einen Bereich in diesem Container durchlaufen, aber erlauben Sie es, um die Enden des Intervalls zu wickeln. Zum Beispiel "alle Linien zwischen Winkeln PI*3/4 bis -PI*3/4".

Um zu klären, ob ich wie multimap Standardcontainer verwenden, kann ich nicht einfach die üblichen tun:

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 
} 

ich zerhacken könnte „zirkular Iterierte i“ -Funktion an die Stelle des ++i zu nehmen in die Schleife, denke ich. Aber es scheint, dass es ein allgemeines Problem sein sollte, also frage ich mich, ob es bereits ein bestehendes Idiom gibt, um es anzugehen?

Answer 1

Es gibt einen trigonometrischen Ansatz, um Probleme mit kreisförmigen Bereichen zu lösen. Für Bereich - seinen Enden (Beispiele here) normalisieren, und mittlere Winkel und Halbwinkel

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) 

nun diesen Unterschied des Winkels und der Bereich Mitte vergleichen ist niedriger als Halbwinkel bekommen. Cosinus löst mögliche Probleme mit Periodizität, negative Werte usw.

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