Wie kann man viele Punkte schnell vergleichen?

[Uwe Raabe]

@Medium: Es gibt da neben ein paar Grenzfällen, in denen der Code einen ERangeError auslöst (z.B. erster Punkt liegt innerhalb des ersten Fensters, letzter Punkt liegt außerhalb des letzten Fensters), noch das Problem, daß er fehlerhafte Resultate liefert. Mit den gegebenen Werten ergänzt um ein paar weitere Fenster mit Spezialfällen (drittes Fenster umschließt erstes, kompletter Bereich, genau ein Punkt, nur ein Punkt im Bereich) bekomme ich folgende Ergebnisse:

Code:

Punkte: 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 

erwartet: -------------------------------------------------------------
0.7-1.8: 1.0, 1.5
1.4-3.7: 1.5, 2.0, 2.5, 3.0, 3.5
0.6-2.1: 1.0, 1.5, 2.0
0.0-5.0: 0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0
2.0-2.0: 2.0
2.9-3.1: 3.0

erhalten: -------------------------------------------------------------
0.7-1.8: 1.5 , 2.0 
1.4-3.7: 
0.6-2.1: 1.0 , 1.5 , 2.0 , 2.5 , 3.0 , 3.5 
0.0-5.0: 
2.0-2.0: 3.0 
2.9-3.1: 4.5

[himitsu]

Hab jetzt nur mal auf die Schnelle das Find der TStringList versucht anzupassen und hoffe es stimmt soweit auch.

Delphi-Quellcode:

type TMyArray = array of record  X, Y: Integer;  end;

function FindLowerXIndex(const Arr: TMyArray; LowX: Integer): Integer;
var
  L, H, I: Integer;
begin
  L := 0;
  H := High(Arr);
  while L <= H do
  begin
    I := (L + H) shr 1;
    if Arr[I].X < LowX then L := I + 1 else H := I - 1;
  end;
  Result := L;
end;

Das Array muß natürlich nach X sortiert sein.

[Medium]

Zitat von Uwe Raabe:

@Medium: Es gibt da neben ein paar Grenzfällen, in denen der Code einen ERangeError auslöst (z.B. erster Punkt liegt innerhalb des ersten Fensters, letzter Punkt liegt außerhalb des letzten Fensters)

Dessen war ich mir bewusst, war aber gestern Nacht zu faul explizit drauf einzugehen - ich nahm einfach mal an, dass das offensichtlich sein, dass wenn solche Fälle existieren, sie einer Spezialbehandlung bedürfen

Zitat:

noch das Problem, daß er fehlerhafte Resultate liefert. Mit den gegebenen Werten ergänzt um ein paar weitere Fenster mit Spezialfällen (drittes Fenster umschließt erstes, kompletter Bereich, genau ein Punkt, nur ein Punkt im Bereich) bekomme ich folgende Ergebnisse:

Wie gesagt, das hab ich durchaus erwartet. Sobald Fenster Edges teilen (bzw. identische haben), ein Fenster 0 Punkte umschließt oder Edges ausserhalb des Bereiches liegen, müsste ein wenig ge-if-then-else betrieben werden. Meine Intention war auch nicht, einen fix und fertigen Algo einzustellen, sondern nur fix die spontane Idee zu illustrieren

Schöne Grüße,
Medium

[Matze]

Huch, schön, dass euch das Thema auch so interessiert. Erst einmal danke für die zahlreichen Beiträge.

Zitat von NamenLozer:

Wie viele Punkte sind es denn ungefähr?

Ich vermute, das wird 50.000 nicht deutlich überschreiben, aber theoretisch könnten es auch 1 Million sein. Das ganze muss fortlaufend für 8 Kurven berechnet werden. D.h. es muss schnell gehen.

1 Million Punkte zu prüfen hat heute ca. 2-3 Sekunden gedauert nach meinem bisherigen Vorgehen. Das ist natürlich langsam.

Die binäre Suche und die anderen Algorithmen werden vermutlich nicht funktionieren, zumindest nicht wie gewünscht.

Würde die Steigung der Kurve immer positiv sein, wäre denkbar, mit dieser Suche, die jeweils linken und rechten Kanten der Fenster zu bestimmen. Ist die Steigung innerhalb eines Fensters sehr groß und tritt die Kurve unten in das Fenster ein, komme ich mit den Algorithmen dennoch nur zur linken Kante. D.h. ich muss sämtliche Werte in den Fenstern weiterhin prüfen, da hier der Y-Wert ausschlaggebend ist.

Eine weitere Schwierigkeit ist, dass die Kurve auch "zurück laufen" kann. Es handelt sich also nicht um eine mathematische Funktion.
Ja, langsam wird's kompliziert.

Grüße, Matze

[blackfin]

Zitat:

Das ganze muss fortlaufend für 8 Kurven berechnet werden. D.h. es muss schnell gehen.

Ist das eine Echtzeit-Operation?
Wenn ja, wär es vielleicht sogar anzudenken, das ganze über die Grafikkarte und OpenGL zu machen und die Punkte als Vertices in die Grafikkarte zu jagen.
Dann hättest du schlussendlich so ziemlich alle Möglichkeiten, die dir Occlusion Tests der Hardware so bieten.
Aber ich denke, für dein Projekt ist das wohl etwas zuviel des Guten?

[Namenloser]

Zitat von Matze:

Ich vermute, das wird 50.000 nicht deutlich überschreiben, aber theoretisch könnten es auch 1 Million sein. Das ganze muss fortlaufend für 8 Kurven berechnet werden. D.h. es muss schnell gehen.

Das heißt also, die Daten kommen in Echtzeit herein? Also es ist nicht möglich, die Daten vorher optimiert (z.B. als Quadtree) abzuspeichern? Das verkompliziert die Sache natürlich...

[edit]
Das wäre jetzt der Punkt, wo ich anfangen würde, über manuelle Optimierungen und Multithreading das meiste aus der Implementierung herauszuholen, da ich bezweifle, dass es in diesem Fall eine schnellere Lösung gibt, als für jeden Punkt den Vergleich auszuführen, wenn die Daten in Echtzeit hereinkommen. Denn jede optimierte Suche setzt irgendeine Sortierung voraus, und die minimale Laufzeit für einen Sortieralgorithmus beträgt laut Wikipedia O(n*log(n)). Ein einfacher Durchlauf über alle Punkte hingegen hat eine lineare Laufzeit von O(n), und ist somit bei deinen Datenmengen wahrscheinlich schneller als die Sortierung allein. Disclaimer: Ich habe kein Informatik studiert (noch nicht ).
[/edit]

[Matze]

Ähm jain. Sie kommen nicht direkt in Echtzeit rein, da das ganze voraussichtlich unter Windows laufen wird.
Die Daten werde ich jedoch puffern und anschließend, wenn sie alle da sind, auswerten.

Parallel zum Einlesen die Auswertung vorzunehmen wäre auf der einen Seite nett, aber dann müsste ich ständig prüfen, ob die Werte überhaupt so weit eingetroffen sind, dass sie ein Fenster ausfüllen. Und das ist wohl nicht möglich.

Wenn die Werte bsp. in ein Fenster reichen, aber noch nicht drüber raus, dann habe ich unnötig herum gerechnet.

Über die Grafikkarte lasse ich das nicht laufen. Das soll auf CPU-Ebene ablaufen.

[Namenloser]

Ändern sich die Daten denn zwischen zwei Messungen komplett, oder kommen z.B. nur rechts neue Werte hinzu und die alten verschieben sich nach links o.ä.?

[Matze]

Die Kurvenform wird in den meisten Fällen ähnlich sein.
Vor jeder Messung werden die Daten jedoch gelöscht.

[ibp]

Bei Punkt und Ebene fällt mir immer die Hessesche Normalform ein. Durch Optimierung für 2-Ebenen lässt sich da sicherlich noch etwas gewinnen.

vergiss die erste Idee...

2: Idee:

Berechne die Abstände zum Mittelpunkt des Rechtecks. Ist die Differenz (Positiv und Negativ) zum Rand minimal dann sind das die gesuchten Punkte.