Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten

izoards

Bekanntes Mitglied
Hallo,

Mit der OCR Texterkennung kriege ich Unsortierte Elemente, welche ich nun von links nach rechts und von oben nach unten sortieren möchte. Von den erkannten Elementen kann ich z.B. die X,Y Koordinaten ermitteln.
Leider fehlt mir die Idee, wie ich nun die Sortierung machen soll.

Hoffe jemand hatte auch schon ein ähnliches Thema und kann mir auf die Sprünge helfen 🙏
 

mihe7

Top Contributor
Zum Beispiel:
Java:
record Element(int x, int y) {}

public void sort(List<Element> elements) {
    Comparator<Element> xCoords = Comparator.comparingInt(Element::x);
    Comparator<Element> yCoords = Comparator.comparingInt(Element::y);
    // erst nach x-Koordinate, dann nach y-Koordinate:
    Comparator<Element> comparator = xCoords.thenComparing(yCoords);
    // erst nach y-Koordinate, dann nach x-Koordinate:
    // Comparator<Element> comparator = yCoords.thenComparing(xCoords);
    Collections.sort(elements, comparator);
}
 

izoards

Bekanntes Mitglied
Wow Danke @mihe7 :)
Habs gerade getestet, sieht schonmal recht gut aus, wobei ich noch folgendes Problem habe:

Sortierung erfolgt erst nach y-Koordinate, dann nach x-Koordinate:
Das Ergebnis ist dann wie folgt:
Java:
Identnummer        (X: 491 Y: 33)
56546684        (X: 789 Y: 33)
Daum            (X: 398 Y: 150)
07.07.2022         (X: 1025 Y: 151)
Bestellnummer:     (X: 509 Y: 266)
12345            (X: 969 Y: 271)
65786654        (X: 1015 Y: 384)
Auftragsnummer:    (X: 546 Y: 389)
Tester            (X: 971 Y: 499)
Name:            (X: 420 Y: 504)
Sonstige        (X: 999 Y: 616)
Notiz:            (X: 414 Y: 617)

Beim Scan von diesem Bild:

scan.PNG

Also Y ist sehr gut sortiert, jedoch X ab Position "Auftragsnummer" nicht mehr.

Ich hätte erwartet, dass der Text "Auftragsnummer" vor der Nr. selbst sortiert wird....(?)
 

Neumi5694

Top Contributor
Der Komparato macht schon das, was er soll. Natürlich kennt hier niemand deinen Code na der Stelle.
Aber wenn du schon glaubst, die Reihenfolge der Comparatoren wäre falsch, dann vertausch sie doch einfach.
 

izoards

Bekanntes Mitglied
Aber wenn du schon glaubst, die Reihenfolge der Comparatoren wäre falsch, dann vertausch sie doch einfach.
Nein, das glaube ich nicht, Y ist ja sauber geordnet. X jedoch nicht.
Hier die der Code:

Java:
private HashMap<Element, String> mapPosToElement = new HashMap<>();
private ArrayList<Element> points = new ArrayList<>();

.addOnSuccessListener(new OnSuccessListener<Text>() {
                            @RequiresApi(api = Build.VERSION_CODES.N)
                            @Override
                            public void onSuccess(Text visionText) {
                                // Task completed successfully
                                // [START_EXCLUDE]
                                // [START get_text]
                                ocrResult.clear();
                                mapPosToElement.clear();
                                mapRectToElement.clear();
                                ocrResultElements.clear();
                                points.clear();
                               for (Text.TextBlock block : visionText.getTextBlocks()) {
                                    Rect boundingBox = block.getBoundingBox();
                                    Point[] cornerPoints = block.getCornerPoints();
                                    String text = block.getText();
                                    ocrResult.add(block.getText());
                                    Log.d("OCR-BLOCK", "Text Block " + text);
                                    Log.d(LOG_TAG, "boundingBox: " + block.getCornerPoints());
                                    Log.d("OCR-BLOCK", "CornerPoints: " + block.getBoundingBox().toString());

                                    for (Text.Line line: block.getLines()) {
                                        Point[] lineCornerPoints = line.getCornerPoints();
                                        Rect lineFrame = line.getBoundingBox();
                                        Log.d("OCR-LINES", "Text Lines " + line.getText());
                                        //Log.d(LOG_TAG, "LineCornerPoints: " + line.getCornerPoints());
                                        Log.d("OCR-LINES", "LineFrame: " + line.getBoundingBox().toString());


                                        for (Text.Element element: line.getElements()) {
                                            Log.d("OCR-ELEMENT", "Text Element " + element.getText());
                                            Point[] elementCornerPoints = element.getCornerPoints();
                                            Rect elementFrame = element.getBoundingBox();
                                            //Element pointElement = new Element(Math.round(element.getBoundingBox().exactCenterX()), Math.round(element.getBoundingBox().exactCenterY()));
                                            int x = elementCornerPoints[0].x;
                                            int y = elementCornerPoints[0].y;
                                            Element pointElement = new Element(x, y);
                                            Log.d("OCR-ELEMENT", "X: " + x + " Y: " + y);
                                            ocrResultElements.add(element.getText());
                                            mapPosToElement.put(pointElement, element.getText());
                                            points.add(pointElement);
                                            Log.d("OCR-ELEMENT", "X-Center: " + pointElement.getX());
                                            Log.d("OCR-ELEMENT", "Y-Center: " + pointElement.getY());


                                        }
                                    }
                                }
                                mProgressDialog.dismiss();
                                sort(points);
                                //showResults();
                                showResultsInDialog(ocrResult, resultUri);
                                // [END get_text]
                                // [END_EXCLUDE]
                            }
                        })
                        .addOnFailureListener(
                                new OnFailureListener() {
                                    @Override
                                    public void onFailure(@NonNull Exception e) {
                                        Log.d(LOG_TAG, "failure" + e.getMessage());

                                        // Task failed with an exception
                                        // ...

                                    }

                                });
        // [END run_detector]
        Log.d(LOG_TAG, "End run_detector");
d


Java:
public class Element {

        int x;
        int y;

        public Element(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }


        public int getY() {
            return y;
        }

    }

Java:
 @RequiresApi(api = Build.VERSION_CODES.N)
    public void sort(ArrayList<Element> elements) {
        Comparator<Element> xCoords = Comparator.comparingInt(Element::getX);
        Comparator<Element> yCoords = Comparator.comparingInt(Element::getY);
        // erst nach x-Koordinate, dann nach y-Koordinate:
        //Comparator<Element> comparator = xCoords.thenComparing(yCoords);
        // erst nach y-Koordinate, dann nach x-Koordinate:
        Comparator<Element> comparator = yCoords.thenComparing(xCoords);
        Collections.sort(elements, comparator);
        for (Element element : elements) {
            Log.d("SORTED", "X: " + element.getX() + " Y: " + element.getY());
            Log.d("SORTED", mapPosToElement.get(element));
        }
    }

Ich sehe den Fehler nicht
 

mihe7

Top Contributor
OK, zwei Dinge:
a) Du musst nicht extra eine Klasse Element verwenden; Du kannst auch direkt mit Point arbeiten. Das Element habe ich nur als Beispiel eingeführt. Statt comparingInt kannst Du auch comparingDouble nehmen.

b) was passiert nach dem Sortieren mit der Liste points?
 

izoards

Bekanntes Mitglied
a) Du musst nicht extra eine Klasse Element verwenden; Du kannst auch direkt mit Point arbeiten. Das Element habe ich nur als Beispiel eingeführt. Statt comparingInt kannst Du auch comparingDouble nehmen.
Das habe ich mir auch gedacht, werde das noch versuchen ohne Klasse Element umzusetzen. Aber eine separate Liste mit Points, welche dann als Key für den Zugriff auf die Hashmap dient, ist schon nötig? Oder könnte man auch direkt die HashMap sortieren?
Denkst Du, dass es daran liegt?

b) was passiert nach dem Sortieren mit der Liste points?
Die Liste points bleibt bestehen, und wird jeweils vor einem neuen OCR Scan gelöscht. (Zeile 11 im Code Schnipsel 1)
Ich verwende die Liste points dann, als Key für den Zugriff auf die HashMap.
 

Neumi5694

Top Contributor
Ich hab den Comparator auf so was angewendet (Klasse mit Namen, x und y), wurde alles sauber nach x aufsteigend sortiert.

Ich denke, du machst es dir etwas zu kompliziert, auf die Map könntest du verzichten, wenn du den Bezugspunkt direkt als Eigenschaft des Elements speicherst. Dann pack diese Elemente in eine Liste und sortier die.
 

izoards

Bekanntes Mitglied
Die Sortierung macht glaube ich folgendes:
Sortieren nach z.B. x falls zwei x - werte gleich sind, werden die y-Werte verglichen und entsprechend sortiert.

Das Problem ist nun, dass selten zwei x-Werte gleich sind.
Was ich nun benötige, ist ein zweiter Vergleich von den x-Werten, welche in einer gewissen Spanne liegen und diese Gruppen dann nochmals nach y - sortieren. Also gruppieren der X-Werte mit einer festgelegten Toleranz, danach diese intern nach Y sortieren.

Wie setzt man so eine Sortierung um?

Code:
Identnummer        (X: 491 Y: 33)
56546684        (X: 789 Y: 33)
Daum            (X: 398 Y: 150)
07.07.2022         (X: 1025 Y: 151)
Bestellnummer:     (X: 509 Y: 266)
12345            (X: 969 Y: 271)
65786654        (X: 1015 Y: 384)
Auftragsnummer:    (X: 546 Y: 389)
Tester            (X: 971 Y: 499)
Name:            (X: 420 Y: 504)
Sonstige        (X: 999 Y: 616)
Notiz:            (X: 414 Y: 617)

Bei dem Beispiel, würde man die Y-Werte mit z.B. einer Toleranz von 10 nehmen und alle gefundenen Elemente danach noch nach X sortieren.
 

izoards

Bekanntes Mitglied
Ich denke, du machst es dir etwas zu kompliziert, auf die Map könntest du verzichten, wenn du den Bezugspunkt direkt als Eigenschaft des Elements speicherst. Dann pack diese Elemente in eine Liste und sortier die.

