Wie interpoliert man linear mit 3 Punkten ?

Übersicht

BlitzBasic

Allgemein

	Bura.Tino Betreff: Wie interpoliert man linear mit 3 Punkten ?	Sa, März 06, 2010 0:47 Antworten mit Zitat
Servus. Habe leider im Forum nichts passendes oder verständliches gefunden. Deswegen mal eine Frage bezüglich linearer Interpolation. Folgendes Problem: Ich habe einen Startwert(bsp. 0) und einen Endwert(bsp. 100). Die ganzen Zwischenwerte zwischen 0.0 und 1.0 zu interpolieren ist kein Problem. In meinem Beispiel wäre der 75te Wert(bei 0.75) logischerweise 75. Was muss ich aber machen um 3 Werte zu Interpolieren, also mit Zwischenwerten ? (Die Werte sollen linear interpoliert werden. Also nix mit Bezier, Cubic etc.) Ein weiteres Beispiel: Startwert bei 0.0 = 0 Zwischenwert bei 0.75 = 90 Endwert bei 1.0 = 70 Wie kann man jetzt zwischen diesen Werten interpolieren ohne das man erst die eine Strecke berechnet und dann die zweite, sich also doppelt Arbeit macht ? Meines Erachtens nach müsste das doch eine Interpolation n-ten Grades sein, oder !?

Bura.Tino

Betreff: Wie interpoliert man linear mit 3 Punkten ?

Sa, März 06, 2010 0:47
Antworten mit Zitat

Servus.

Habe leider im Forum nichts passendes oder verständliches gefunden. Deswegen mal eine Frage bezüglich linearer Interpolation.

Folgendes Problem:
Ich habe einen Startwert(bsp. 0) und einen Endwert(bsp. 100). Die ganzen Zwischenwerte zwischen 0.0 und 1.0 zu interpolieren ist kein Problem. In meinem Beispiel wäre der 75te Wert(bei 0.75) logischerweise 75.

Was muss ich aber machen um 3 Werte zu Interpolieren, also mit Zwischenwerten ? (Die Werte sollen linear interpoliert werden. Also nix mit Bezier, Cubic etc.)

Ein weiteres Beispiel:
Startwert bei 0.0 = 0
Zwischenwert bei 0.75 = 90
Endwert bei 1.0 = 70

Wie kann man jetzt zwischen diesen Werten interpolieren ohne das man erst die eine Strecke berechnet und dann die zweite, sich also doppelt Arbeit macht ? Meines Erachtens nach müsste das doch eine Interpolation n-ten Grades sein, oder !?

	BladeRunner Moderator	Sa, März 06, 2010 8:16 Antworten mit Zitat
"Linear, also nix mit Bezier oder so." Wenn Du nicht in Kauf nimmst dass bei drei Punkten eine Kurve herauskommt kannst Du die werte nicht interpolieren falls nicht der Sonderfall eintritt das Punkt 3 auf der Verlängerung der Strecke 1-2 liegt. Dein gegebenes Beispiel setzt voraus dass sich die Steigung innerhalb des Betrachtungsraumes ändern kann. Das einzige was ich mir als 'Linien-interpolation' vorstellen kann ist dass Du von punkt1 zu punkt 2 nach der Steigung von 1-2 interpolierst und ab da nach der Steigung von 2 zu 3. Das gibt dann zackige Kurven.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Sa, März 06, 2010 8:16
Antworten mit Zitat

"Linear, also nix mit Bezier oder so."
Wenn Du nicht in Kauf nimmst dass bei drei Punkten eine Kurve herauskommt kannst Du die werte nicht interpolieren falls nicht der Sonderfall eintritt das Punkt 3 auf der Verlängerung der Strecke 1-2 liegt.
Dein gegebenes Beispiel setzt voraus dass sich die Steigung innerhalb des Betrachtungsraumes ändern kann.
Das einzige was ich mir als 'Linien-interpolation' vorstellen kann ist dass Du von punkt1 zu punkt 2 nach der Steigung von 1-2 interpolierst und ab da nach der Steigung von 2 zu 3. Das gibt dann zackige Kurven.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	darth	Sa, März 06, 2010 11:19 Antworten mit Zitat
Hallo, gleich wie Blade verstehe ich nicht wirklich, wie du interpolieren willst wenn du doch alles linear halten willst. Kann es sein, dass du eine Interpolation willst, ohne Bezier oder Splines zu benutzen? Falls ja, dann gibt es die Polynominterpolation, dazu gibt es zwei Ansätze, einen von Newton und einen von Lagrange, die beide das gleiche Ergebnis liefern, da das Interpolationspolynom eindeutig ist. Das Prinzip ist aber beschränkt auf "1D", du gibst einer Funktion eine Liste von X und Y Werten (deiner Stützpunkte), und einen X Wert, und du erhältst einen Y Wert zurück. Newton: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Function NewtonInterpolate#(X#[100], Y#[100], N, Px#) Local A#[100], P# For i=0 To N-1 A[i]=Y[i] Next For k=1 To N-1 For i=N-1 To k Step -1 A[i]=(A[i]-A[i-1])/(X[i]-X[i-k]) Next Next P=A[N-1] For k=(N-2) To 0 Step -1 P=A[k]+(Px-X[k])P Next Return P End Function Lagrange: BlitzBasic:* [AUSKLAPPEN] [EINKLAPPEN] Function LagrangeInterpolate#(X#[100], Y#[100], N, Px#) Local L#[100], P# For i=0 To N-1 L[i]=1 For k=0 To N-1 If i<>k L[i]=L[i](Px-X[k])/(X[i]-X[k]) EndIf Next P=P+L[i]Y[i] Next Return P End Function PS: Während der Arbeit an Perlin Noise bin ich auf diese Seite hier gestossen, wenn du da etwas runter scrollst, findest du eine Liste mit Interpolationswerten, da gibt es u.a. auch "Linear_Interpolation", die aber eigentlich gar nicht interpoliert.. Naja, schaus dir mal an. MfG, Darth --- Hallo nochmal, mir ist eingefallen, dass du vielleicht gar nicht Interpolation, sondern Regression meinst. Man hat eine gegebene Menge an Punkten und will eine Linie finden, die möglichst gut durch diese Punkte passt, aber keine KURVE, sondern eine GERADE. Um das zu lösen, braucht man die Methode der kleinsten Fehlerquadrate, und dazu ein wenig Matrizen Rechnerei und einen Algorithmus zum Lösen von linearen Gleichungssystem. Beispiel: Gegeben sind die Punkte P1=(0,0), P2=(10,12), P3=(20,20), gesucht ist eine Gerade y=ax+b, so dass sie möglichst gut durch alle Punkte geht. Dazu stellt man das Gleichungssystem auf: Code:* [AUSKLAPPEN] [EINKLAPPEN] 0 1 0 10 1 * a = 12 20 1 b 20 Das System ist nicht einfach so zu lösen, weil du mehr Stützwerte als Variabeln hast, es ist überdefiniert. Dem kann man sich helfen, indem man nicht Sv=y löst, sonder S^T S * v = S^T y, man transponiert also die Matrix S, und multipliziert von links. Dann kommt man auf ein ausgeglichenes Gleichungssystem, das man lösen kann. Aber wie gesagt müsste man sich sowas zuerst einmal schreiben, ich habe hier mal ein paar Dinge davon implementiert (Direktlink), vielleicht ist es das, was du brauchst. MfG, Darth

darth

Sa, März 06, 2010 11:19
Antworten mit Zitat

Hallo,

gleich wie Blade verstehe ich nicht wirklich, wie du interpolieren willst wenn du doch alles linear halten willst. Kann es sein, dass du eine Interpolation willst, ohne Bezier oder Splines zu benutzen? Falls ja, dann gibt es die Polynominterpolation, dazu gibt es zwei Ansätze, einen von Newton und einen von Lagrange, die beide das gleiche Ergebnis liefern, da das Interpolationspolynom eindeutig ist.

Das Prinzip ist aber beschränkt auf "1D", du gibst einer Funktion eine Liste von X und Y Werten (deiner Stützpunkte), und einen X Wert, und du erhältst einen Y Wert zurück.

Newton:

BlitzBasic: [AUSKLAPPEN]

Function NewtonInterpolate#(X#[100], Y#[100], N, Px#)
	Local A#[100], P#
	
	For i=0 To N-1
		A[i]=Y[i]
	Next
	
	For k=1 To N-1
		For i=N-1 To k Step -1
			A[i]=(A[i]-A[i-1])/(X[i]-X[i-k])
		Next
	Next
	
	P=A[N-1]
	For k=(N-2) To 0 Step -1
		P=A[k]+(Px-X[k])*P
	Next
	
	Return P
End Function

Lagrange:

BlitzBasic: [AUSKLAPPEN]

Function LagrangeInterpolate#(X#[100], Y#[100], N, Px#)
	Local L#[100], P#
	
	For i=0 To N-1
		L[i]=1
		
		For k=0 To N-1
			If i<>k
				L[i]=L[i]*(Px-X[k])/(X[i]-X[k])
			EndIf
		Next
		
		P=P+L[i]*Y[i]
	Next
	
	Return P
End Function

PS:
Während der Arbeit an Perlin Noise bin ich auf diese Seite hier gestossen, wenn du da etwas runter scrollst, findest du eine Liste mit Interpolationswerten, da gibt es u.a. auch "Linear_Interpolation", die aber eigentlich gar nicht interpoliert..

Naja, schaus dir mal an.
MfG,
Darth

---

Hallo nochmal,

mir ist eingefallen, dass du vielleicht gar nicht Interpolation, sondern Regression meinst. Man hat eine gegebene Menge an Punkten und will eine Linie finden, die möglichst gut durch diese Punkte passt, aber keine KURVE, sondern eine GERADE.

Um das zu lösen, braucht man die Methode der kleinsten Fehlerquadrate, und dazu ein wenig Matrizen Rechnerei und einen Algorithmus zum Lösen von linearen Gleichungssystem.

Beispiel:

Gegeben sind die Punkte P1=(0,0), P2=(10,12), P3=(20,20), gesucht ist eine Gerade y=a*x+b, so dass sie möglichst gut durch alle Punkte geht. Dazu stellt man das Gleichungssystem auf:

Code: [AUSKLAPPEN]

0 1 0
10 1 * a = 12
20 1 b 20

Das System ist nicht einfach so zu lösen, weil du mehr Stützwerte als Variabeln hast, es ist überdefiniert. Dem kann man sich helfen, indem man nicht S*v=y löst, sonder S^T * S * v = *S^T * y, man transponiert also die Matrix S, und multipliziert von links. Dann kommt man auf ein ausgeglichenes Gleichungssystem, das man lösen kann.

Aber wie gesagt müsste man sich sowas zuerst einmal schreiben, ich habe hier mal ein paar Dinge davon implementiert (Direktlink), vielleicht ist es das, was du brauchst.

MfG,
Darth

Zuletzt bearbeitet von darth am Sa, März 06, 2010 13:59, insgesamt einmal bearbeitet

	Bura.Tino	Sa, März 06, 2010 13:50 Antworten mit Zitat
Vielen Dank für die schnellen Antworten. Mir ist aufgefallen, das die Farbverlaufsfunktion in Photoshop wahrscheinlich so funktioniert wie ich es meinte. Ich brauchs zwar nicht für Farben, aber Farbwerte sind ja auch nur Werte. Also hab ich hier im Forum mal nach 'Farbverlauf' gesucht und einige interessante Ansätze gefunden. Diese werde ich jetzt erstmal ganz genau studieren.
<- Ich liebe dieses Smilie !

Bura.Tino

Sa, März 06, 2010 13:50
Antworten mit Zitat

Vielen Dank für die schnellen Antworten.

Mir ist aufgefallen, das die Farbverlaufsfunktion in Photoshop wahrscheinlich so funktioniert wie ich es meinte. Ich brauchs zwar nicht für Farben, aber Farbwerte sind ja auch nur Werte.
Also hab ich hier im Forum mal nach 'Farbverlauf' gesucht und einige interessante Ansätze gefunden. Diese werde ich jetzt erstmal ganz genau studieren. Smile

<- Ich liebe dieses Smilie ! Very Happy

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Wie interpoliert man linear mit 3 Punkten ?

Bura.Tino

Betreff: Wie interpoliert man linear mit 3 Punkten ?

BladeRunner

darth

Bura.Tino