nächsten Punkt aus einer Matrix finden
-
Hallo zusammen
Ich habe eine teilweise gefüllte zweidimensionale Matrix M[101[101]. Diese Matrix beinhaltet Referenzwerte. Nun ist es so, dass ich einen Vektor (a1;a21) mit 0<a1<101 & 0<a2<101 einlese und für diesen mit Hilfe der Referenzwerte einen (nennen wir ihn Z-)Wert interpolieren möchte. Dazu brauche ich die 4 nächsten Punkte in positiver/negativer X- und Y-Richtung, siehe Grafik:
^ Y| Vektoren X Y Z 100- 140 150 Referenz1 60 80 100 | Referenz2 60 100 140 | Referenz3 100 80 80 | I Referenz4 100 100 150 | Input I 80 86 ? 80- 100 80 | . . . | x-...-|----|----|---> 60 80 100 X(die einfache Variante)
^ Y| Vektoren X Y Z 100- 140 150 Referenz1 62 84 100 | Referenz2 60 100 140 | Referenz3 98 76 80 | I Referenz4 100 100 150 | Input I 80 86 ? 80- 100 80 | . . . | x-...-|----|----|---> 60 80 100 X(aber auch möglich, dass die Werte nicht alle in einer Spalte bzw Zeile angeordnet sind)
Es geht hier nicht um die Interpolation, nur um das finden der 4 Werte. Da das ganze später mal auf einem embedded Device laufen soll (STM32 Discovery), wäre eine effiziente Suche (keine Wurzel, nach Möglichkeit wenig Division und wenig Speicherzugriff) cool, aber erstmal nicht zwingend (außer keine Wurzel). Hat evtl jemand eine Idee?
Vielen Dank und viele Grüße
-
(gelöscht, hatte die Frage falsch verstanden)
Hilfe, ich weiß nicht, was "die vier nächsten Punkte" sind.
Das ist noch recht klar:
^ Y| Vektoren X Y Z 80- 140 150 Referenz1 60 60 100 | Referenz2 60 80 140 | Referenz3 80 60 80 | I Referenz4 80 80 150 | Input I 70 70 ? 60- 100 80 | . . . | x-...-|----|----|---> 60 80 XAber hier:
^ Y| 140 Vektoren X Y Z 80- 150 Referenz1 60 60 100 | 142 Referenz2a 61 81 140 | Referenz2b 59 79 140 | Referenz3 80 60 80 | I Referenz4 80 80 150 | Input I 70 70 ? 60- 100 80 | . . . | x-...-|----|----|---> 60 80 Xist mir schleierhaft, ob ich Referenz2a oder Referenz2b wählen soll.
-
Vielen Dank für deine(n) Beitrag(e). Ich hatte deinen ersten Beitrag schon gelesen und bin eig auch sehr angetan von dem k-d-Baum (kannte ich vorher nicht, sry). Mit deinem Einwand hast du natürlich Recht, das weiß ich auch nicht und das wird auch sonst wahrscheinlich niemand wissen.
Aber die Idee ist jetzt die, dass die Fläche in sich nicht überlappende Rechtecke, deren Ecken die Referenzpunkte bilden, gesplitet wird. Mit Hilfe eines modifizierten kd-Baums bekommt man die Ecken.
Vielen Dank Dir
-
Kathrino schrieb:
die Idee ist jetzt die, dass die Fläche in sich nicht überlappende Rechtecke, deren Ecken die Referenzpunkte bilden, gesplitet wird.
Mhhm.
Nehmen wir mal diese Aufteilung in nichtüberlappende Rechtecke: http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/2dbaum.svg/860px-2dbaum.svg.png
und den Punkt (2;1.5).
Sein Rechteck hat zwar 4 Ecken, aber (1.8;2.5) ist auch ein Referenzpunkt und liegt näher als die Ecke (1,2;2.5). Ok, den würde ich einfach ignorieren, die viel Eckpunkte lassen sich so fein finden.Soll so eine wirre Zerlegung möglich sein oder vielleicht doch bloß ein Grid? http://media2mult.uni-osnabrueck.de/pmwiki/fields/dbs/m2m.d/Main.GridFile/media/image/eps/skalen-und-gitterzellen.png
Mit durchgehenden Bruchlinien hättest Du nur zwei Ramzugriffe und viel weniger Code, um zu wissen, wo die 4 Eckpunkte liegen, weil Du für jede Achse ein Array hättest, wo der Abstand zur linken und rechten Bruchlinie gespeichert ist.
-
Die wirre Aufteilung und die Wahl der nur vier Ecken des den Punkt umgebenden Rechtecks macht glaube ich eine stetige Interpolation über Rechtecksgrenzen unmöglich.
http://www.sea-of-memes.com/LetsCode28/gaps.jpg
