bilineare Interpolation auf beliebigem Viereck

Neue Frage »

marodeur Auf diesen Beitrag antworten »
bilineare Interpolation auf beliebigem Viereck
Hallo,

kurz die Problembeschreibung:
Ich habe eine unregelmäßiges konvexes Viereck, an dessen Eckpunkte der Funktionswert einer Funktion bekannt ist. Nun brauche ich jedoch einen Funktionswert im Inneren dieses Vierecks bei den Koordinaten .

Habe mir dazu schon dieses hier angeschaut: Wiki: bilin. Interpolation (leider nur für Rechtecke).

Wie komme ich nun auf bel. Vierecke? Eine Transformation von Viereck auf Rechteck ist sicherlich sehr aufwendig und rechenintensiv.

Alternativ kam mir folgende Idee:
Ich stelle in jedem Eckpunkt eine funktion auf, die im zugehörigen Eckpunkt gleich ist und in allen anderen 0. Das heißt ich muss 4mal ein Gleichungssystem von der Dimension 4 lösen. Habe ich die so bilde ich als Näherung für .
Geht das so?
frank09 Auf diesen Beitrag antworten »

Man kann das so machen:
Seien die Eckpunkte eines beliebigen Vierecks (im Beispiel konvex) (, etc. deren Ortsvektoren). Gesucht wird eine Näherung von . Man sucht Punkte und, die die Vektoren und jeweils im gleichen Verhältnis teilen und deren Verbindunggerade durch geht.
sei der Parameter für sowie . Punkt liegt auf der Geraden mit
Wenn man für und entsprechend einsetzt und die Eckpunkt durch ihre beiden Koordinaten ersetzt, bekommt man zwei Gleichungen (je eine für die x / y-Koord.) und kann und bestimmen. Mit interpoliert man sowie , um dann mit zu interpolieren:
marodeur Auf diesen Beitrag antworten »

ist es richtig, dass die beiden Gleichungen nicht linear in und sind? Man bekommt ja ein in die Gleichung.
Ehos Auf diesen Beitrag antworten »

Aus mathematischer Sicht suchst du die Taylerentwickung einer Funktion f(x) bis zur ersten Ordnung, wobei das Argumnet der Funktion die folgende Gestalt hat: x=A+BA*k1+DA*k2. Dabei sind k1, k2 die Parameter im Intervall [0;1].

Die Rechnung von Frank09 ist ok. Aber seine Näherungsformel wird in der Tat nichtlinear, weil das Parameterprodukt k*l auftritt. Dies lässt sich nur dann vermeiden, wenn man von den 4 Eckpunkten des Viereckes nur 3 Eckpunkte „mitnimmt“ und den vierten Funktionswert f(C), der dem Punkt A diagonal gegenüberliegt, ignoriert.

Man dies umgekehrt auch so formulieren: Wenn man alle 4 Eckpunkte berücksichtigen wollte, wäre eine lineare Näherung zu grob. Für eine derartige „gute“ Näherung müsste man die quadratische Ordnung der Taylorentwicklung „mitnehmen“.

Wenn man nur 3 Punkte des Viereckes berücksichtigt, bedeutet dies geometrisch, dass das Viereck ein Parallelogramm sein muss, das von zwei Vektoren AB und AD aufgespannt wird. Der Näherungswert auf dem 4.Punkt ist dann durch die anderen 3 Punkte bereits festgelegt (weil die lineare Näherung so grob ist).

Auf der Kante AB lautet der genäherte Funktionswert

f=f(A)+k1*[f(B)-f(A)] mit dem Parameter k1: 0<k1<1

Auf der Kante AD lautet der genäherte Funktionswert analog

f=f(A)+k2*[f(D)-f(A)] mit Parameter k2: 0<k2<1

Daraus folgt, die Näherungsformel innerhalb der Fläche des Parallelogrammes:

f= f(A)+k1*[f(B)-f(A)]+ k2*[f(D)-f(A)]

Wie gesagt, das ist nichts anderes als eine Taylorentwicklung in 1.Ordnung.

