Datenstruktur/Algorithmus nächster Punkt?

[PatkIllA]

Ich möchte in einer C# Anwendung beim Bewegen des Mauszeigers aus einer Koordinatenmenge (zweidimensional, mehrere tausend bis wenige zehntausende) den jeweils nächsten Punkt finden.
Der maximal zulässige Abstand ist dabei vorgegeben, kann sich aber nach dem Einsammeln der Punkte noch verändern.
Was für Datenstrukturen/Algorithmen würdet ihr da empfehlen?

[RLZ]

Nearest Neighbour über Quadtree.

[Bietchiebatchie]

Was für Datenstrukturen/Algorithmen würdet ihr da empfehlen?
Gar keine.
Solange es wenige zehntausende Punkte sind kannst du einfach jedes Mal alle Punkte durchiterieren. Auch bei 100 Abfragen in der Sekunde wird die App wahrscheinlich immer noch mehr als 90% der Zeit rumidlen.

[Monger]

Nearest Neighbour über Quadtree.
Sorry wenn ich jetzt mal so dämlich frage, aber: der Quadtree muss doch für jeden einzelnen Punkt aufgebaut werden, oder etwa nicht? Das wären eine Menge Quadtrees.


@topic: ist denn deine Koordinatenmenge variabel, oder nur der maximal zulässige Abstand? Und wenn ja, wie häufig ändert sie sich? Kann es sein, dass von einer Abfrage zur nächsten die Koordinatenmenge komplett anders aussieht, oder bleibt sie eher statisch?

[PatkIllA]

Sorry wenn ich jetzt mal so dämlich frage, aber: der Quadtree muss doch für jeden einzelnen Punkt aufgebaut werden, oder etwa nicht? Das wären eine Menge Quadtrees.
Die Punkte sind die Blätter des Trees. Wäre Also ein Baum. Man könnte auch so Mischformnen machen, wo die Tiefe einen bestimmten Wert nicht überschreitet und dann einfach eine Liste von Punkten verglichen wird.
An die Variante von Bietchiebatchie einfach gar nichts zu machen habe ich aber auch schon gedacht.

@topic: ist denn deine Koordinatenmenge variabel, oder nur der maximal zulässige Abstand? Und wenn ja, wie häufig ändert sie sich? Kann es sein, dass von einer Abfrage zur nächsten die Koordinatenmenge komplett anders aussieht, oder bleibt sie eher statisch?Ist beides variabel. Ändert sich aber beides eher selten im Vergleich zum Test bei Mausbewegung. Die Koordinatenmenge ändert sich wenn ein anderer Kartenausschnitt gewählt wird und den Abstand stellt der Benutzer ein.

[pest]

ich würde eine Hashlist nehmen, und dort die Punkte direkt mit ihrem Abstand einsortieren

[PatkIllA]

ich würde eine Hashlist nehmen, und dort die Punkte direkt mit ihrem Abstand einsortierenAbstand wozu?

[pest]

der zweite Teilsatz war in meinem Kopf schon gestrichen, habe ihn aber dennoch aufgeschrieben :>

[Monger]

Dann schließe ich mich Bietchiebatchie an: versuch es erstmal mit nackter Gewalt, und schau dann wie flott die Sache ist.

Die Idee mit dem Quadtree leuchtet mir nach wie vor nicht ein, weil sobald ich den Mauszeiger bewege, ändert sich doch die Wurzel des Trees, oder etwa nicht? Und damit muss auch der gesamte Tree wieder neu aufgebaut werden.

Wenn alles variabel ist, nützt cachen halt auch nix, bzw. ist eher kontraproduktiv. Da bist du mehr mit der Pflege der gespeicherten Daten beschäftigt, als mit der eigentlichen Berechnung.

Da lohnt es sich wahrscheinlich eher, an anderer Stelle anzusetzen. Zum Beispiel könntest du die Zahl der Neuberechnungen drastisch reduzieren, wenn du eben nicht bei jeder Pixelveränderung des Mauszeigers neu berechnest, sondern entweder beim Maus-"Hover", oder es mit einer Zeitgrenze kombinieren. Es reicht völlig aus, wenn die Zahlen erst nach einer Zehntelsekunde aktualisieren.

[PatkIllA]

