Objekte mit X/Y Werten die sich "nähern"?

[Angel4585]

Hallo zusammen.

Ich habe mehrere Objekte, jeweils mit X und Y Eigenschaften.
Auf welche Methode finde ich jetzt am schnellsten raus ob sich zwei Objekte überschneiden,
bzw. sich zu "nahe" kommen?

Also ein ObjektA hat x = 10 und Y = 10

Jetzt ist irgendwo ein ObjektX mit den Werten X= 12 und Y = 12, oder X= 8 und Y = 8, oder X= 8 und Y = 12.

Also ObjektX ist eben in der Nähe von ObjektA.

Und ObjektA soll irgendwie prüfen, ob sich irgendein Objekt(z.B.ObjektX) in diesem bestimmten Bereich um ObjektA(sich selbst) befindet.

Bisher hab ich das ungefähr so:

Delphi-Quellcode:

if SQRT(Abs(Self.X-Ziel.X)*Abs(Self.X-Ziel.X)+Abs(Self.Y-Ziel.Y)*Abs(Self.Y-Ziel.Y)) < 10 then

Weis jemand eine Effizientere Möglichkeit dafür?

Danke schonmal

(PS: Sorry, ist vielleicht bissl kompliziert erklärt)

[shmia]

Die Entfernung zweier Punkt wird mit Pythagoras berechnet:

Delphi-Quellcode:

entfernung := Round(Sqrt( Sqr(Self.X-Ziel.X)+Sqr(Self.Y-Ziel.Y)));

Du kannst Rechenzeit sparen, indem du das Sqrt (=Wurzelziehen) weglässt und stattdessen
die gewünschte Entfernung quadrierst:

Delphi-Quellcode:

Sollentfernung := 10;
Sollentfernung2 := Sqr(Sollentfernung);
if Sqr(Self.X-Ziel.X)+Sqr(Self.Y-Ziel.Y) < Sollentfernung2 then
   ShowMessage('Entfernung ist < 10');

[Angel4585]

Gut soweit zum SQRT mein eigentliches Problem ist das ich etliche solcher Objekte in einer Objectlist habe und nicht mit einer For Schleife jedes einzelne vergleichen will, sondern ne effizientere Methode suche.

[Der_Unwissende]

Hi,
du kannst da wahrscheinlich ne Menge optimieren, wobei es dann an anderer Stelle einfach Zeit kostet. So könntest du deine Liste vorsortieren. Müsstest du mal gucken wieviel Zeit das kostet (wenn du eine durchmischte Liste sortierst, wenn du sortiert einfügst...). Wenn du so etwas hast, dann musst du natürlich nur schauen ob dein i-tes Objekt (Liste = 0..n, i >= 0, i <= n) schon weiter weg ist als du möchtest, dann ist halt alles dahinter erst recht weiter weg.
Dann könntest du auch das maximale x (y = 0) und das maximale y (x = 0) ausrechnen, dass ein Objekt haben kann bevor der Abstand größer als dein Wert ist. (Gut, ist der Wert, da gibts nichts zu rechnen) und da kannst du dann schon mal alles rausschmeissen oder nicht betrachten, was ein größeres X oder Y hat.

Wie effizient was davon ist, kommt natürlich auf die Anzahl der Objekte und die zu erwartende Entfernung der Objekte zur Referenz an. Was assymptotisch immer am schnellsten ist hab ich mir natürlich nicht überlegt, aber ich denke in deinem Fall sollte es wirklich von der erwarteten Anordnung abhängen (ausser du hast wirklich 100.000de Objekte, sonst können große Konstanten die echte Laufzeit doch gut verfälschen).

Gruß Der Unwissende