optimale Gerade in einer Punktemenge finden
Hallo community,
Ich habe eine endliche Liste von Punkten, wie ( (x1,y1) (x2,y2)...(xn,yn)). Nun brauche ich für mein Projekt ein schnelles Verfahren, um eine Gerade f(x) = ax +b zu berechnen, die durch möglichst viele Punkte gehen sollte. Die Anzahl der Punkte liegen etwa bei 250 - 500 punkten.
Mein jetziger Stand sieht wie folgt aus: Man berechnet für jeweils zwei Punkten eine Funktion und die Funktion die die meisten Punkte schneidet, hat gewonnen und ich bin glücklich.
Doch die Laufzeit ist wirklich schlimm. Sei n die Anzahl der Punkte, dann gilt für Berechnung der Funktionen: n + (n - 1) + (n - 2) ... + 2 + 1 = (n-1) (n-2) / 2 und da ich ja noch jede Funktion austesten muss so etwa in n^3 -> dies dauert bei mir schon 5min bis er fertig ist^^
Aus diesem Grund wäre ich für jede Inspiration sehr hilfreich!
(Falls ihr euch über die Zeit wunder. Ich schreibe racket =) )
2 Antworten
Sehr gut gehen hier auch genetische Algorithmen. Ich habe dies einmal erfolgreich programmiert für das Auffinden einer Kreislinie, die "am Nächsten" an einer gegeben Punktwolke liegt. "Am nächsten" hatte ich einfach als die Summe aller (positiven) Abstände von den Punkten zur gesuchten Kreislinie definiert.
Als Ausgangslage habe ich 100 Kreise genommen, von jedem den (summierten) "Abstand" zur Punktwolke bestimmt und dann mittels Cross-Over (ca 30% der Population) und einer leichten Mutationsrate von ca. 1% neue Kreise bestimmt. (Dabei habe ich auch immer wieder die schlechtesten etwa 30% der Population gelöscht.
Probleme sind wie immer die lokalen Minima. Wenn ich nun als Input nur Punkte nehme, die auf einem gegebenen Kreis Ka oder auf einem gegebene Kreis Kb liegen, so wird entweder der eine oder der andere Kreis gefunden, selten aber irgendetwas sinnvolles dazwischen. Wobei "sinnvoll" ja gar nicht definiert war.
Ich nehme an, Du meinst nicht die Korrelationsgerade. Dann würde ich so vorgehen:
Zähle die Häufigkeit H(a,b) jeder Geraden g: y=a·x+b durch zwei verschiedene Punkte. H(a,b) ist am Ende die Zahl der möglichen Punktepaare auf g, und die steigt monoton mit der Zahl der Punkte auf g. Die häufigste Gerade ist also Dein Gewinner.
Das braucht 'nur' O(n²) Zeit, also bei Dir etwa eine Sekunde.
Das klingt nun doch eher wie eine Regressionsgerade (Korrelationsgerade hat weniger Such-Treffer). Die lässt sich sogar in O(n) berechnen:
Punkte (xi, yi), Mittelwerte xm und ym. Dann g: y=a(x-xm)+ym mit
a = Σ(xi-xm)(yi-ym) / Σ(xi-xm)².
In Deinem Beispiel wäre xm = 4, ym = 11/7 = 1,57 und
a = [ (-3-2-1)·(-4/7) +(1+2+3)·3/7 ] / (9+4+1+0+1+4+9) = 15/98
also g: y=15/98x+94/98 ⇒ y(1) = 1,11, y(4) = 1,57, y(7) = 2,03
Haut das in etwa hin?
Ja, das stimmt. Die Häufgigkeit hätte es getan! :) Vielen Dank!
Leider habe ich mich bei meiner Frage nicht konkret ausgedrückt und tue es dann nun :P
Diese Punkte sind Pixelpunkte. Das heißt, dass wir hier von Flächenpunkte sprechen. Angenommen wir haben die Punkte
(1,1) (2,1) (3,1)(4,2)(5,2)(6,2) (7,2). So wäre f(x) = 0x + 2 nicht die beste Funktion sondern eher eine Funktion die durch den Punkt (2,1) und (7,2) verläuft (oder sogar eine ganz Andere, aber so eine Lösung würde mir schon reichen).
Bei meiner Idee runde ich den Wert g(x) auf einen Integer und zähle die Treffer einer Funktion.
Vielleicht hast du für dieses Problem eine Hilfe :D
Grüsse klauszi