Ziel wäre es keine separate "Elemente" Klasse zu haben, sondern eine HashMap<Point, String>
Dann diese Map nach X mit Toleranz sortieren. So dass alle X, welche innerhalb der Spannweite liegen als gleich angesehen werden und dann das zweite sortier Kriterium zum Zug kommt, in diesem Falle Y.

Ich glaube für das müsste ich den Comparator überschreiben, richtig?
So dass er nicht natürlich sortiert, sondern nach meinem Kriterium
 

mihe7

Top Contributor
Ich glaube für das müsste ich den Comparator überschreiben, richtig?
Du kannst z. B. das Bild in Blöcke aufteilen und dann z. B. per Lambdaausdruck den Block eines Punkts bestimmen:
Java:
int xBlockSize = 10;
int yBlockSize = 20;
Comparator xCoords = Comparator.comparingInt(point -> ((int) point.getX()) / xBlockSize);
Comparator yCoords = Comparator.comparingInt(point -> ((int) point.getY()) / yBlockSize);
// ...
 

Neumi5694

Top Contributor
Die Sortierung macht glaube ich folgendes:
Sortieren nach z.B. x falls zwei x - werte gleich sind, werden die y-Werte verglichen und entsprechend sortiert.
Wenn ud zuerst nach X und dann nach Y sortieren willst, dann ist das doch genau die Aufgabe ...
Teile die X-Werte doch zum Beispiel einfach mal durch 10, dann hast du deine Spanne.
Dann sind 11 und 13 gleich.
(edit: gerade gesehen, dass mihe das gleiche geschrieben hat)

Alternativ kannst du so was machen:

Java:
boolean treatAsEqual(int a, int b, int tolerance) {
    return Math.abs(a-b) <= tolerance;
}

Comparator<Integer> compi = (a,b) -> treatAsEqual(a,b,tolerance) ? 0 :  Integer.compare(a,b);

Damit kann's dir aber passieren, dass 3 Werte in der selben Gruppe liegen, von denen der niedrigste und der höchste aber nicht in der selben Gruppe landen sollten, beide aber in der selben Gruppe liegen wie der mittlere.
 

izoards

Bekanntes Mitglied
Puuuh...
Du kannst z. B. das Bild in Blöcke aufteilen und dann z. B. per Lambdaausdruck den Block eines Punkts bestimmen:
Das verstehe ich nicht wirklich.
Java:
int xBlockSize = 10;
int yBlockSize = 20;
Comparator xCoords = Comparator.comparingInt(point -> ((int) point.getX()) / xBlockSize);
Comparator yCoords = Comparator.comparingInt(point -> ((int) point.getY()) / yBlockSize);
// ...
Habe @mihe7 's Vorschlag übernommen, bzw. nur auf eine Koordinate angewendet. Und erste Tests scheinen zu funktionieren.
Teile die X-Werte doch zum Beispiel einfach mal durch 10, dann hast du deine Spanne.
Dann sind 11 und 13 gleich.
Leider verstehe ich nicht, wieso "durch 10" rechnen, die Spannweite gibt, damit die Elemente dann als "gleich" angeschaut werden für die compare Methode... Falls Ihr mir das erklären könnt wäre das sehr toll. :)

Java:
boolean treatAsEqual(int a, int b, int tolerance) {
    return Math.abs(a-b) <= tolerance;
}

Comparator<Integer> compi = (a,b) -> treatAsEqual(a,b,tolerance) ? 0 :  Integer.compare(a,b);

Verstehe ich leider auch nicht, aber sowas ähnliches hätte ich versucht in eine eigene compare Logik einzubauen.
Hätte eher erwartet, dass man eine eigene Compare Methode schreibt.

So was wie hier:
Sorting values with tolerance

Aber wieso teilen der X-Werte eine Spannweite gibt, wo dann die X-Werte für den Comparator als gleich angesehen werden, wäre sehr nett, wenn Ihr mir das erklären könntet. 🙏🙏
 

httpdigest

Top Contributor
Aber wieso teilen der X-Werte eine Spannweite gibt, wo dann die X-Werte für den Comparator als gleich angesehen werden, wäre sehr nett, wenn Ihr mir das erklären könntet.
--> Integer-Arithmetik

Java:
int a = 1 / 10;
int b = 4 / 10;
int c = 9 / 10;
// a, b und c haben exakt denselben Wert, nämlich 0
int d = 10 / 10;
int e = 11 / 10;
int f = 19 / 10;
// d, e und f haben exakt denselben Wert, nämlich 1
In Integer-Arithmetik werden einfach Nachkommastellen abgeschnitten. 1/10 ist also nicht 0.1 sondern 0.
 

Neumi5694

Top Contributor
Puuuh...

Das verstehe ich nicht wirklich.

Wenn du mit Gleitkommazahlen arbeitest, wird eine "echte" Division durchgeführt.
Bei Integer gibt's so was nicht, hier gibt es dafür 2 Befehle, meistens als DIV und MOD (für Modulo) bezeichnet.

DIV liefert das ganzzahlige Ergevnis der Division.
MOD (Modulo) liefert den Rest.

