Doppelte objekte entfernen.
lima-city → Forum → Programmiersprachen → Java
berechnen
code
double
duplikat
http
koordinate
liegen
liste
methode
objekt
paar
point
private double
problem
punkt
schnittpunkt
set
string
system
url
-
Bei einer Schnittpunktberechnung kann es manchmal vorkommen, dass einige Schnittpunkte übereinander liegen. Das heißt es befinden sich Schnittpunkt-Objekte mit den gleichen x/y-Koordinaten in einer Liste.
Hab versucht die Duplikate über den HasSet aus meiner Liste zu entfernen, aber irgendwie gibt das Teil immer alles genauso zurück.
HashSet<Point> hashSet = new HashSet<Point>(intersections); intersections.clear(); intersections.addAll(hashSet);
Das Punkt Objekt speichert nur eine x und y Koordinate. Hab mir probehalber 3 Schnittpunkte übereinander berechnen lassen, zb 3 Mal ein Point- Objekt mit der Koordinate(100.0, 100.0), aber dieses Hash set, scheint wohl nicht zu verstehen, dass es gleiche Objekte sind.
Weiß leider nicht, wie das Problem zu lösen ist.
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Moin,
ich weiß nur, dass Sets Probleme bereiten, wenn die Objekte nicht immutable sind. Wie schaut das denn bei Deinem Point-Objekt aus?
Du weist dem HashSet die intersections direkt zu, wie ich das sehe. Du könntest mal durchiterieren um zu sehen, ob das einen Unterschied machen würde.
Gruß,
Pawnee
-
Moin, die Punkt Klasse ist eigentlich sehr schlicht, weiß gar nicht ob sie immutable ist.
public class Point { private double x; private double y; public Point(double x, double y) { this.x = x; this.y = y; } public double getX() { return x; } public double getY() { return y; } }
Hab es gerade auch mit durchiterieren probiert
HashSet<Point> hashSet = new HashSet<Point>(); for(Point intersection : intersections) { hashSet.add(intersection); } intersections.clear(); intersections.addAll(hashSet); for(Point intersection : intersections) { System.out.println("Intersection at: ["+intersection.getX()+"] ["+intersection.getY()+"]"); }
Ergebnis:
Intersection at: [241.4213562373095] [241.4213562373095]
Intersection at: [241.4213562373095] [241.4213562373095]
Intersection at: [241.4213562373095] [241.4213562373095]
Notfalls würde ich mit BruteForce jeden Schnittpunkt mit jedem vergleichen, aber ich möchte wegen dem Aufwand lieber kein BruteForce benutzen. Leider liegen die Schnittpunkte unsortiert in der Liste vor, man kann auch nicht einfach die benachbarten Punkte vergleichen. Wie würdet ihr denn in diesem Fall vorgehen :) -
Deine Objekte wären immutable, wenn alle Felder final sind, so dass man das Objekt nicht mehr durch seine Eigenschaften ändern kann.
Eine HashSet versucht anhand des Inhaltes eines Objekts einen Hash-Wert zu berechnen und vergleicht diesen Hashwert dann mit allen anderen Einträgen in dem HashSet (vermutlich mit einem hierarchischem Verfahren).
Sollte sich ein Objekt in einem HashSet ändern, wird trotzdem noch der alte HashWert für den Vergleich verwendet. Und das will man natürlich nicht.
Du kannst für deine Klasse auch eine Methode hashCode() mit Rückgabetyp int definieren, die möglichst effizient ist. Dann verwendet die Hash-Map automatisch diese Methode und das ganze geht dann auch schneller.
edit: Um auch deinen Code zurückzukommen:
Welche Klasse hat intersections?
Warum arbeitest du nicht jetzt einfach mit dem HashSet weiter?
Beitrag zuletzt geändert: 29.5.2012 17:30:59 von bladehunter -
Hallo pixilab,
da ich ein ziemlich fauler Mensch bin würde ich die Intersections einfach in ein ArrayList packen, sortieren und dann von hinten nach vorne die Duplikate eliminieren.
Nachdem Du aber Intersections hast stellt sich mir die Frage, woher die eigentlich kommen. Da sie offensichtlich keiner Sortierung unterliegen klingt das so als ob Du per Brute-Force (alles mit allem schneiden) die Schnittpunkte zwischen Strecken berechnen lässt.
Wenn Du etwas mehr Zeit hast und deine Performance optimieren willst, dann kannst Du Dir ja mal den Bentley-Ottmann Algorithmus anschauen.
Hier ist auch ein funktionierendes Beispiel dazu:
http://www.cs.uwaterloo.ca/~bjlafren/segint/index.htm
Allerdings ist das leider nicht ganz einfach. Die doppelten Einträge ließen sich dabei aber ziemlich einfach vermeiden. -
bladehunter schrieb:
edit: Um auch deinen Code zurückzukommen:
Welche Klasse hat intersections?
Warum arbeitest du nicht jetzt einfach mit dem HashSet weiter?
Die Intersections sind einfache Point-Objekte sie liegen in der gleichen Klasse, wo ich auch versuche die Dublikate wegzubekommen.
Die Schnittpunkte liegen in einer ArrayList.
Würde gerne HashSet benutzen, aber das will leider noch nicht so richtig klappen. Das hat aber auch nicht unbedingt mit meinem Code drum herum zu tun. Bereits dieses einfache Beispiel funktioniert nicht.
Hab auch wie vorgeschlagen die hashCode Methode in meiner Point-Klasse implementiert.
public class Point { private double x; private double y; private int hashCode; public Point(double x, double y) { this.x = x; this.y = y; this.hashCode = (int) Math.round(this.x * this.y * 1000); } public int hashCode() { return this.hashCode; } public double getX() { return x; } public double getY() { return y; } }
Von dieser Klasse werden 3 Testobjekte erstellt und mit HashSet ausgeführt.
List<Point> points = new ArrayList<Point>(); points.add(new Point(100, 100)); points.add(new Point(100, 200)); points.add(new Point(100, 100)); HashSet<Point> hashSet = new HashSet<Point>(points); for(Point intersection : hashSet) { System.out.println("Intersection at: ["+intersection.getX()+"] ["+intersection.getY()+"] Hashcode: "+intersection.hashCode()); }
Ergebnis:
Intersection at: [100.0] [200.0] Hashcode: 20000000
Intersection at: [100.0] [100.0] Hashcode: 10000000
Intersection at: [100.0] [100.0] Hashcode: 10000000
Muss man vielleicht in der Pointklasse explizit HasSet oder sowas implementieren? -
Moin pixilab,
Du musst noch explizit die equals-Methode in der Point-Klasse implementieren:
@Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final Point other = (Point) obj; if (this.hashCode != other.hashCode) { return false; } return true; }
Dann sollte es eigentlich keine Probleme mehr geben.
Das HashSet scheint nicht nur auf hashCode zuzugreifen, sondern verwendet auch jene Methode.
Gruß,
Pawnee
Beitrag zuletzt geändert: 29.5.2012 23:28:55 von pawnee -
Da Pawnee die Lösung gefunden hat, hier noch ein paar Anmerkungen:
pixilab schrieb:
Hab auch wie vorgeschlagen die hashCode Methode in meiner Point-Klasse implementiert.
So wie du das notiert hast
this.hashCode = (int) Math.round(this.x * this.y * 1000);
ist das aber keine Methode. Das ist ein Feld.
public hashCode() { return this.x + this.y * 1000; }
wäre eine Methode. Außerdem ist es wichtig dass eine Hashfunktion eindeutige Werte zurückliefert. Wenn du die beiden Punkte (1,2) und (2,1) hast, so haben sie nach deiner Formel x*y*1000 den gleichen Hash-Wert. Das sollte vermieden werden.
Muss man vielleicht in der Pointklasse explizit HasSet oder sowas implementieren?
Definitiv nicht. Die Methode hashValue wird von der Klasse "Object" geerbt (die Wurzel der Klassenhierarchie). Und diese Methode kannst du überschreiben.
Beitrag zuletzt geändert: 29.5.2012 23:56:06 von bladehunter -
Ich werd verrückt, das klappt mit der equals Klasse
Mal wieder was neues gelernt. Danke, ohne euch würde ich noch Wochen dran tüfteln
Hatte schon damit begonnen eine eigene Methode zu schreiben, die nach benachbarten Duplikaten sucht. Findet den größten Teil aller Duplikate, die HashSet Lösung, dagegen alle :) Frag mich was die Suche für einen Aufwand hat. O(n^2) glaub nicht, dafür geht es ziemlich schnell. -
Kann dir auch erklären warum: Wenn du zwei Point-Objekte mit gleichen Koordinaten hast, sind das immer noch unterschiedliche Objekte. Wenn du jetzt die equals-Methode überschreibst, gibst du explizit an, wann diese unterschiedlichen Objekte als gleich behandelt und damit in einem Set auch nur einmal gespeichert werden sollen.
-
Nochmal im Schnelldurchlauf - ich habe den Eindruck, hier ist einiges an solidem Halbwissen am Start (sorry, no offense
):
Ein HashSet erkennt gleiche Elemente mit Hilfe der equals()-Methode der Elementklasse. Wenn man die nicht selbst schreibt, wird die entsprechende Methode von Object geerbt, die die Referenzen im Speicher vergleicht (das gleiche, was man auch mit "==" überprüfen würde). Wenn man jetzt mit "new" zwei Point-Objekte erzeugt, sind die für die equals()-Methode von Object immer unterschiedlich - auch wenn x und y tatsächlich gleich sind.
Das wird vielleicht anhand eines kleinen String-Beispiels deutlicher:
String a = "foo"; String b = "foo"; // Hier greift Java intern auf das bereits existierende Objekt zurück. String c = new String("foo"); // Hier wird explizit ein neues Objekt erzeugt. System.out.println(a == b); // true System.out.println(a == c); // false System.out.println(a.equals(c)); // true
Die equals()-Methode von pawnee ist so gesehen übrigens falsch, da eigentlich x und y unabhängig voneinander geprüft werden müssten und man mit der aktuellen Implementierung nicht auf den hashCode zurückgreifen darf. Mit
undhashCode = x + y * 1000
wären z.B. die Punkte (1000, 0) und (0, 1) für das HashSet identisch.if (this.hashCode != other.hashCode) { return false; } return true;
Für die equals()-Methode gelten zudem ein paar zusätzliche Einschränkungen, vielleicht aus der Mathematik bekannt:
- Wenn a gleich b ist, dann muss auch b gleich a sein,
- Wenn a gleich b ist und b gleich c ist, dann muss auch a gleich c sein und
- a muss gleich a sein
Klingt nicht sonderlich kompliziert, kann aber schon durch eine falsche Überprüfung schiefgehen - Details liefert Google.
Die hashCode()-Methode ist in dem Zusammenhang relevant, weil das HashSet aus Performancegründen zuerst mit dem HashCode nach einem Objekt sucht. Deshalb müssen gleiche Objekte auch zwingend den gleichen HashCode haben. Dafür wäre
eine völlig valide Implementierung. Unterschiedliche HashCodes sind in erster Linie im Hinblick auf Performanceoptimierungen relevant - was im Normalfall aber eher unnötig ist.public int hashCode() { return 0; }
Vielleicht interessant zum Selbstudium: http://www.java-blog-buch.de/040311-besondere-methoden-equals-hashcode-und-tostring/ -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
