AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Nächtes Objekt auf einer "Karte" finden

Nächtes Objekt auf einer "Karte" finden

Ein Thema von CalganX · begonnen am 13. Apr 2007 · letzter Beitrag vom 13. Apr 2007
Antwort Antwort
CalganX

Registriert seit: 21. Jul 2002
Ort: Bonn
5.403 Beiträge
 
Turbo Delphi für Win32
 
#1

Nächtes Objekt auf einer "Karte" finden

  Alt 13. Apr 2007, 18:33
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?
  Mit Zitat antworten Zitat
shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#2

Re: Nächtes Objekt auf einer "Karte" finden

  Alt 13. Apr 2007, 19:04
Ich würde ALLE Entfernungen berechnen und in einer N*N Matrix speichern.
Die Diagonale hat immer den Wert 0.
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.
Andreas
  Mit Zitat antworten Zitat
CalganX

Registriert seit: 21. Jul 2002
Ort: Bonn
5.403 Beiträge
 
Turbo Delphi für Win32
 
#3

Re: Nächtes Objekt auf einer "Karte" finden

  Alt 13. Apr 2007, 19:08
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
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#4

Re: Nächtes Objekt auf einer "Karte" finden

  Alt 13. Apr 2007, 19:21
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.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#5

Re: Nächtes Objekt auf einer "Karte" finden

  Alt 13. Apr 2007, 19:23
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 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)
Andreas
  Mit Zitat antworten Zitat
CalganX

Registriert seit: 21. Jul 2002
Ort: Bonn
5.403 Beiträge
 
Turbo Delphi für Win32
 
#6

Re: Nächtes Objekt auf einer "Karte" finden

  Alt 13. Apr 2007, 19:32
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
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#7

Re: Nächtes Objekt auf einer "Karte" finden

  Alt 13. Apr 2007, 19:47
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.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 13:11 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz