Positionen (x ,y Achse, float) nach Distanz sortieren

[Diengo]

Hallo,

folgendes Vorhaben: Ich möchte etwa 1000~ Positionen welche sich in einem simplen Array vom Typ TPositions ->

Delphi-Quellcode:

TPositions = packed record
  x, y: single;
end;

befinden nach Distanz sortieren. Meine Überlegung war nun jede Position in dem Array zu durchlaufen und mittels abs die Distanz zu ermitteln. Meine simple Funktion hierzu:

Delphi-Quellcode:

function GetDistance(x1, y1, x2, y2: single): double;
begin
  result := abs(x2 - x1) + abs(y2 - y1);
end;

Wie sortiere ich die Positionen nun möglichst schnell im Array nach der Distanz? Einstiegspunkt soll dabei immer die Distanz zum ersten Eintrag im Array sein. Mir fällt da nur ein die Liste mehrmals zu durchlaufen um von jeder Position die Distanz zu ermitteln und dann irgendwie zu ordnen.

Geht das nicht irgendwie bequemer?

Gruß

[Bummi]

Wie der Betreff schon sagt, einfach per z.B. Quicksort sortieren ...

[stahli]

Die Entfernung sollte man so berechnen (meint Google ): a = Wurzel((x2-x1)²+(y2-y1)²).

Nach Möglichkeit würde ich den Record um "distance" erweitern, alle Entfernungen einmal berechnen lassen und dann das Array nach "distance" sortieren.

[Uwe Raabe]

Zitat von stahli:

Die Entfernung sollte man so berechnen (meint Google ): a = Wurzel((x2-x1)²+(y2-y1)²).

Für die reine Sortierung sollte das unerheblich sein, da ein Vergleich der Abstände zweier Punkt-Paare mit beiden Abstandsfunktionen das gleiche Ergebnis liefert. Wenn die realen Abstände nicht noch für etwas anderes gebraucht werden, ist die Abs-Lösung etwas performanter.

Den korrekten Abstand zweier Punkte kann man aber auch mit

Delphi-Quellcode:

uses Math;

  a := Hypot(y2-y1, x2-x1);

bekommen.

[stahli]

Ich bin schon ein paar Jahre raus aus der Schule und hatte mir nur gedacht, dass

0/0 : 0/20
und
0/0 : 10/10

unterschiedliche Entfernungen ergeben müsste (was in der einfachen Variante ja nicht der Fall ist).
Daher habe ich mal gesucht...

[Uwe Raabe]

Zitat von stahli:

Ich bin schon ein paar Jahre raus aus der Schule und hatte mir nur gedacht, dass

0/0 : 0/20
und
0/0 : 10/10

unterschiedliche Entfernungen ergeben müsste (was in der einfachen Variante ja nicht der Fall ist).
Daher habe ich mal gesucht...

Stimmt, ich hatte mich da blenden lassen. Der alternative Ansatz für eine performantere Abstandsformel ist das weglassen der Wurzel - die Quadrate müssen bleiben. Sorry.

[stahli]

Ja, das leuchtet selbst mir ein