Die Wurzel des Quadtrees wäre die gesamte dargestellte Fläche und die Kinder jeweils ein Viertel des Bildschirm. Je nach Mauszeigerposition weiß man dann in welchem der Kinder man suchen muss. Wegend er Sache mit dem maximalen Abstand muss man evtl. mehrere Kinder durchsuchen.

[Monger]

*Klatsch*
Args, Dummheit!

Ja, okay, habs verstanden! :D

[pest]

jetzt ist es mir wieder eingefallen, also entweder ne hashlist, oder ne linked list was imo besser ist, da man bei der hashlist vielleicht nicht alle punkte erwischt wenn man den schlüssel ungünstig wählt

einsortiert wird anhand des abstandes zum vorgänger innerhalb der liste

[Tesseract]

Ich möchte in einer C# Anwendung beim Bewegen des Mauszeigers aus einer Koordinatenmenge (zweidimensional, mehrere tausend bis wenige zehntausende) den jeweils nächsten Punkt finden.

wie ist dieser satz zu verstehen? welcher punkt ist der "nächste"? der nächstgelegene? der nächstgelegene in richtung der mauszeigerbewegung? kann ein punkt in der iteration mehrfach ausgewählt werden? soll das so eine art TSP werden oder soll frei navigiert werden können?

[PatkIllA]

wie ist dieser satz zu verstehen? welcher punkt ist der "nächste"? der nächstgelegene? der nächstgelegene in richtung der mauszeigerbewegung? kann ein punkt in der iteration mehrfach ausgewählt werden? soll das so eine art TSP werden oder soll frei navigiert werden können?
Einfach nur der nächstgelegene Punkt zum Mauszeigerposition. Die Richtung der Bewegung spielt keine Rolle. Immer nur maximal ein Punkt als Ergebnis. Kein Ergebnis, wenn der nächstgelegene Punkt den Maximalabstand überschreitet.
jetzt ist es mir wieder eingefallen, also entweder ne hashlist, oder ne linked list was imo besser ist, da man bei der hashlist vielleicht nicht alle punkte erwischt wenn man den schlüssel ungünstig wählt

einsortiert wird anhand des abstandes zum vorgänger innerhalb der liste
da kann ich dir nicht folgen.

[Tesseract]

Einfach nur der nächstgelegene Punkt zum Mauszeigerposition. Die Richtung der Bewegung spielt keine Rolle. Immer nur maximal ein Punkt als Ergebnis. Kein Ergebnis, wenn der nächstgelegene Punkt den Maximalabstand überschreitet.

achso, du willst nur den nächsten punkt zum mauszeiger ohne irgendein gedächtnis.

dann sollte der vorschlag mit dem quadtree bei dieser größenordnung schon eine mögliche ideallösung sein.

[pest]

da kann ich dir nicht folgen.

wenn du z.b. einen max radius von <100px hast, kannst du die hunderter-position als hash-schlüssel nehmen, innerhalb eines hash-schlüssels legst
du eine linked list an, in dem jeder pixel minimalen abstand zu seinen nachbarn besitzt, durch die liste kannst du dich dann durchhangeln.

damit hast du einen table-lookup und ein paar zeiger-operationen um den pixel zu finden

[Gnafoo]

Die einfache Alternative zum Quadtree wäre eine Unterteilung des Feldes in eine Matrix von größeren Zellen, die jeweils die enthaltenen Punkte in Listen speichern. Solange die Verteilung der Punkte etwa gleichmäßig ist und die Anzahl nicht sehr stark schwankt müsste das ganz gut gehen.

[RLZ]

Die einfache Alternative zum Quadtree wäre eine Unterteilung des Feldes in eine Matrix von größeren Zellen, die jeweils die enthaltenen Punkte in Listen speichern. Solange die Verteilung der Punkte etwa gleichmäßig ist und die Anzahl nicht sehr stark schwankt müsste das ganz gut gehen.

Falls man eine gleichmäßige Verteilung hat, ist das natürlich ein gangbarer Weg.
Wenn die Zeit dafür da ist würde ich trotzdem empfehlen einen Quadtree dafür zu implementieren. Sowas macht in einer Programmiersprache einmal generisch und brauch sich in Zukunft keine Gedanken mehr über ein solches häufig auftretendes Standardproblem zu machen.

[Coda]

Oder ne BVH. Ist meistens effizienter.

[Gast]

BVH auf Punkmengen?? Und effizienter ??
BVH verwendet man eigentlich bei Flächenobjekten oder Volumenobjekten,
z.B. bei Raytracing oÄ.