Wenn du Code kompilieren lässt, erkennt der Compiler anhand der Datentypen, wofür das "/" Zeichen steht.
Stehlt links und rechts ein Integer, so wird der DIV-Befehl verwendet. Ist eine der beiden Zahlen eine Gleitkommazahl, so wird eine entsprechende Division durchgeführt.

Java:
double d = 13;
var d1 = d / 10;  //d1 == 1.3, double-Wert

int i = 13;
var i1 = i / 10; //i1 == 1, Integer-Wert
var i2 = i % 10;//i2 ==3, Integer-Wert
var i3 = i / 10.0;// i3 == 1.3, double Wert, da "10.0" als Gleitkommazahl behandelt wird, "10d" ginge auch. Der Compiler wandelt i entsprechend vor der Division in einen double-Wert um.
 

izoards

Bekanntes Mitglied
Danke vielmals für die Erklärung @httpdigest & @Neumi5694
Raffiniert :)

Mein Endziel ist es, danach nach Schlüsselwörter mittels Regex die Werte auszulesen.
Also Schlüsselwort Datum sollte dann das Datum rauskommen.

Daher wollte ich die Anordnung und würde dann einen String erstellen, wo dann mittels Regex Ausdrücken die Schlüssel - Werte Paare gefunden werden können.

Ist das das richtige Vorgehen? Oder gäbe es da noch besseres / einfacheres?
 

Neumi5694

Top Contributor
Dat jetzt mit der geographischen Sortierung nichts zu tun, ich würde dafür einen neuen Thread starten.

Aber hier schon mal eine Idee, wie die Parsermethode ausschauen könnte
Ich würde sagen: Eingangswert String, Ausgangswert Optional<Map.Entry<String, Object>> (oder was Vergleichbares, kannst auch ein record anlegen).
Im Key steht drin, welche Property gefunden wurde, im Value der gefundene Wert.
Java:
var aEntry = parseString(aString);;
if (aEntry.isPresent()) {
  var prop = aEntry.get();
  myPoperties.put(prop.getKey(), prop.getValue()).
}
 

izoards

Bekanntes Mitglied
Hallo @Neumi5694 Aber die geographische Sortierung hilft schon, dass die Schlüssel-Werte Paare dann mittels einer Parsermethode gefunden werden können?
Oder wäre das gar nicht nötig?

Ich hätte jetzt aus den geografisch geordneten Elemente einen String zusammengebaut mit einem definierten Trennzeichen und danach die Paare gesucht. Wobei ich dann ja eigentlich auch gar kein Regex mehr benötige, ich könnte dann ja direkt mit dem Trennzeichen arbeiten...

record bzw. Optional<Map.Entry<String, Object>> kenne ich leider noch nicht...


Wie wird denn in deiner Parsermethode der gefundene Wert abgegrenzt? Oder anders gefragt, was wird dort genau durchsucht? Ein String?
 

Neumi5694

Top Contributor
Wenn der Text "Datum" enthalten muss, um ein Datum zu sein, warum ist dann seine Position wichtig?

Wenn du allerdings den Inhaltstyp entsprechend der Position bestimmt, dann klar, dann brauchst du die Position. Dann allerdings sollte die Position nicht über eine Map verknüpft sein, sondern Teil des eingescannten Objekts. Schließlich ist die Information dann ohne die Position unvollständig.
 

izoards

Bekanntes Mitglied
Also ohne Sortierung kriege ich meiner Meinung einfach ein Durcheinander z.B.:

Datum
Bestellnummer:
Auftragsnummer:
07.07.2022
Name:
65786654
Sonstige
12345
Tester
Notiz:

Hier habe ich nun keine Idee, wie ich das Datum, also der Wert (07.07.2022) finde.
Darum dachte ich, dass ich erst sortiere und dann die Extraktion des Datum-wertes (07.07.2022) einfacher ist.
 

Neumi5694

Top Contributor
Ah, 2 getrennte Werte, die zusammen geparst werden müssen, verstehe. Dann sollten die beiden Felder aber auch in ein Objekt rein, ein Tupel aus Key und Content.

Das sollte also erst mal der nächste Schritt sein. Bilde Tupel aus Beschreibung und Inhalt, speichere diese in einer Liste.

... und die Map würde ich wirklich zum Teufel jagen, die Position ist schließlich eine wichtige Information und sollte bei den Daten bleiben.
Damit wird auch dein Code gleich viel übersichtlicher.
Aktuell hast du eine Liste von Strings, eine Liste von Punkten und eine Map, die das Ganze verbindet.
Ohne die Map, hast du eine Liste von Objekten, die als Information einen String samt Position enthalten, alle notwendigen Informationen an einem Ort.

Falls die Positionen nach der Tupelbildung immer noch wichtig sind, dann behalte diese Objekte bei, ansonsten reichen Strings. Löse die Koordinaten erst dann von Inhalt, wenn du sie nicht mehr brauchst


ps: Ein Datum finden wäre übrigens einfach, du müsstest nur mit dem Regex-Matcher über alle Texte fahren, aber das hat sich ja erledigt.
 

izoards

Bekanntes Mitglied
Das sollte also erst mal der nächste Schritt sein. Bilde Tupel aus Beschreibung und Inhalt, speichere diese in einer Liste.
Ist dann Tupel eine Klasse? Oder gibt es sowas bereits von Java?
Sorry, bin da jetzt grad bisschen aus dem Konzept...
So wie ich das verstehe, würde ich jetzt Tupel Objekte aus einer Klasse machen welche Beschreibung und Content halten. Wobei der Content ja zu dieser Zeit noch leer ist. Und diese Objekte in einer Liste speichern.
Oder muss der Content die "Formatierung" angeben? (Bei Datum ja noch möglich, aber bei Fliesstext ja nicht wirklich...)

... und die Map würde ich wirklich zum Teufel jagen, die Position ist schließlich eine wichtige Information und sollte bei den Daten bleiben.
Dann benötige ich hierfür statt eine Map ebenfalls eine eigene Klasse, wo dann der Text und Position gespeichert wird...(?)
Dies kommt dann auch in eine Liste?

Falls die Positionen nach der Tupelbildung immer noch wichtig sind
Was ist eine Tupelbildung? Wäre das so, dass nun die Tupel sich die Formatierung suchen und so den entsprechenden Match machen?

Das Problem ist, dass ich z.B. bei Auftragsnummer nicht weiss, wie diese Formatiert ist, das kann ganz verschieden sein.
Funktioniert denn das noch mit dieser Idee?
 

Neumi5694

Top Contributor
Tupel: Wenn du nur 2 Elemente hast, kannst du Map.Entry nutzen, ansonsten leg dir selbst eine Klasse an, ist eh angenehmer, gut lesbare Begriffe zu haben, anstatt Key und Value,

Und ja, eine einfache Klasse mit Text und Point oder x+y ist ja kein Thema, die Liste der Einträge kannst dann auch direkt sortieren, so wie bisher deine Punkteliste, nur steht der Text dann auch gleich mit dabei, anstatt dass der erst umständlichüber eine Map geholt werden muss.

Tupelbildung: Das musst du ausprogrammieren. Anhand der Position suchst du die 2 Elemente, die zusammengehören, deshalb hast du ja sortiert.
 

izoards

Bekanntes Mitglied
Tupelbildung: Das musst du ausprogrammieren. Anhand der Position suchst du die 2 Elemente, die zusammengehören, deshalb hast du ja sortiert.

Sucht man dann mittels Key-Wörter? Oder nur anhand der Position?
Weil, wenn anhand der Position, hätte ich die Zuweisung ja schon, denn es handelt sich bei mir jeweils um 2 Elemente...
 

izoards

Bekanntes Mitglied
Wenn ud zuerst nach X und dann nach Y sortieren willst, dann ist das doch genau die Aufgabe ...
Teile die X-Werte doch zum Beispiel einfach mal durch 10, dann hast du deine Spanne.
Dann sind 11 und 13 gleich.
(edit: gerade gesehen, dass mihe das gleiche geschrieben hat)

Noch was zum sortieren, mittels teilen und Integer Arithmetik.
Es kommt immer wieder vor, dass Werte sehr nahe beieinander liegen, jedoch die Teilung dann doch gerade am falschen Ort passiert.

z.B. 689 & 702
beim Teilen durch 10, ist das nun halt nicht gleich.

Darum dachte ich zuerst dass es mittels delta zwischen den Werten, also einer Toleranz, besser funktionieren würde...?
Dann würde man die Toleranz angeben, wie weit die Werte auseinandersein dürfen.

Wie müsste das umgesetzt werden?
Oder kann das in die bestehende Variante mit integriert werden?
 

Neumi5694

Top Contributor
Überleg dir einfach, wie du das auf dem Blatt machen würdest. Zeichne dir mal wo was auf, ersetz die eingescannten Objekte durch Rechtecke ohne Inhalt. Reicht das als Information? Kannst du so erkennen, was zusammengehört? Falls ja, dann musst du noch programmieren, was dein Gehirn eben gemacht hat. Anylsiere, was du da eben gemacht hast und drück es in Worten aus. Dann setz diese Worte als Code um. Falls das aber nicht ausreicht, dann musst du den Inhalt ebenfalls analysieren.

Teilen durch 10 war EINE Möglichkeit, Gemeinsamkeiten zu finden. Du kannst z.B. ja auch grober vorgehen (durch 20 etwa). Delta ist auch eine Möglichkeit Wie man so was erechnet, hab ich oben schon gezeigt. Du kannst ja auch die Distanz zwischen Punkten messen (Point.distance).
Und vergiss nicht. Deine elements-Liste hatte auch komplette Rechtecke, nicht nur eine Position, vielleicht helfen dir die mehr weiter als nur x und y.
Da musst du halt probieren, bis was brauchbares rauskommt.

"Integrieren"? Wir reden hier von einer neuen Funktion, die zusammenfasst, was zusammengehört.

Eingang: Liste von eingescannten Objekten. ausgang. Liste von je 2 eingescannten Objekten oder Texten.
 

izoards

Bekanntes Mitglied
Danke vielmals für die Hilfe 🙏

Ich weiss, die Lösung mit der Toleranz würde ich gerne ausprobieren und herausfinden, ob es hier weniger Probleme gibt, denn ich habe schon mit verschiedenen Teiler gearbeitet und es hat immer wieder Überschneidungen gegeben.

Dein Lösungsansatz:

Java:
boolean treatAsEqual(int a, int b, int tolerance) {
    return Math.abs(a-b) <= tolerance;
}

Comparator<Integer> compi = (a,b) -> treatAsEqual(a,b,tolerance) ? 0 :  Integer.compare(a,b);

finde ich sehr spannend, leider weiss ich nicht, wie ich die Liste so filtern kann, denn a und b sind ja jeweils z.B. y-Werte von verschiedenen eingescannten Objekten. Wie kann ich auf diese Zugreifen? Bin hier ziemlich ratlos 🙈 😥
 

Neumi5694

Top Contributor
Warum willst du eine Liste filtern? Hast du das denn auf dem Zettel auch so gemacht?
Was für eine Liste hattest du denn da auf dem Zettel?

Und warum willst du einen Comparator verwenden? Der dient doch nur zum Sortieren.
 

Neumi5694

Top Contributor
Ich möchte, dass du mir mal in Worten beschreibst, woran du erkennst, welche aus einer Menge von 10 Rechtecken zusammengehören. Verwende dabei nicht das Wort "Liste". Welche Kriterien müssen erfüllt sein, damit die Rechtecke zusammengehören?
 

izoards

Bekanntes Mitglied
Ich möchte, dass du mir mal in Worten beschreibst, woran du erkennst, welche aus einer Menge von 10 Rechtecken zusammengehören. Verwende dabei nicht das Wort "Liste". Welche Kriterien müssen erfüllt sein, damit die Rechtecke zusammengehören?

Also auf dem Papier mit Rechtecken würde ich paare suchen, welche dieselben Y-Positionswerte haben.
Dann würde ich die gefundenen Paare noch mit der X-Position in aufsteigender Form sortieren.
Danach wäre dann links der Key und rechts der Value.

Falls es mehrere Paare mit denselben Y Positionswerte gibt, müssten mehrere Paarbildungen gemacht werden. (Ebenfalls wieder mit X-Sortierung)

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

d.h. ich mache nun eine Klasse mit den gescannten Elementen inkl. Position (X, Y) wie Du schon immer sagtest.
Danach suche ich gleiche Y - Werte. Dort muss ich jedoch die Toleranz einbauen. Auf dem Papier sind die Y-Werte nämlich exakt gleich ;-) auf dem scan jedoch nicht...
Danach ist das Paar-Element mit dem kleineren X-Wert der Schlüssel und das andere Element der Wert dazu.





Die Voraussetzung für so ein Scan ist natürlich, dass das Bild immer gleich aufgebaut ist.

(Denke es ist unmöglich, verschiedene "Bilder" (Dokumente) zu scannen, welche irgendwo z.B. "Auftrag: 5465irgendeineNummer" haben und dann dieses zu finden, ohne die Position zu wissen, oder?)
 

izoards

Bekanntes Mitglied
Das ist noch relativ einfach, wenn Du den Scan erstmal als String zur Verfügung hast (Regex).

Zur Zeit mache ich es mit dem Sortieren mit Arithmetik Teilung, das ergibt dann ein String, dort mache ich ein "$" Zeichen als Trennzeichen zwischen den Elementen, das ergibt dann diesen String:

Java:
Betriebsauftrag$7600000000000052123$Kunde$Firma XY$Auftrag$500123$Bestellung$EBO00123$Charge$500/2021$Menge$500 Stk$

Nun splitte ich den String mit dem Trennzeichen $ und lese die ungeraden Elemente aus.
So klappts... aber eben nur meistens, da es den Fall gibt, dass die Arithmetik Teilung trotz naher Y-Werte, die Teilung gerade auf den Teiler fällt.


EDIT: Evt. wäre es am einfachsten, hier einfach noch zu prüfen ob das gerade element tatsächlich dem erwarteten String entspricht, falls nicht, dann ist es der andere 🙃 Vermutlich eine ziemlich gebastelte Lösung..
 

mihe7

Top Contributor
Evtl. lässt sich Dein Vorhaben mit einem Sweep lösen:
  1. Sortiere die Rechtecke aufsteigend nach y-Koordinate und absteigend nach Höhe.
  2. zeile := leer
  3. Für jedes Rechteck r dieser sortierten Rechtecke
    1. Falls zeile leer, füge r zu zeile hinzu und setze minY := r.y, maxY = r.y + r.height,
    2. sonst, falls r.y < maxY, füge r zu zeile hinzu und merke maxY := Math.max(maxY, r.y + r.height)
    3. sonst, sortiere zeile nach x-Koordinate, gib zeile aus und setze zeile := r, minY := r.y, maxY := r.y + r.height
  4. falls zeile nicht leer, sortiere zeile nach x-Koordinate, gib zeile aus.
Könnte evtl. funktionieren. Pseudo-Code (quick & dirty):
Java:
record Element(String text, Rectangle rect) {}
record Row(List<Element> elements) {}

public List<Row> getRows(List<Element> elements) {
    List<Row> rows = new ArrayList<>();
    List<Element> currentRow = new ArrayList<>();
    Collections.sort(elements, Comparator.comparingDouble((Element e) -> e.rect().getY())
            .thenComparing(Comparator.comparingDouble((Element e) -> e.rect().getY() + e.rect().getHeight())));
    int minY = 0, maxY = 0;
    for (Element current : elements) {
        Rectangle rect = current.rect();    
        if (currentRow.isEmpty()) {
            minY = rect.y;
            maxY = rect.y + rect.height;
        } else if (rect.y < maxY) {
            maxY = (int) Math.max(maxY, rect.y + rect.height);
        } else {
            Collections.sort(currentRow, Comparator.comparingDouble(e -> e.rect().getX()));
            rows.add(new Row(currentRow));
            currentRow = new ArrayList<>();
            minY = rect.y;
            maxY = rect.y + rect.height;
        }
        currentRow.add(current);
    }
    return rows;
}
 

Neumi5694

Top Contributor
Cool, wenn du mit der Sortierung eh schon abwechselnd die Bezeichner und Wert rauskriegst, brauchst du danach nur noch die Liste durchgehen und brauchst die Koordinaten nicht weiter zu berücksichtigen.


Ansonsten hätt ich gesagt, such zu einem Rechteck das jeweils nächste, was davon Wert und was Key ist, entscheidet, was weiter links oben liegt (am Besten per Diagonalabstand).

