Nächtes Objekt auf einer "Karte" finden

[CalganX]

Hi,
eine theoretische Frage: ich habe auf einer Art Karte mehrere Objekte, die sich bewegen. Nun möchte ich wissen, wie weit die zwei Objekte sind, die einem Objekt am nächsten sind. Diese Distanz soll nämlich bspw. nicht kleiner werden 10 bzw. 15 (nächstes, zweitnächstes Objekt).
Nun bin ich auf der Suche nach einem möglichst einfachen Algorithmus, der mir diese beiden Objekte liefert. Das geht natürlich ganz einfach, indem ich die ganze Sammlung durchgehe und nach denen suche, die die niedrigste Entfernung habe. Problem ist nur, dass das bei meinen Größenordnungen (bis zu 200 Objekte) wahrscheinlich relativ langsam werden wird (da das ganze wechselseitig ist, muss jedes der 200 Objekte die beiden Objekte finden, die am nächsten zu ihm sind).

Ich kenne einen Algorithmus, der das zumindest für ein Objekt macht: man zerlegt das Feld in viele einzelne Sektionen und sucht die benachbarten Sektionen. Ich hab darüber mal einen Vortrag gehört, allerdings kann ich mich kaum noch daran erinnern und ich weiß auch nicht, wie dieser Algorithmus bzw. dieses Prinzip heißt. Außerdem scheint mir das ein wenig problematisch, da mit jeder Iteration sich mein Feld verändert und somit es extrem langsam zu werden scheint.

Kann mir da jemand einen Tipp geben oder gar einen guten und performanten Algorithmus nennen?

Chris

Edit: Das, was ich meine sind Voronoi-Diagramme und die Delaunay-Triangulation. Wie es scheint ist das die optimale Lösung für mein Problem, oder?

[shmia]

Ich würde ALLE Entfernungen berechnen und in einer N*N Matrix speichern.
Die Diagonale hat immer den Wert 0.

Delphi-Quellcode:

Type TDistanceTable = array[0..199, 0..199] of Integer;

Wenn ein Objekt sich bewegt, dann müssen nur 2*N-1 Entfernungen neu berechnet werden,
alle anderen bleiben gleich.
Die Entfernung wird mit der Format distance=(X2-X1)^2+(y2-Y1)^2 berechnet.
Das Wurzelziehen schenken wir uns. Das vermeidet die Verwendung von Flieskommazahlen.

Nun werden die beiden nächsten Objekte ermittelt.
Das benötigt N*(N-1) Vergleiche, aber heutige PCs erledigen das in Null Komma Nix.

[CalganX]

Hi shmia,
Problem ist, dass sich in jeder Iteration alle Objekte bewegen (unterschiedliche Richtung, unterschiedliche Weite, etc.). Bleibt es dann immer noch so perfomant, wie du sagst?

Mir ist gerade wieder eingefallen, wie ich die Delaunay-Triangulation verwenden könnte, allerdings ist halt wirklich die Frage, ob das wirklich das schnellste Verfahren wäre (bei O(n log(n) ) bin ich mir da nicht so ganz sicher, aber auch nicht vom Gegenteil überzeugt).

Chris

[Nikolas]

Zitat:

Wenn ein Objekt sich bewegt, dann müssen nur 2*N-1 Entfernungen neu berechnet werden,

Warum das? Es gibt doch nur (N-1) andere Objekte zu denen sich die Entfernung ändert.

Ein anderer Ansatz ist ein Teile und Herrsche, den ich mal für den BWINF erdacht habe:
Teile dein Gebiet in denen die Körper sind, in Sektoren ein und gib dann jedem Sektor eine Liste mit den enthaltenen Körpern. Bei jedem Zeitschritt werden dann diese Listen erneuert, was proportional zu N ist.
Wenn du für einen Körper dann die nächsten Körper suchst, betrachtest du erst die anderen Körper im Sektor. Wenn der minimale Abstand zu denen kleiner ist, als der Abstand deines Körpers zu einer Sektorgrenze, bist du fertig, alternativ musst du noch die Elemente in diesem Sektor prüfen. Je nach Sektorengröße bist du damit auf jeden Fall schneller als ein BruteForce ansatz.

[shmia]

Zitat:

Zitat von CalganX

Problem ist, dass sich in jeder Iteration alle Objekte bewegen (unterschiedliche Richtung, unterschiedliche Weite, etc.). Bleibt es dann immer noch so perfomant, wie du sagst?

Nein, das ändert natürlich alles.
Man kann bei der Entfernungsermittlung die Hälfte einsparen, werden man beachtet, das Entfernung von A->B gleich B->A ist.

Zitat:

Zitat von CalganX

Mir ist gerade wieder eingefallen, wie ich die Delaunay-Triangulation verwenden könnte

Das wäre natürlich eine wirklich grosse Einsparung.
Pro Punkt müssen in der Regel dann nur noch 3 bis 8 Vektoren überprüft werden, um das Minimum zu finden.

Ich würd's einfach mal mit meiner "Brute-Force" Methode probieren; könnte mir vorstellen, dass das trotz der vielen Berechnungen und Vergleiche doch noch recht schnell sein kann.
Wenn die Anzahl der Objekt verzehnfacht wird, verhundertfacht sich der Aufwand ~O(N^2) :roll:

[CalganX]

Hi,
@shmia:
okay. Ich hab jetzt diese drei Verfahren zur Auswahl und ich werde einfach mal sehen, was im Test als Schnellstes erscheint. Ich werde auch erstmal mit weniger Objekten anfangen.

@Nikolas:
Divide-and-Conquer ist im Prinzip die Delaunay-Triangulation, die ich meinte, oder zumindest eine Variation davon.

Danke dir,
Chris

[Nikolas]

Ich hab mir deine Idee mal angesehen und die Umsetzung dürfte doch recht aufwändig sein, so wie ich das verstanden habe. Da dürfte mein Ansatz schneller gehen und wenn du die Körper durchnummerierst, musst du beim einsortieren in die Listen jeweils nur 2 divs pro Körper machen und einen Integer schreiben.