Ein generischer Quadtree-Algo hat Komplexität O(n*log(n)), was ja
wohl kaum zu übertreffen ist ;)

Beim Einpflegen der Punkte muss nur darauf geachtet werden, dass der
Baum immer auftariert ist (z.B. durch Zähler auf Wurzelebene für alle 4
Quadranten). Einpfegen dauert dann O(n Log n) für n Punkte und
O(log n) für einen NextNeighbour-Test.

[Coda]

BVH auf Punkmengen?? Und effizienter ??
Ja. Ein Quadtree ist viel tiefer wenn man lokale Cluster hat.

Ein generischer Quadtree-Algo hat Komplexität O(n*log(n)), was ja
wohl kaum zu übertreffen ist ;)
Was ist O(n*log(n))?

Abgesehen davon ist das Laufzeitverhalten einer BVH exakt gleich, wenn man feste Split-Planes nimmt. Dann ist allerdings der Vorteil von oben nicht mehr gegeben. Man hat aber trotzdem oft engere Bounding Volumes.

[Gast]

Was ist O(n*log(n))?


Ist eine Komplexitätsklasse, wenn ein Algorithmus in O(Ausdruck) liegt dann bedeutet das er höchstens so Aufwendig ist wie O(Ausdruck), bezogen auf Rechen- (oder Speicher-) Aufwand.

http://de.wikipedia.org/wiki/Komplexitätstheorie

[Coda]

Ich weiß was die O-Notation bedeutet :rolleyes:

Was an einem Octree ist deiner Meinung nach O(n log n)? Insert? Update? Search?

Insert eines Wertes ist jedenfalls O(n) und nicht O(n log n).

[Gast]

Sicherlich findet man in Wiki passende Algos, meine Quelle ist Berg et Al.
"Computational Geometrie", Shamos/Preparata tuts aber sicherlich auch:

Balanzieren: O(d*n) (kompletter Baum, d: Tiefe, n: Anz.Knoten)
Einfügen : O(log(n)) (mit UND ohne Ausbalanzierung)
Suche : O(log(n)) (FALLS balanziert, sonst O(d), d: Tiefe)

Wird beim Einfügen ausbalanziert, erhöht sich natürlich der Aufwand um eine Konstante..

Mein O(n*log(n)) bezog sich auf das gesamte BigBang-Szenario: Punktmenge
ändert sich ständig zwischen den Suchvorgängen.

Die von dir angesprochene Tiefe ändert in der Analyse nur die Log-Basis,
was aber in der Komplexität nur eine Konstante ausmacht. Unter O(log(n))
fürs Einfügen/Suchen geht's im Allg. nicht.


Nebenbei bemerkt: meine Anmerkung bezog sich bis jetzt nur auf die
Komplexität, nicht auf die Spezifikation: Gesucht werden soll ja der
nächste Punkt, und den findet man nur durch entsprechende
Datenstrukturen wie z.B. Voronoi-Diagramme (ein Quadtree oder BVH etc.
hilft hier überhaupt nichts). Diese können entsprechend trianguliert (auch
in O(n*log(n)) gesamt und O(log(n) für Insert) und in Baumform dargestellt
werden (<= Delaunay, durch z.B. Quadtree, BVH dargestellt).


Merry XMas

Gast1 (nicht Gast2)

[RLZ]

Meine Güte....
Egal ob er Quadtree, BVH oder noch eine "bessere" Datenstruktur wählt, er wird keinen Unterschied merken, da alle diese Datenstrukturen schnell genug für den Anwendungszweck sind. :freak:

[Gast]

Meine Güte....

es geht ja nicht um die Datenstrukturen, es geht um das wesentlich
schnellere Finden des nächsten Punktes; und das ist nun mal sehr
kompliziert.
Falls du die Punkte nacheinander testest, dann hast du bei 10.000
schon 10.000 tests, für eine Windowsanwendung heisst das schon
stottern. Bei Voronoi sinds dann nur noch log(10.000), also wesentlich
schneller und vorallem fenstertauglich.

[Bietchiebatchie]

Sorry, aber was die Performance angeht verschätzt du dich gerade gewaltig...

Aus reiner Neugierde hab ich mal einen simplen Test gefahren:
- 1.000 * 1.000 pixel fenster
- 1.000.000 zufällige Punkte innerhalb dieses Fensters
- Ziel: Suchen von allen Punkten die deren Abstand weniger als ein gegebener Wert ist
- Durchlauf mit Abstand = 20 Pixel (d.h. im Durchschnitt > 1000 Treffer)
- simpler Brute-Force-Ansatz (s.u.)
- Ergebnis: < 0.1 s = mehr als ausreichend; falls man nur an den an dem allernächsten Punkt interessiert ist kann man ~ 50 Mio Punkte pro Sekunde vergleichen (im unoptimierten debug mode auf einem alten Laptop;) )

Code: (leicht gekürzt; falls gewünscht poste ich auch das ganze Projekt)

var numberOfPoints = 1000000;
var maxDistance = 20;
var random = new Random();
var points = new Point[numberOfPoints];

for (int i = 0; i < points.Length; i++)
{
points[i] = new Point(random.NextDouble() * this.Width, random.NextDouble() * this.Height);
}

this.MouseDown += delegate
{
var mousePosition = Mouse.GetPosition(this);

foreach (var point in neighbours)
{
if (Math.Sqrt((point.X - mousePosition.X) * (point.X - mousePosition.X) +
(point.Y - mousePosition.Y) * (point.Y - mousePosition.Y)) < maxDistance)
{
// Pixel zeichnen; Details irrelevant (imo)
}
}
}


Mein Fazit: Für das gegebene Problem irgendwas außer Brute-Force zu nutzen ist Zeitverschwendung.

[Aquaschaf]

Wenn einem 10 FPS reichen, und man sonst nichts weiter rechnen muss.. vielleicht ;) Du könntest btw wenigstens die quadrierte Distanz vergleichen, und dir so die ganzen Wurzeln sparen.

[PatkIllA]

eine Million dürften es eigentlich nie sein.
Man könnte auch noch so Sachen machen, wie die Wurzel weglassen und dafür vorher die Entfernung quadrieren.

@Bietchiebatchie
Warum hast du das LINQ-Konstrukt rauseditiert? (Wobei ich das zwecks Windows 2000 Unterstützung eh nicht benutzen kann)

[Gast]

.. wenn man nur bei jedem Mausklick die Suche startet, dann reicht
die Geschwindigkeit (und die Strukturen sind damit Overkill!), für
flüssiges MouseMove aber viel zu langsam!

Schreib einfach mal zu Testzwecken folgendes Programm (eigentlich
sehr einfach): Nach jedem MouseMove soll ein rechteckiges Muster mit
256*256 = 65536 Pixel gezeichnet werden (CPU, nicht GPU!). Auf einem
aktuellen Mittelklasse-PC fängt die Maus schon deutlich zu ruckeln an,
die Rechtecke werden z.B. nur alle 10-20 Pixel gezeichnet. Wird das
Rechteck auf 1000*1000 Punkte erweitert, dann wirds sehr ecklig (und
das OHNE floats!!).
Erst unter Einsatz von GPUs wirds flüssig, ab 1000x1000 merkt man aber
leichtes Ruckeln.

Die Oben genannten Strukturen machen also nicht nur auf sehr alten
PCs Sinn, sie sind auch auf aktuellen PCs oft sehr hilfreich (allerdings
sehr aufwendig zu programmieren).

[Bietchiebatchie]

wegen Wurzel: macht keinen großen Unterschied.


@Bietchiebatchie
Warum hast du das LINQ-Konstrukt rauseditiert? (Wobei ich das zwecks Windows 2000 Unterstützung eh nicht benutzen kann)
die query war letztlich unnötig und foreach-loop + if versteht jeder ;)


.. wenn man nur bei jedem Mausklick die Suche startet, dann reicht
die Geschwindigkeit (und die Strukturen sind damit Overkill!), für
flüssiges MouseMove aber viel zu langsam!

Schreib einfach mal zu Testzwecken folgendes Programm (eigentlich
sehr einfach): Nach jedem MouseMove soll ein rechteckiges Muster mit
256*256 = 65536 Pixel gezeichnet werden (CPU, nicht GPU!). Auf einem
aktuellen Mittelklasse-PC fängt die Maus schon deutlich zu ruckeln an,
die Rechtecke werden z.B. nur alle 10-20 Pixel gezeichnet. Wird das
Rechteck auf 1000*1000 Punkte erweitert, dann wirds sehr ecklig (und
das OHNE floats!!).
Erst unter Einsatz von GPUs wirds flüssig, ab 1000x1000 merkt man aber
leichtes Ruckeln.


Ich kann jetzt nur von wpf reden aber da sehe ich bei einem 1000*1000 Rechteck mit 200 * 200 Schachbrettmuster absolut null ruckeln.
im übrigen verstehe ich nicht ganz worauf du hinaus willst, da ich den Zusammenhang zwischen "benachbarte Punkte finden" und "Rechtecke rendern" nicht wirklichsehe.

[PatkIllA]

Es soll schon bei Mausbewegung und nicht erst beim Klicken passieren.

Bildschirm aktualisieren ist eh immer böse.
Das war glaube ich der größte Performancegewinn, als wir den Bildschirm nicht mehr nach jeder Kachel (die Karte ist gekachelt) sondern erst nach x Sekunden aktualisiert haben.
Danach wurde bei uns bei einer Präsentation sogar schon nachgesagt, dass die Vorführung gefaket sei. So schnell könnte das nicht gehen.

[Bietchiebatchie]

was genau soll bei der Mausbewegung geschehen?

[PatkIllA]

was genau soll bei der Mausbewegung geschehen?
Es soll der nächste Punkt gefunden werden und der soll dann hervorgehoben werden. Das ganze soll dazu dienen, um an den Eckpunkten zum Zeichnen ansetzen zu können.

[Bietchiebatchie]

Achso, dann hast du zwei Optionen:
a) dich an das MouseMove-Event anklinken und bei jedem Aufruf prüfen welches der nächste Punkt ist (schnelltest bei mir: bis ~100.000 kein ruckeln)
b) wie du selber schon geschrieben hast alle x (Milli)Sekunden die Mouseposition abfragen und dann zeichnen.

[Monger]

Schreib einfach mal zu Testzwecken folgendes Programm (eigentlich
sehr einfach): Nach jedem MouseMove soll ein rechteckiges Muster mit
256*256 = 65536 Pixel gezeichnet werden (CPU, nicht GPU!).

Der Vergleich ist unfair, weil GDI Operationen sind grundsätzlich sehr langsam, und wenn man so zwanghaft jedesmal neu refresht, erst recht.

Was er macht, ist nix anderes als ein paar Punkte miteinander zu vergleichen. Das sind ein paar Integer Berechnungen, das entlockt der CPU nur ein müdes Gähnen. Natürlich wäre die Berechnung noch schneller, wenn man statt 10.000 mal eben nur 100mal berechnet.

Aber mich würde es nicht wundern, wenn das gar nicht mal den Flaschenhals in dem Programm darstellen würde. Da dauert das Repainten des Labels wahrscheinlich länger als die ganze Neuberechnung.

Es ist immer das selbe Spiel: erst messen, dann optimieren, dann wieder messen. Da kommen manchmal echte Überraschungen raus.

[Aquaschaf]

Was er macht, ist nix anderes als ein paar Punkte miteinander zu vergleichen. Das sind ein paar Integer Berechnungen, das entlockt der CPU nur ein müdes Gähnen. Natürlich wäre die Berechnung noch schneller, wenn man statt 10.000 mal eben nur 100mal berechnet.

Bei einer interaktiven Framerate sind es schon "ein paar mehr". Die arithmetischen Operationen sind dabei wahrscheinlich gar nicht der Flaschenhals, sondern die Speicherzugriffe (wäre jedenfalls eine Erklärung dafür dass die Wurzel nicht viel kostet). Natürlich tut es trotzdem nicht weh sich erst einmal mit der einfachen Schleife zu begnügen und zu gucken ob das reicht.

[Tesseract]

Mein Fazit: Für das gegebene Problem irgendwas außer Brute-Force zu nutzen ist Zeitverschwendung.

kennst du das projekt? weißt du was performance für eine rolle spiel? weißt du was neben dem problem des threads noch zu berechnen ist?
wahrscheinlich gibt es für quadtrees sogar irgenwelche generischen standardklassen die du verwenden kannst. der aufwand ist nicht gerade groß.
auf was du sicher verzichten kannst sind "kosmetische optimierungen" die irgendwo vereinzelt konstanten aufwand einsparen und solche dinge. das wäre in der tat overkill.
aber linearen aufwand für jedes mouseevent/frame/update/wasauchimmer sollte man bei so einer objektmenge auf jedenfall vermeiden wenn man mit geringem aufwand was logarithmisches bekommt.