Führ noch einen Maximalabstand zwischen 2 Elementen ein, damit gegebenenfalls einzlene, die fernab vom Rest liegen, nicht mit anderen verbunden werden.
Wurde ein Element als Nachbar eines anderen identifiziert, muss dafür natürlich kein neuer Nachbar gesucht werden, davon abgesehen wird das für alle eingescannten Elemente wiederholt.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
C Laufzeit eines Sortier-Algorithmus ermitteln Java Basics - Anfänger-Themen 4
J Sortier alternativen mit der compareTo Methode? Java Basics - Anfänger-Themen 6
kaoZ Methoden Eigenen Sortier Methode erstellen Java Basics - Anfänger-Themen 5
S Sortier Frage (schleifen HILFE) Java Basics - Anfänger-Themen 6
K Algorithmus entwickeln Java Basics - Anfänger-Themen 1
laxla123 Eigenschaften eines Algorithmus (determiniert vs.. deterministisch) Java Basics - Anfänger-Themen 2
C Gewinnspiel erstellen mit Algorithmus Java Basics - Anfänger-Themen 3
C negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch Java Basics - Anfänger-Themen 10
H Minimax Algorithmus in Tic Tac Toe Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus für Vier gewinnt Java Basics - Anfänger-Themen 11
ohneInformatik; Trockentest Algorithmus, mathematischen Zusammenhang angeben Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus Java Basics - Anfänger-Themen 17
mervanpolat Binary Search Algorithmus ausführen Java Basics - Anfänger-Themen 1
J Rekursiver Algorithmus Java Basics - Anfänger-Themen 9
M monte carlo Algorithmus für 4 gewinnt Java Basics - Anfänger-Themen 12
S Algorithmus entwicklen, der zu einem gegebenen Datum die Jahreszeit ermittelt Java Basics - Anfänger-Themen 13
rosima26 Merge-Algorithmus Java Basics - Anfänger-Themen 53
C Ein Algorithmus soll schneller werden Java Basics - Anfänger-Themen 24
D Dijkstra Algorithmus Hilfe!! Java Basics - Anfänger-Themen 9
U Den Kuchen aufteilen - aber wie? (Rebalancing-Algorithmus) Java Basics - Anfänger-Themen 14
s_1895 Pseudocode Naiver Algorithmus Java Basics - Anfänger-Themen 17
H String verschlüsseln - eigener Algorithmus Java Basics - Anfänger-Themen 104
T Algorithmus für Index mit min-Wert Java Basics - Anfänger-Themen 2
Düsseldorf2002 Testen meines Algorithmus Java Basics - Anfänger-Themen 1
D Primzahlen Rechner nach Eratostenes von Kyrene Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Algorithmus java searchAll IKey Java Basics - Anfänger-Themen 4
S Algorithmus Datensätze einfügen wenn... Java Basics - Anfänger-Themen 26
KogoroMori21 MergeSort Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Textdatei einlesen im Array (Selection Sort Algorithmus) Java Basics - Anfänger-Themen 3
fendix Compiler-Fehler Algorithmus zur Bestimmung von Primzahlen Java Basics - Anfänger-Themen 7
S Algorithmus (reelle Zahl <65536 von dezimal zu dual) max. 10 Nachkommastellen Java Basics - Anfänger-Themen 4
G Algorithmus Graphen Java Basics - Anfänger-Themen 10
D Input/Output fehlerhafter Algorithmus zum Ersetzen von Array-Werten nach logischem Schema Java Basics - Anfänger-Themen 1
N Selection Algorithmus: Methode wird nicht erkannt (BlueJ) Java Basics - Anfänger-Themen 3
U Meinung zum Dijkstra Algorithmus Java Basics - Anfänger-Themen 6
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
L Math.exp also eigenen Algorithmus Java Basics - Anfänger-Themen 2
Kirby.exe Algorithmus entwickeln Java Basics - Anfänger-Themen 37
M Algorithmus Max-Heap? Java Basics - Anfänger-Themen 3
I Labyrinth auf der Basis eines rekursiven Algorithmus Java Basics - Anfänger-Themen 27
CptK Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
A Algorithmus effizienter machen Java Basics - Anfänger-Themen 1
V Algorithmus zur fortlaufenden Berechnung des duechscjnt Java Basics - Anfänger-Themen 1
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
O Labyrinth Algorithmus Java Basics - Anfänger-Themen 3
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
D Algorithmus in Pseudocode mit log2(n) Operationen erstellen Java Basics - Anfänger-Themen 3
H aufgabe java luhn algorithmus Java Basics - Anfänger-Themen 10
A Datenstruktur für Savings Algorithmus und Planung von kleinen Programmierprojekten Java Basics - Anfänger-Themen 1
J Algorithmus für eine Reihe implementieren Java Basics - Anfänger-Themen 2
S Dijkstra Algorithmus funktioniert nicht Java Basics - Anfänger-Themen 4
N Denksportaufgabe durch Algorithmus lösen Java Basics - Anfänger-Themen 2
S Problem mit einem rekursivem FloodFill Algorithmus Java Basics - Anfänger-Themen 62
B Algorithmus Square und Multiply Java Basics - Anfänger-Themen 3
J Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen Java Basics - Anfänger-Themen 4
D Frage Boyer-Moore Algorithmus Java Basics - Anfänger-Themen 7
M Komplexität Algorithmus Java Basics - Anfänger-Themen 8
H Zeichen im algorithmus Java Basics - Anfänger-Themen 4
B Code Verständnisfragen - FLoyd Warshall Algorithmus Java Basics - Anfänger-Themen 1
B Algorithmus zum entmischen einer Zahlenfolge Java Basics - Anfänger-Themen 15
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
T Algorithmus zur Überprüfung eines binären Suchbaums Java Basics - Anfänger-Themen 2
K Best Practice Algorithmus für Berechnung von Zahlenreihenfolge Java Basics - Anfänger-Themen 12
M Simpler Algorithmus läuft extrem langsam. Java Basics - Anfänger-Themen 3
K Erste Schritte Brute Force Algorithmus Java Basics - Anfänger-Themen 2
L Frage zu BubbleSort Algorithmus Java Basics - Anfänger-Themen 2
B gibt es ein Stundenplan-Algorithmus? Java Basics - Anfänger-Themen 11
O Algorithmus-Problem Java Basics - Anfänger-Themen 5
P Euklidischer Algorithmus Java Basics - Anfänger-Themen 9
L Greates Commong Dividend - euklidischer Algorithmus, modulos not positive Java Basics - Anfänger-Themen 5
J Euklidischer Algorithmus Java Basics - Anfänger-Themen 1
S Quicksort Algorithmus Java Basics - Anfänger-Themen 2
S GraphNode --- Dijkstra Algorithmus : NullPointerException Java Basics - Anfänger-Themen 1
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
V Algorithmus in einer Methode ausführen Java Basics - Anfänger-Themen 3
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
M Dijkstras Algorithmus Java Basics - Anfänger-Themen 5
S Zusammenhang Datenstruktur/Algorithmus Java Basics - Anfänger-Themen 1
M Simulation - Algorithmus Java Basics - Anfänger-Themen 3
F Erste Schritte Hilfe beim Algorithmus finden Java Basics - Anfänger-Themen 8
D Algorithmus für Punkte auf einem Kreis Java Basics - Anfänger-Themen 0
D Algorithmus zu gegebener Laufzeit implementieren Java Basics - Anfänger-Themen 1
B Doppelte Werte aus Array entfernen ohne Import - Algorithmus Java Basics - Anfänger-Themen 5
C Ideen für einen Algorithmus Java Basics - Anfänger-Themen 1
F Best Practice Algorithmus optimieren - Binaeruhr Java Basics - Anfänger-Themen 2
S Euklid Algorithmus zur Berechnung des GGTs Java Basics - Anfänger-Themen 2
L Welcher Algorithmus ist das ? Java Basics - Anfänger-Themen 9
J Rekursiver Horner-Schema-Algorithmus - Verstehe ich ihn richtig? Java Basics - Anfänger-Themen 2
O Java Zufalls-Verteil-Algorithmus Java Basics - Anfänger-Themen 3
P ganz simpler algorithmus Java Basics - Anfänger-Themen 3
C Sortieren ohne Algorithmus Java Basics - Anfänger-Themen 8
J Algorithmus: Grad von floating zu Grad/Minute/Sekunde Java Basics - Anfänger-Themen 3
A Text Verschriebung/Algorithmus(?) Java Basics - Anfänger-Themen 8
R Rekursionsformel für Laufzeit von Algorithmus Java Basics - Anfänger-Themen 3
E Algorithmus für kart. Produkt: als int [] Feld repräsentiert Java Basics - Anfänger-Themen 10
U Peterson Algorithmus Java Basics - Anfänger-Themen 13
algebraiker Collections Bräuchte Hilfe bei dem Algorithmus - LinkedHashMap Java Basics - Anfänger-Themen 2
S A* Path Algorithmus in Java schon vorhanden Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben