Wie kann man viele Punkte schnell vergleichen?

[Matze]

Hallo zusammen,

ich habe Punkte, die ich in einem Diagramm anzeigen lasse (verbunden ist es natürlich eine Kurve). D.h. jeder Punkt besitzt einen x- und eine y-Wert.

Nun habe ich mehrere Fenster festgelegt, mit denen ich die Kurvenabschnitte auswerte.

Ein Beispiel mit 2 Fenstern ist folgendes:

x = 12,5 bis 17,8
x = 16,9 bis 20

Ich kann beliebig viele Fenster (Rechtecke) vorgeben und ich möchte die Punkte darin schnell ausfindig machen, damit ich diese mit anderen Dingen vergleichen kann.

Würden sich die Fenster nicht überschneiden, könnte ich die Kurve in einer Schleife ein einziges Mal durchlaufen (von links nach rechts).
Da sich die Fenster überschneiden untersuche ich aktuell pro Fenster die Kurve vom niedrigsten x-Wert bis zum Ende des Fensters (dann kann ich den Suchdurchlauf natürlich abbrechen). D.h. es sind viele Vergleiche nötig, um überhaupt herauszufinden, ab wann die Kurve in das Fenster eintritt.

Ich kann nicht direkt auf die Punkte zugreifen, da ich erst herausfinden muss, welcher Punkt in welchem Fenster liegt.

Ein Zahlenbeispiel zur Verdeutlichung:

Punkte:

Code:

0    0,5    1    1,5    2    2,5    3    3,5    4    4,5    5

Die Fenster sind wie folgt definiert:

Code:

Fenster 1:
x = 0,7 bis 1,8

Fenster 2:
x = 1,4 bis 3,7

Mein Ziel ist es, den Punkt direkt vor dem Fenster und den ersten im Fenster zu ermitteln und beim Austritt ebenfalls. Hier zeige ich nur den Suchvorgang allgemein.

2 Bereiche -> 2 Schleifen:

Schleife 1 fürs 1. Fenster:
Diese läuft von x = 0 bis x = 2 und gibt mir als Werte innerhalb des Fensters 1 und 1,5 zurück.

Schleife 2 fürs 2. Fenster:
Diese läuft von x = 0 bis x = 4 und gibt mir als Werte innerhalb des Fensters 1,5 bis 3,5 zurück.

Bei tausenden Werten und vielen Fenstern kann das lange dauern.

Geht es irgendwie schneller?

Die Punkte liegen übrigens in 2 Arrays vor: in einem sind die x- und im anderen die y-Werte definiert.

Grüße, Matze

[H4ndy]

Dreh es doch um, und lauf die Punkte nur einmal durch und vergleich pro Punkt, ob dieser in einem der Fenster liegt, koennte schneller sein, solange weniger Fenster als Punkt vorhanden sind. Vielleicht kann man auch was mit Sortierung noch rausholen.

[himitsu]

Wenn die Punkte-Liste sortiert ist, dann kannst du doch über eine binäre Suche ganz schnell den Anfang für deinen Bereich suchen.

Also den ersten Wert, welcher größer-gleich deinem Anfan für das Rechteck ist.

Diese Suche wäre dann mit O(log n) schon recht schnell, so daß bei 1.000.000 Punkten schon nach maximal 20 Vergleichen der Anfang gefunden wäre.

[Matze]

Puh, das wird komplex. Aber stimmt, das wäre evtl. schneller. Danke für den Hinweis.

Wie angedeutet, brauche ich jeweils den Punkt direkt vor dem Fenster, dann den ersten und letzten im Fenster und den ersten Punkt, der wieder aus dem Fenster draußen ist.
D.h. ich müsste immer den aktuellen und den nächsten Punkt mit den Fensterkanten vergleichen. Und es kommen zu den x-Wertenauch noch die y-Werte hinzu und die Vergleiche mit den Fensterober- und -unterkanten. Ohje ....

@Himi: Ich weiß nicht, ob das funktioniert, da ich keinen bestimmten Wert suche. D.h. die Suche würde bei mir fast immer "kein Treffer" liefern.

[himitsu]

Klar funktioniert das.
Du suchst also einfach nur den wert, welcher Größer-Gleich deinem Startpunkt ist und welcher am nähesten an diesem Punkt liegt.

Schau dir mal die Find-Methode der TStringList an.
Über diese wird zwar ein bestimmter Wert gesucht, aber wenn nix gefunden wird, dann gibt diese die Position zurück welcher der Wert eingefügt werden könnte.

[Matze]

Ich guck mal, ob ich den Algorithmus verstehe und ihn umsetzen kann.

[Namenloser]

Wie viele Punkte sind es denn ungefähr? Wie wäre es mit einem Quadtree? (Kann sein, dass himitsu mit Binärer Suche das gleiche meinte).

PS: Unten ist auch eine Seite mit Beispielen verlinkt.