Ich glaube, du kommst prinzipiell auf die gleiche Formel, wenn du den nichtlinearen Summanden in der Formel von Frank09 weglässt.
marodeur Auf diesen Beitrag antworten »

ich glaube ich werde mal versuchen alle varianten an nen paar beispielen nachzurechnen. da damit mitunter konzentrationen von medikamenten/wirkstoffen bestimmt werden sollen, sollte es schon relativ sehr genau sein, finde ich jedenfalls.
Ehos Auf diesen Beitrag antworten »

Die gesuchte Näherungsformel in 2.Ordnung, die du nach dem Prinzip von frank09 bekommst, lautet:

f(P)=f(A)+[f(B)-f(A)]*k1+[f(D)-f(A)]*k2+[f(C)-f(D)-f(B)+f(A)]*k1*k2

Die Parameter k1 und k2 laufen im Intervall [0;1]

Dass diese Formel richtig ist, ergibt sich durch Probe, indem man die Parameter k1, k2 wie folgt wählt und erwartungsgemäß die Funktionswerte an den Eckpunkten des Viereckes herausbekommt.

Setze k1=k2=0. Dann bekommst du f(P)=f(A).
Setze k1=k2=1. dann bekommst du f(P)=f(C)
Setze k1=1, k2=0. Dann bekommst du f(P)=f(B)
Setze k1=0, k2=1. Dann bekommst du f(P)=f(D)

Damit ist die obige Formel bestätigt.
 
 
marodeur Auf diesen Beitrag antworten »

hast du auch noch einen tipp, wie ich die beiden Faktoren k1 und k2 bestimmen kann, möglichst numerisch nicht aufwendig.
frank09 Auf diesen Beitrag antworten »

Eine rein lineare Funktion würdest du bekommen, wenn du -wie schon erwähnt-
nur 3 Punkte berücksichtigen würdest und durch diese eine Ebene legen würdest. Diese hätte folgende Form:
f(x,y)=ax+by+c
Die einfachste nicht-lineare Funktion, die 4 Punkte enthalten würde, wäre ja:

Die Koeffizienten ließen sich relativ leicht bestimmen, indem man vier Gl. aufstellt
durch Einsetzen von den Koordinaten der gegebenen Punkte sowie auf der linken Seite deren Funktionswert.
Es könnte sogar sein, dass diese Funktion genau den Näherungswert ergibt, der auch bei dem anderen Verfahren herauskommt.
Ich habe mit einfachen, rechteckig angeordneten Punken schon das lineare
Verhalten auf den Rändern des Vierecks festgestellt.
Das ist noch keine Beweis, dass diese Funktion dem anderen Verfahren entspricht, jedoch ein Hinweis. Man sollte das mal überprüfen, weil man damit schneller zum Ziel käme.
frank09 Auf diesen Beitrag antworten »

Die genannte Funktion f(x,y)=ax+bxy+cy+d ist nicht linear für die Ränder.

Nochmal zur Berechnung der Parameter k,l: du kannst ja z.B k durch l ausdrücken
und dann in das Produkt k*l einsetzen. Von den Lösungen dieser quadr. Gleichung nimmst du natürlich nur die zwischen 0 und 1.
Ehos Auf diesen Beitrag antworten »

Hallo Marodeur,

Du schreibst, ich soll dir noch sagen, wie man die Faktoren k1, k2 bestimmt.

Diese Frage ist mir unklar, weil die Parameter k1, k2 im Intervall [0;1] beliebig wählbar sind, je nachdem, wo du den Funktionswert f(P) wissen willst.

Unterteile das Viereck in Gedanken in ein Netz aus 10 waagerechten und 10 senkrechten Linien (Längen- und Breitengrade).

Der Parameter k1 gibt innerhalb des Viereckes den Längengrad an (also die Position "von links nach rechts"). Der Parameter k2 gibt dort den Breitengrad an (also die Position "von oben nach unten").

Beispiel 1
Wenn du den Funktionswert f(P) in der Mitte des Viereckes haben willst, also am der 5.Längengrad und am 5.Breitengrad, dann lauten die Parameter: k1=k2=0,5.

Beispiel 2:
Wenn die den Funktionswert f(P) am 9.Längengrad (also fast ganz rechts) und am 7.Breitengrad wissen willst, lauten die Parameter k1=9 und k2=7.
usw.

Eigentlich ist mit der Formel, die ich dir beim letzten Mal angegeben habe, alles gesagt. Wenn Du trotzdem noch Fragen hast, beschreibe mir nochmal Deine exakte Aufgabe.
marodeur Auf diesen Beitrag antworten »

@Ethos: hab nicht dran gedacht, dass du ja von nem Parallelogramm ausgehst Ups

@frank: das verstehe ich nicht. Die Parameter sind doch unabhängig voneinander und ergeben sich aus den Koordinaten des Punktes? verwirrt
frank09 Auf diesen Beitrag antworten »

Sei und mit .
Ich suche nun eine Näherung für mit


Wie schon erwähnt liegt ja auf dieser Geraden:
wobei und

Einsetzen ergibt:


Erste Koordinatenzeile:

Zweite Koordinatenzeile:


Folgendes nicht-lineare GLS:



untere mit -3 multipl. und zur oberen addieren, ergibt:
in untere einsetzen ergibt:

Lösungen: wegen

zweimal linear interpolieren ergibt:




Ehos Auf diesen Beitrag antworten »

Hallo Marodeur,

nein, die Formel, die ich dir am 17.06.09 um 12:50 Uhr geschrieben habe, gilt nicht nur für ein Parallelogramm, sondern die exakte Formel für ein Viereck mit den beliebigen Eckpunkten A, B, C, D. Das ist akso die quadratische Näherung, denn in der Formel taucht das Produkt k1,k2 der Parameter auf

Nur in meinem Beitrag davor habe ich mich auf die lineare Näherung bezogen, welche nur für das Parallelogramm galt
marodeur Auf diesen Beitrag antworten »

@frank: Ah, jetzt hab ichs verstanden. Einfach das k*l rauskicken und dann gucken was passiert. Ich werd mal versuchen dies umzusetzen und zu verallgemeinern. die frage ist, bekomme ich damit immer eine exakte lösung, oder können auch mal beide lösungen der quadratischen gleichung im intervall liegen?

@ehos: du hast doch aber längen und breitengrade angegeben, da diese aber nicht überall äquidistant sind, erschwert sich das doch alles.


sagt es ruhig, wenn ich mich zu doof anstelle Augenzwinkern
Ehos Auf diesen Beitrag antworten »

Hallo Marodeur,

iDie gesuchte Näherungsformel für den Funktionswert f(P) innerhalb deines unregelmäßigen Vierecks lautet wie gesagt.

f(P)=f(A)+[f(B)-f(A)]*k1+[f(D)-f(A)]*k2+[f(C)-f(D)-f(B)+f(A)]*k1*k2

Es muss sich NICHT notwendig um ein parallelogramm handeln!!! Dabei sind A,B,C,D die Eckpunkte und die Parameter k1 und k2 laufen im Intervall [0;1].

Du hast recht, die Längen und Breitengrade sind nicht äquidistant. Das ist bei einem Globus genauso und kein Nachteil.

Anschaulich kannst du dein Problem wie folgt veranschaulichen:

Betrachte eine quadratische Plastik-Folie mit den Eckpunkten A,B,C,D und der Seitenlänge 1. Auf dieser Folie ist eine Funktion f(P) gegeben, die z.B. die temperatur auf jedem Punkt P der Folie. Innerhalb der quadratischen Folie stelle dir ein Netz aus k1- und k2-Koordinatenlinien vor, die man wie ein Netz aus Längen- und Breitengraden auffassen kann.

Jetzt wird diese quadratische Plastik-Folie verzerrt, indem jemand an den 4 Ecken anfasst und zieht. Danach ist ist diese Folie ein unregelmäßiges Viereck. Du möchtest nun eine Formel, die die Funktion f(P) nach der Verzerrung angibt. Das leistet genau die oben angegeben Formel. Die Koordinaten k1, k2 laufen genau wie vor der Verzerrung im Intervall [0;1].

Mehr kann man dazu nicht sagen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »