Sortieren und Selektieren einer ArrayList<Point3D>

CaSiLe95

Mitglied
Hallo liebes Java-Forum!

Dies ist mein erster Beitrag, deshalb: habt bitte Nachsicht, was das Beschreiben meines Problems betrifft, ich hoffe ich drücke mich präzise genug aus.. ;)
Im Rahmen meiner Projektarbeit, habe ich eine Punktewolke zu bearbeiten. In dieser Punktewolke befinden sich mehrere "Punktesäulen" (siehe Anhang). Bei diesen einzelnen Säulen soll jeweils der höchste Wert zurückgegeben und in einen ArrayListe gespeichert werden.
Hierbei stoße ich jedoch immer wieder auf Probleme.. Diesmal jedoch sitze ich seit 3 Tagen an einer einzigen Methode, die mir eine Liste an Punkten der Klasse Point3D (JavaFx) sortieren soll. Desweiteren soll sie auch eine kleine Operation ausführen.

Es wird der Methode eine Point3D-ArrayList mit Datentyp Point3D übergeben. Ziel ist es 1. die Punkte nach X, dann nach Y, und dann nach Z aufsteigend zu sortieren (also eine geschachtelte Sortiermethode: Wenn es mehrere Werte mit gleichem X-Wert gibt, soll anschließend nach Y aufsteigend aufgelistet werden und das gleiche dann mit Z, falls mehrere Punkte eben gleiche X UND Y Werte haben).

Soviel zur Sortierung.. Ich habe lange gebraucht, jedoch es durch YT-Tutorials geschafft die Point3D-Daten - zumindest stückweise - durch ein Comparator-Objekt zu sortieren:
Java:
public class Point3DComparator implements Comparator<Point3D> {

    String auswahl;

    public Point3DComparator(String auswahl) {
        this.auswahl = auswahl;
    }

    @Override
    public int compare(Point3D o1, Point3D o2) {
        if (auswahl.equals("X")) {
            if (o1.getX() < o2.getX()) {
                return -1;
            } else if (o1.getX() > o2.getX()) {
                return 1;
            } else {
                return 0;
            }
        } else if (auswahl.equals("Y")) {
            if (o1.getY() < o2.getY()) {
                return -1;
            } else if (o1.getY() > o2.getY()) {
                return 1;
            } else {
                return 0;
            }
        } else {
            if (o1.getZ() < o2.getZ()) {
                return -1;
            } else if (o1.getZ() > o2.getZ()) {
                return 1;
            } else {
                return 0;
            }
        }
    }

Wie man sehen kann, übergebe ich dem Comparator entweder "X", "Y" oder "Z" - String. Durch anschließenden Aufruf von "Collections.sort([ArrayList], [Comparator-Objekt])" wird dann die Liste sortiert.

So weit,so gut.

Nun der eigentliche Knackpunkt: Ich möchte die gesamte übergebene Punkteliste durchlaufen. Es soll überprüft werden, ob der nachfolgende Punkt gleiche X-Werte besitzt. Wenn ja, sollen diese Punkte in eine temporäre ArrayListe ("tmp1", wieder vom Typ <Point3D>) geschrieben werden. Wenn nein, soll die Verzweigung abgebrochen werden und beim nächsten Punkt weiter untersucht werden.
Diese temporäre Liste soll dann anschließend nach Y sortiert werden (Stichwort "Point3DComparator("Y")"). Auch hier gleiches Vorgehen: Gibt es vom Punkt mit den gleichen X-Werten jetzt auch Punkte mit den gleichen Y-Werten, sollen diese in einer weiteren temporären ArrayListe ("tmp2") gespeichert werden. Diese nun gespeicherten Werte sollen ein letztes Mal überprüft werden und der Wert mit dem höchsten Z-Wert soll in eine finale Rückgabe-ArrayList<Point3D> gespeichert werden.

Ich lade mal meinen geistigen Erguss hier hoch.. Vielleicht sagt ihr mir ja "das ist generell eine falsche Herangehensweise" oder ja auch nur "tja, da ist eben ein kleiner Fehler drin, der alles zu nichte macht". Ich habe meine fehlerbehaftete Methode jedenfalls wie folgt aufgebaut:
Code:
 public ArrayList<Point3D> getHighestZPoint2(ArrayList<Point3D> support, double range) {

        ArrayList<Point3D> output = new ArrayList<>();
        ArrayList<Point3D> tmp1 = new ArrayList<>();
        ArrayList<Point3D> tmp2 = new ArrayList<>();

        Point3DComparator comp1 = new Point3DComparator("X");
        Collections.sort(support, comp1);

        for (int m = 0; m < support.size(); m++) {

            double x0 = support.get(m).getX();

            for (int i = m; i < support.size(); i++) {

                double x = support.get(i).getX();

                if (x0 == x) {
                    tmp1.add(support.get(i));
//                    System.out.println(support.get(i));
                    x0 = x;
                } else {

                    Point3DComparator comp2 = new Point3DComparator("Y");
                    Collections.sort(tmp1, comp2);

                    for (int n = 0; n < tmp1.size(); n++) {

                        double y0 = tmp1.get(n).getY();

                        for (int j = n; j < tmp1.size(); j++) {

                            double y = tmp1.get(j).getY();

                            if (y0 == y) {
                                tmp2.add(tmp1.get(j));
                                y0 = y;
                            } else {

                                Point3DComparator comp3 = new Point3DComparator("Z");
                                Collections.sort(tmp2, comp3);
                                output.add(tmp2.get(tmp2.size()));
                            }
                            tmp2.clear();
                            n = j;
                        }

                    }
                    tmp1.clear();
                    m = i;
                }

            }
        }
        return output;
    }

Im Anhang könnt ihr auch die Beispiel .txt finden, die ich genutzt habe um die Punkte zu berechnen... Um diese einzuspielen, habe ich sie mir via Scanner- und File-Objekt in eine ArrayList<String> geladen und danach via Methode zu einer ArrayList<Point3D> konvertiert:
Code:
public ArrayList<String> dateiEinlesen(String url) throws FileNotFoundException {
        File file = new File(url);
        Scanner scanner = new Scanner(file);
        ArrayList<String> datei = new ArrayList<>();

        while (scanner.hasNextLine() == true) {
            String inhalt = scanner.nextLine();
            datei.add(inhalt);
        }
        return datei;
    }
    
        public Point3D getPunkt(String zeile) {
        Point3D point = new Point3D(0, 0, 0);
        String koordinate = "";
        int index = 0;
        String[] splitted = zeile.split(" ");
        int stellen = splitted[0].length();
        double x = Double.parseDouble(splitted[0].substring(0, stellen - 1));
        stellen = splitted[1].length();
        double y = Double.parseDouble(splitted[1].substring(0, stellen - 1));
        stellen = splitted[2].length();
        double z = Double.parseDouble(splitted[2].substring(0, stellen));

        return point.add(x, y, z);
    }
    
     public ArrayList<Point3D> StringToPoint3D(ArrayList<String> ergebnis) throws NullPointerException {

        ArrayList<Point3D> liste = new ArrayList<>();

        for (int i = 0; i < ergebnis.size(); i++) {
            if (getPunkt(ergebnis.get(i)) != null) {
                liste.add(getPunkt(ergebnis.get(i)));
            }
        }
        return liste;
    }

So.. Entschuldigt, für diesen ellenlangen Beitrag.. Ich hoffe wirklich, dass ihr mir vielleicht helfen könntet, denn ich habe leider keine Programmierer im Freundes- bzw. Bekanntenkreis und mein Lehrer in Softwareentwicklung ist nur sehr selten verfügbar..


Liebe Grüße und besten Dank auf alle Fälle schon jetzt für Hinweise und Tipps!

CaSiLe
 

Anhänge

  • Punktewolke_HighRes.txt
    266,1 KB · Aufrufe: 0
  • Punktewolke_Med_Res.txt
    241,9 KB · Aufrufe: 0
  • Punktewolke_LowRes.txt
    220,6 KB · Aufrufe: 0
  • Punktewolke.JPG
    Punktewolke.JPG
    258,8 KB · Aufrufe: 1

mihe7

Top Contributor
Ziel ist es 1. die Punkte nach X, dann nach Y, und dann nach Z aufsteigend zu sortieren (also eine geschachtelte Sortiermethode: Wenn es mehrere Werte mit gleichem X-Wert gibt, soll anschließend nach Y aufsteigend aufgelistet werden und das gleiche dann mit Z, falls mehrere Punkte eben gleiche X UND Y Werte haben).
Java:
Comparator<Point3D> pointComparator = Comparator.comparingDouble(Point3D::getX)
        .thenComparingDouble(Point3D::getY)
        .thenComparingDouble(Point3D::getZ);

Und jetzt einfach

Java:
Collections.sort(pointList, pointComparator);
 

CaSiLe95

Mitglied
Java:
Comparator<Point3D> pointComparator = Comparator.comparingDouble(Point3D::getX)
        .thenComparingDouble(Point3D::getY)
        .thenComparingDouble(Point3D::getZ);

Und jetzt einfach

Java:
Collections.sort(pointList, pointComparator);

Hallo mihe7,

danke dir für die schnelle Antwort! Das erleichtert mir zumindest mal direkt die "gestückelte" Sortierung der Liste, super! :)

Ich versuche jetzt gleich mal mich an meinem zweiten Problem, vielleicht komm ich da ja jetzt besser voran.. Über weitere Tipps bin ich dennoch sehr sehr dankbar! :)

GaLiGrü

CaSiLE
 

CaSiLe95

Mitglied
Hey mihe7,
okay ich versuchs nochmal zu erklären:

Die nun - dank deiner super Hilfe - sortierte Liste wird Point3D-Objekt für Point3D-Objekt durchlaufen. Es wird überprüft, ob der nachfolgende X-Wert des Punktes der gleiche ist wie der vorherige X-Wert . Wenn ja, soll eine temporäre Liste ("tmp1") angelegt werden mit diesen Punkten. Mit dem befüllen der Liste soll gestoppt werden, sobald ein Punkt mit anderem X-Wert auftaucht.
  • Nun sind wir sozusagen eine Ebene tiefer und versuchen das gleiche auf Y zu untersuchen. Gibt es also vom ersten zu untersuchenden Punkt mit gleichem X-Wert auch welche, die gleiche Y-Werte besitzen, so werden diese in einer weiteren temporären Liste ("tmp2") gespeichert. Auch hier wird mit dem Befüllen gestoppt, wenn nun ein Punkt zwar mit gleichem X, jedoch unterschiedlichem Y-Wert auftaucht.
    • Der letzte geschriebene Wert dieser tmp2 wird dann auf die "Hauptausgabeliste" (output), sprich den Rückgabewert der Methode (ArrayList<Point3D>) geschrieben. Danach wird die temporäre Liste über tmp2.clear() gelöscht.

  • Nun befinden wir uns am nächsten Y-Wert der tmp2. Gibt es hier also wieder mehrere Punkte mit gleichem X- und Y-Wert werden diese wieder in die frisch gelöschte temporäre Liste (tmp2) geschrieben. Wieder wird damit gestoppt, sobald ein Y-Wert folgt, der sich von dem vorherigen unterscheidet.
    • Und wieder wird der letzte Punkt der Liste auf output geschrieben, --> tmp2.clear();
Wir springen wieder in die oberste Ebene zurück und untersuchen nun den nächsten X-Wert, der sich vom vorherigen unterschieden hat.



Ich habe gerade eben es tatsächlich geschafft, meine Punkteliste nach dieser Vorstellung zu selektieren. Einzig eine Kleinigkeit schaffe ich nicht: Ist ein Wert sowohl in X, wie in Y einzigartig (sprich keine weitern Punkte der Liste haben gleichen X und Y-Wert) wird dieser Punkt der Liste einfach übersprungen und nicht mit aufgezeichnet.. Dies liegt an meinem Schleifenaufbau, bei dem mir noch das letzte Bit sozusagen fehlt..

Hier mein Code:
Java:
public ArrayList<Point3D> getHighestZPoint(ArrayList<Point3D> input) {

        Comparator<Point3D> pointComparator = Comparator.comparingDouble(Point3D::getX)
                .thenComparingDouble(Point3D::getY)
                .thenComparingDouble(Point3D::getZ);
        Collections.sort(input, pointComparator);

        ArrayList<Point3D> output = new ArrayList<>();
        ArrayList<Point3D> tmp1 = new ArrayList<>();
        ArrayList<Point3D> tmp2 = new ArrayList<>();

        int j = 0;
        int i = 0;

        for (j = 0; j < input.size(); j++) {
            double x0 = input.get(j).getX();
            for (i = j; i < input.size(); i++) {
                double x = input.get(i).getX();
                if (x == x0) {
                    tmp1.add(input.get(i));
                    x0 = x;
                } else {
                    j = i;
                    break;
                }
            }
            int l = 0;                                                              // Y-Ebene
            int k = 0;
            for (l = 0; l < tmp1.size(); l++) {
                double y0 = tmp1.get(l).getY();
                for (k = l; k < tmp1.size(); k++) {
                    double y = tmp1.get(k).getY();
                    if (y == y0) {
                        tmp2.add(tmp1.get(k));
                        y0 = y;
                    } else {
                        l = k;
                        break;
                    }
                }
                if (tmp2.isEmpty()) {                                                 // Z-Ebene
                    output.add(tmp2.get(0));
                } else {
                    output.add(tmp2.get(tmp2.size() - 1));
                }
                tmp2.clear();
            }
            tmp1.clear();
        }
        return output;
    }

Im Anhang hab ich mal die übergebene Liste und den Output hochgeladen. Ebenso ein Bild um mein kleines, noch übriges Problem vielleicht besser zu erläutern..

Gruß

CaSiLe
 

Anhänge

  • input.txt
    266 KB · Aufrufe: 0
  • output.txt
    95,2 KB · Aufrufe: 0
  • Vergleich.jpg
    Vergleich.jpg
    827,8 KB · Aufrufe: 0

mihe7

Top Contributor
okay ich versuchs nochmal zu erklären:
Danke. Da die Liste ja schon entsprechend sortiert ist, muss einfach der Punkt vor einem Wechsel des x- bzw. y-Werts zu output hinzugefügt werden.

Java:
Point3D old = sortierteListe.get(0);
Point3D lastAdded = null;
for (Point3D current : sortierteListe) {
    if (current.getX() != old.getX() || current.getY() != old.getY()) {
        output.add(old);
        lastAdded = old;
        old = current;
    }
}
if (lastAdded != null && (lastAdded.getX() != old.getX() || lastAdded.getY() != old.getY()) {
    output.add(old);
}

Nachtrag: Sonderfälle, wie sortierteListe.size() <= 1 sind nicht berücksichtigt.
 
Zuletzt bearbeitet:

CaSiLe95

Mitglied
Hallo mihe7,

sorry, dass ich mich erst jetzt melde.. Es war sehr viel zu tun die letzte Zeit..

Danke für deine konstruktive Hilfe!! Es hat ein paar Veränderungen an deinem Code benötigt, doch letztlich bin ich nun an meinem Etappenziel angekommen! :)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L allgemein Strings händisch in Liste sortieren Allgemeine Java-Themen 47
K Verbesserung der Laufzeit beim Sortieren von Einwohnern nach ihrem Geburtsjahr Allgemeine Java-Themen 0
Willi.We Array sortieren Allgemeine Java-Themen 5
L ArrayList sortieren Allgemeine Java-Themen 2
Monokuma String List nach Zahlen und Worten sortieren Allgemeine Java-Themen 9
MiMa ArrayList sortieren?? Allgemeine Java-Themen 5
C MySQL Tabellen sortieren. Allgemeine Java-Themen 33
Curtis_MC Collections Liste anhand mehrere Kriterien sortieren Allgemeine Java-Themen 6
B Java Mail: Emails sortieren? Allgemeine Java-Themen 5
G Liste (UsageStats) sortieren (Android) Allgemeine Java-Themen 5
FRI3ND Datentypen Date-Array sortieren - Text mitnehmen? Allgemeine Java-Themen 7
P Wertepaare sortieren Allgemeine Java-Themen 3
MiMa Sortieren nach Stellenangaben Allgemeine Java-Themen 7
T Collections ArrayList Sortieren Allgemeine Java-Themen 4
P Listen sortieren Allgemeine Java-Themen 1
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
S Verkettete (Teil)Liste sortieren ( rekursiv bis n) Allgemeine Java-Themen 2
K Strings sortieren: 2 Kritieren Allgemeine Java-Themen 5
B Algortihmus zum linearen Sortieren Allgemeine Java-Themen 1
K ArrayList sortieren Allgemeine Java-Themen 16
heyluigi Random Integer Array Ausgabe nach Größe sortieren Allgemeine Java-Themen 6
H Liste sortieren anhand optionalem Property Allgemeine Java-Themen 3
2 Mehrere Uhrzeiten Sortieren Allgemeine Java-Themen 2
B Counting Sort (Sortieren durch Zählen) Allgemeine Java-Themen 13
H Liste von Objekten generisch sortieren Allgemeine Java-Themen 0
Bluedaishi String Array mit Datum und Uhrzeit String sortieren Allgemeine Java-Themen 6
K Sortieren nach Vorgabe Allgemeine Java-Themen 6
S Erste Schritte Arrayliste alphabetisch sortieren mit Eingabe Allgemeine Java-Themen 9
L Sortieren von "Map<String, Object>" Allgemeine Java-Themen 2
M Sortieren und Leerzeichen Allgemeine Java-Themen 11
W Array Indizes sortieren Allgemeine Java-Themen 16
D Sortieren von Liste zu unperformant Allgemeine Java-Themen 6
E Array alphabetisch sortieren Allgemeine Java-Themen 1
5 Objekte Sortieren lassen Allgemeine Java-Themen 7
P Beim sortieren nullpointerexception Allgemeine Java-Themen 12
G Map nach key sortieren Allgemeine Java-Themen 14
T Array Sortieren (null Werte ans Ende) Allgemeine Java-Themen 2
Gossi Collections (Unbekannte) Liste Sortieren Allgemeine Java-Themen 10
S Int Values sortieren Allgemeine Java-Themen 7
S Sortieren nach Objekten Allgemeine Java-Themen 13
A 2D-array problem (sortieren) Allgemeine Java-Themen 6
T Liste mit GregorianCalendar-Objekten in List einlesen, mit Collection sortieren und ausgeben Allgemeine Java-Themen 3
D priority queue sortieren Allgemeine Java-Themen 10
G List<Person> sortieren Allgemeine Java-Themen 6
K Hashmap sortieren Allgemeine Java-Themen 6
H Problem beim Sortieren einer HashMap mit TreeSet Allgemeine Java-Themen 4
M ArrayList<String>, String häufigkeit sortieren Allgemeine Java-Themen 4
J Wie sortieren? Allgemeine Java-Themen 11
T Liste sortieren Allgemeine Java-Themen 6
K Strings sortieren (knifflig) Allgemeine Java-Themen 7
B JTable nach Icon sortieren Allgemeine Java-Themen 6
C ArrayList (mit Objekten) sortieren Allgemeine Java-Themen 12
J Map nach value sortieren Allgemeine Java-Themen 14
N Zahlen in Strings einer ArrayList sortieren Allgemeine Java-Themen 14
V ArrayList sortieren Allgemeine Java-Themen 7
S String-Array nach Datum sortieren Allgemeine Java-Themen 10
Developer_X Ein Array nach einem bestimmten Attribut sortieren Allgemeine Java-Themen 3
B Sortieren mit generischen Datentypen Allgemeine Java-Themen 3
C ArrayList anhand von zwei Attributen sortieren Allgemeine Java-Themen 4
O Sortieren von Telefonnummern Allgemeine Java-Themen 8
D JTabel sortieren nach mehreren kriterien Allgemeine Java-Themen 3
G Verschachtelte Treemaps, nach Value sortieren Allgemeine Java-Themen 11
K ArrayList nach bestimmtem Muster sortieren Allgemeine Java-Themen 3
I Vector mit Objekten sortieren,Videos mit JMF wiedergeben Allgemeine Java-Themen 6
S Koordinatentupel-Map sortieren?? Allgemeine Java-Themen 16
C ArrayList sortieren (mehrere Kriterien) Allgemeine Java-Themen 6
G ArrayList mit quicksort sortieren Allgemeine Java-Themen 9
Spot84 Vector nach Ressourcetyp sortieren Allgemeine Java-Themen 4
G sortieren von generics Allgemeine Java-Themen 10
Z Als Final deklarierte Klasse im Array sortieren Allgemeine Java-Themen 2
C ArrayList nach Datum sortieren Allgemeine Java-Themen 7
O ArrayList sortieren Allgemeine Java-Themen 8
G ArrayList mit Indices parallel sortieren Allgemeine Java-Themen 8
D HashMap sortieren Allgemeine Java-Themen 2
C Sortieren File[] Allgemeine Java-Themen 5
W [solved] Vector sortieren (Collection / Comparable?) Allgemeine Java-Themen 7
D LinkedList anhand einer long-Variable der Objekte sortieren Allgemeine Java-Themen 5
O Vektoren in Vektor sortieren aber mit Java 1.4 (!) Allgemeine Java-Themen 4
T TreeMap durch Comparator mit Generics sortieren Allgemeine Java-Themen 9
M ArrayList sortieren - HashMap mit sort_id vorhanden Allgemeine Java-Themen 2
A Sortieren mit Java Allgemeine Java-Themen 3
J Properties sortieren Allgemeine Java-Themen 6
T HashMap (String, Object(String , int)) nach int sortieren Allgemeine Java-Themen 7
E Bitte um Rat: Sortieren mit ArrayList Allgemeine Java-Themen 2
G Strings die Zahlen enthalten sinnvoll sortieren (A2 < A10 Allgemeine Java-Themen 4
G List mit selbstdefinierten Objekten sortieren Allgemeine Java-Themen 2
F Doppelt verkettete Liste sortieren? Allgemeine Java-Themen 8
S ArrayList nach mehreren Spalten sortieren? Allgemeine Java-Themen 13
G Set absteigend Sortieren Allgemeine Java-Themen 6
B ein spezielles Byte-Array sortieren Allgemeine Java-Themen 11
D Sortieren? Allgemeine Java-Themen 13
N ArrayList sortieren Allgemeine Java-Themen 10
L Nach Häufigkeit sortieren Allgemeine Java-Themen 6
S Dten im Excel sortieren Allgemeine Java-Themen 5
Z Elemente in Vector nach Häufigkeit sortieren. Allgemeine Java-Themen 13
H Objekte Sortieren Allgemeine Java-Themen 4
F Kann man String[] sortieren? Allgemeine Java-Themen 2
H will einfach nicht sortieren! Allgemeine Java-Themen 23
T Collections/Arrays sortieren => ä, ö, ü, ß Groß/klein Allgemeine Java-Themen 3
T Problem mit Sortieren Fehler: incompatible Types! Allgemeine Java-Themen 3

Ähnliche Java Themen


Oben