Punktkoordinaten in Serpentinenmuster sortieren

bekinect

Hallo alle zusammen

In meinem Code habe ich zur Zeit zwei Vektoren. In jedem Vektor speichere ich die Koordinaten von verschiedenen Punkten. Aus zwei Punkten eines jeden Vektors bilde ich anschließend Geradensegmente und schneide die zwei Segmente miteinander. Die Schnittpunkte, sofern sie existieren werden in einem dritten gespeichert. Dieser dritte Vektor soll jetzt sortiert werden, sodass sich eine Serpentinen ähnliche Struktur bildet. Zur Erklärung hier einmal der derzeitige Output meiner Funktion:
*
5 -2
-5 -2
5 -1
-5 -1
5 0
-5 0
5 1
-5 1
5 2
-5 2
*
Zwar ist die zweite Spalte aufsteigend sortiert, was ich auch brauche, aber die erste Spalte ist absteigend sortiert. Ich hab einmal versucht den Output händisch zu verändern und komm zu diesem Ergebnis:
*
5 -2
-5 -2
-5 -1
5 -1
5 0
-5 0
-5 1
5 1
5 2
-5 2
*
So bräuchte ich es auch durch meinen Code. Wie man sieht ist die zweite Spalte aufsteigend sortiert, die erste Spalte alterniert jedoch. Ich hab mir zwar überlegt wie ich es mit if-Statements machen könnte, aber wirklich schöner Code ergibt sich damit nicht. Ich würde am liebsten die Standard sort-Funktion für C++ verwenden, hab aber leider überhaupt keine Ahnung wie die sortier-Routine ausschauen müsste, damit ich dieses alternierende Muster erreichen kann. Habt ihr vielleicht einen Tipp für mich

lg

sind die Elemente der ersten Spalte immer die gleichen Werte, nur einmal positiv das andere mal negativ? (z.B. +5, -5, ...)

Du könntest jedenfalls den Mittelwert der Elemente der ersten Spalte berechnen. Dann machst du zwei neue Vektoren, der eine enthält alle Elemente größer dem Mittelwert (s1), der zweite Vektor (s2) den Rest.
Und dann baust du dir den Ergebnisvektor sres eben zusammen, indem du abwechselnd ein (oder zwei) Element(e) aus dem Vektor s1 und s2 nimmst, bis alle Elemente entnommen sind.

Ich denke, man kann die brutale Methode nehmen: erst alles nach der 2. Spalte sortieren und dann jeden Bereich gleicher zweiter Spalte einzeln nach der ersten sortieren.

So zum Beispiel:

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    typedef pair<double, double> Punkt;
    vector<Punkt> v{{5, -2}, {5, -1}, {5, 0}, {-5, 0}, {-5, -1}, {-5, 1}, {5, 1}, {5, 2}, {-5, 2}, {-5, -2}};
    sort(v.begin(), v.end(), [](const Punkt &a, const Punkt &b) { return a.second < b.second; });
    bool ascending_first = false;
    auto firstInRange = v.begin();
    while (firstInRange != v.end()) {
        auto endInRange =
            adjacent_find(firstInRange, v.end(), [](const Punkt &a, const Punkt &b) { return a.second != b.second; });
        if (endInRange != v.end()) ++endInRange;
        sort(firstInRange, endInRange, [ascending_first](const Punkt &a, const Punkt &b) {
            return ascending_first ? a.first < b.first : b.first < a.first;
        });
        ascending_first = !ascending_first;
        firstInRange = endInRange;
    }
    for (const auto &p : v) {
        cout << p.first << " " << p.second << "\n";
    }
}

Dasd

Geht auch in einem Rutsch:

#include <algorithm> 
#include <iostream> 
#include <vector> 

using namespace std; 

int main() { 
     typedef pair<double, double> Punkt; 
     vector<Punkt> v{{5, -2}, {5, -1}, {5, 0}, {-5, 0}, {-5, -1}, {-5, 1}, {5, 1}, {5, 2}, {-5, 2}, {-5, -2}}; 
     sort(v.begin(), v.end(), [](const Punkt &a, const Punkt &b) { 
     	if (a.second == b.second) {
     		if (static_cast<int>(a.second) % 2 != 0)
	     		return a.first > b.first;
     		else
	     		return a.first < b.first;
     	} else
     		return a.second < b.second; 
     }
     ); 
     for (const auto &p : v) { 
         cout << p.first << " " << p.second << "\n"; 
     } 
}

Die "Startrichtung" der Serpentine hängt hierbei allerdings von den Daten ab.

Wieso sollte die Sortierrichtung davon abhängen, ob der Ganzzahl-Anteil der 2. Koordinate des Punktes gerade ist?!

Für mich siehst das so aus, als würdest du hier die Annahme machen, dass die 2. Koordinate in allen Punkten eine Ganzzahl ist und dass nur aufeinander folgende Zahlen vorkommen bzw. nie eine Lücke von einer ungeraden Zahl von Zahlen besteht.

Dasd

wob schrieb:

Wieso sollte die Sortierrichtung davon abhängen, ob der Ganzzahl-Anteil der 2. Koordinate des Punktes gerade ist?!

Für mich siehst das so aus, als würdest du hier die Annahme machen, dass die 2. Koordinate in allen Punkten eine Ganzzahl ist und dass nur aufeinander folgende Zahlen vorkommen bzw. nie eine Lücke von einer ungeraden Zahl von Zahlen besteht.

Richtig. Und - wie gesagt - die Startrichtung der Serpentine hängt davon ab, ob die zweite Komponente des ersten Punktes gerade ist.