Sortieren und Selektieren einer ArrayList<Point3D>

[CaSiLe95]

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:

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:

 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:

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

 

[mihe7]

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).

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

Und jetzt einfach

Collections.sort(pointList, pointComparator);

 

[CaSiLe95]

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

Und jetzt einfach

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

 

[mihe7]

Ich versuche jetzt gleich mal mich an meinem zweiten Problem,

Meinst Du das hier?

Nun der eigentliche Knackpunkt

Das hatte ich nicht ganz verstanden. Wenn ich es nochmal lese: geht es darum, je X-Y-Ebene die Punkte mit dem größten Z-Wert zu erhalten?

 

[CaSiLe95]

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:

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

 

[mihe7]

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.

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.

 

[CaSiLe95]

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! 🙂