Was ist eine gute Datenstruktur zum speichern und suchen in 2d-Koordinaten in Java
Ich bin derzeit am schreiben eines plugins für ein Spiel wo die eine Funktion beinhaltet die Möglichkeit, definierte Bereiche durch 2 zweidimensionale Koordinaten Der linken oberen und der rechten unteren Bereichen eines Rechtecks). Diese Regionen werden dann gespeichert werden, und haben verschiedene andere Daten im Zusammenhang mit der jeweiligen region. Der Spieler bewegt sich über die Welt, die ich brauche, um zu bestimmen, wenn er in einer dieser Regionen, von der nur die Koordinaten des Spielers, und die Methode, dies zu tun, müssen effizient sein, wie das am Ende wird aufgerufen, Hunderte Male pro Sekunde.
Gibt es irgendwelche Datenstrukturen effizient unterstützen diese Art der Suche, und wenn ja, wo finde ich Unterlagen über ihn zu finden Sie entweder eine java-Implementierung zu verwenden, oder, falls erforderlich, implementieren Sie es selbst?
Ich möchte auch betonen, ich fand ein paar Baum-Strukturen, die nur zu unterstützen schien, bulk-loading, aber ich muss in der Lage sein, um das hinzufügen und entfernen von Werten aus dieser Struktur in Echtzeit.
- Siehe auch diese answer.
- Wie viele Rechtecke? Tun Rechtecke ändern sich Häufig? Alle performance-Anforderungen für das hinzufügen / entfernen von Rechtecken?
- Rechtecke werden nicht geändert sondern nur Hinzugefügt und entfernt, und da diese auf einem server ausgeführt wird, wird es brauchen, zu behandeln, die mindestens ein paar Einfügungen pro Sekunde, ohne zu verletzen Leistung der server, obwohl im Durchschnitt kann nur aufgerufen werden, einmal in der minute.
- Ich muss in der Lage sein zu suchen, den Raum effizient, obwohl, nicht nur festzustellen, ob die Form enthalten ist oder nicht, das ist schon trivial, aber erschöpfend Suche durch eine Liste von tausenden oder mehr Formen um zu sehen, ob es enthält, ist nicht effizient.
- Können Sie genauer sein als Tausende oder mehr? 10000? 100000? 1000000?
- Ich würde erwarten, dass wahrscheinlich entlang der Linien von 1-10k Regionen im Raum zu einer bestimmten Zeit.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einen guten datastructure für die Bestimmung Kollision in einem Teil des Raumes ist die quad-Baum datastructure. Der quad-tree rekursiv teilt einen Raum entsprechend der Anzahl der Elemente in einem gegebenen Gebiet. So kann es eine Suche, wenn die Koordinaten sich innerhalb einer region in logarithmischer Zeit.
EDIT: ich habe gefunden eine Implementierung hier, aber keine Lizenz Informationen gegeben werden.
Im eindimensionalen Fall, eine geeignete Datenstruktur ist die Intervall-Baum.
Zur Lösung der zwei-dimensionalen cast, können Sie entweder ein Intervall-Baum schnell zu finden, diese Rechtecke an, die den Punkt in mindestens einer dimension, und überprüfen Sie die zweite dimension für jede von Ihnen (die vielleicht schon schnell genug), oder verwenden Sie die Verallgemeinerungen zum vielen Dimensionen der Wikipedia-Artikel Skizzen kurz (obwohl ich zugeben muss, dass ich nicht verstehen, dass die Verallgemeinerung auf die erste gelesen).
Vorausgesetzt, der Spieler bewegt sich langsam (D. H. die Anzahl der region betreten oder verlassen, die Ereignisse, die klein ist im Vergleich zu der Anzahl der Regionen) die folgende Vorgehensweise kann effizienter sein: Halten Sie ein such-Baum der x-Koordinaten, wo Rechtecke beginnen oder enden, und einen ähnlichen Baum für den y-Koordinaten. Wenn ein Spieler betritt oder eine region verlässt, muss er überquerte die x-oder die y-Koordinate der Grenze zeigen. Das heißt, Sie würde eine range-query auf die x-Suchbaum für den Bereich [old_x, new_x], und prüfen Sie jedes dieser Rechtecke. Machen Sie dasselbe für die y-Richtung (nicht-Berichterstattung Duplikate).
Umzusetzen Koordinaten, die Sie verwenden können, Point2D in einer Klasse implementiert die Funktionalität, die Sie suchen:
http://download.oracle.com/javase/6/docs/api/java/awt/geom/Point2D.html