[Alg] Functie bepalen voor kromme lijn

[jvdmeer]

Stel ik heb de volgende punten:


In dit voorbeeld is ∆x constant, in de praktijk helaas niet. Ik ben op zoek naar de formule om de punten van lijnstuk A (tussen punten 2 en 3) te bepalen. Hierbij zoek ik een 'zachte' vorm (geel) loopt in plaats van hoekig (zwart). Mijn veranderstelling is dat de vorm en daarmee de functie van de lijn wordt bepaald door de coördinaten van de punten 1 t/m 4.
Ik ben dus op naar de formule

f(x)= .....

Op zoek naar de juiste formule op internet kwam ik al langs de termen 'fourier' en 'bezier', maar ik kan maar niet vatten hoe ik die moet gebruiken. Kan iemand me op gang helpen om de juiste formule te vinden?

[ Voor 8% gewijzigd door jvdmeer op 20-02-2004 21:34 . Reden: img-tag aangepast ]

[Henk007]

Waar heb je dit voor nodig? Wil je interpoleren tussen gemeten waardes? Dan kun je curve-fitting toepassen met een polynoom van de graad n via de kleinste kwadraten methode; de som van (f(x)-meetpunt(x))^2 is minimaal.

code:

f(x)=a+b*x+c*x^2+d*x^3 enz...

Het lijkt erop dat je als eis stelt dat de punten in je grafiek op de curve liggen. Dan is curve-fitting niet de oplossing.

[.oisyn]

Met curves/splines kan het wel goed. De Catmull-Rom spline lijkt me het best hier, die gaat door alle opgegeven punten. Het punt is echter alleen dat je ∆x niet constant is, waardoor je een 2d curve moet gebruiken (gegeven een variabele, dan is je resultaat een x- en y-coördinaat)

.edit: het lukt je sowieso niet om het in 1 functie te gooien, ik neem aan dat het alleen gaat om het tekenen? In dat geval is het niet zo erg dat je een 2D curve gebruikt

[ Voor 24% gewijzigd door .oisyn op 20-02-2004 22:09 ]

[Knutselsmurf]

En als je wel op zoek bent naar bezier-curven, dan volgt nu een korte uitleg:

Bezier-curven zijn parametrische curven. Dat wil zeggen dat x en y een functie zijn van een parameter u. De functieset x(u)=(1-u)*x1+u*x2,y(u)=(1-u)*y1+u*y2 zal voor het interval u=[0,1] een rechten lijn tussen de punten x1,y1 en x2,y2 opleveren. Waarbij u=0.5 het punt precies tussen x1,y1 en x2,y2 in. De bezier-curven werken op een dergelijke manier.

Als functieset worden de volgende functies gekozen:

code:

x(u)=a1+b1*u+c1*u^2+d1*u^3
y(u)=a2+b2*u+c2*u^2+d2*u^3

Dit betekent dat we 8 onbekenden hebben. Om tot een eenduidige oplossing te komen, zullen we dus 8 vergelijkingen nodig hebben. Met 2 vergelijkingen per punt (1 voor x en 1 voor y) hebben we dus 4 punten nodig.

Uitgewerkt naar een bezier-curve, die iets anders opgezet is, omdattie ook met afgeleiden werkt, is uiteindelijk de volgende vergelijking te achterhalen:

p(u)=p₀(1-3u+3u²-u³) + p₁(3u-6u²+3u³) + p₂(3u²-3u³) + p₃(u³)

De dikke p staat hier voor een vector. De P(u) is een combinatie van x(u) en y(u). En p0 staat dan dus voor de (x,y) coordinaten van het eerste punt.

Hier geldt wederom dat u van 0 tot 1 loopt.

[.oisyn]

Dit is een wellicht simpelere uitleg:

Knutselsmurf heeft het over 2d curves, maar in principe zijn ze er in elke dimensie. Een n-dimensionale curve is eigenlijk gewoon n aparte curves voor elke dimensie.

Bezier curves zijn er in verschillende gradaties. Een lineaire bezier heeft 2 control points, en is eigenlijk gewoon een lineaire interpolatie van punt 1 naar punt 2. Dus zeg maar
[i]x(t) = x₀ * (1 - t) + x₁ * t
x₀ en x₁ zijn hier de control points, en t ligt in het bereik [0, 1]

Laat ik bovenstaande vergelijking even op een generieke manier herschrijven als
x(t) = lerp (x₀, x₁, t)

waarbij lerp staat voor llinear interpolation (dit is een veelgebruikte term hiervoor), en dus eigenlijk gewoon interpoleert tussen de 2 punten aan de hand van t

Een quadratische bezier heeft 3 control points, de lijn wordt dan getrokken tussen het begin en eindpunt (dat is altijd het geval bij beziers), en de lijn begint in de richting van het 2e punt te gaan, en aan het eind heeft ie ook de richting van punt 2 naar punt 3. Deze bezier is gedefinieerd als een combinatie van lineare interpolaties:
a = lerp (x₀, x₁, t)
b = lerp (x₁, x₂, t)
x(t) = lerp (a, b, t)

De kubieke bezier, de meest gebruikte, heeft 4 control points, en is gedefinieerd als
a = lerp (x₀, x₁, t)
b = lerp (x₁, x₂, t)
c = lerp (x₂, x₃, t)
p = lerp (a, b, t)
q = lerp (b, c, t)
x(t) = lerp (p, q, t)

In het algemeen interpoleer je dus steeds tussen alle control points naar een set nieuwe control points (je hebt er dan 1 minder over), en dat doe je net zo lang tot je er nog maar 1 overhoudt

Maar zoals ik al zei, een bezier begint bij het eerste punt, en eindigt bij het laatste, en de punten die ertussenin liggen bepalen hoe de curve zich gedraagt tussen deze punten. Maar ze gaan niet door deze punten.

Dit in tegenstelling tot de catmull-rom curve, die ook kubiek is en dus 4 control points heeft. De curve begint bij het 2e en eindigt bij het 3e punt, en het 1e en 4e bepalen de start en eindrichting van de curve. Maar nu komt het handige hieraan: Als je er een 5e controlpoint bijpakt, en je tekent eerst een curve over de punten 1 t/m 4, en daarna eentje over de punten 2 t/m 5, dan krijg je een vloeiende lijn

Je kunt zo'n curve in jouw voorbeeld gewoon definieren met de punten 1 t/m 4, en de daadwerkelijke lijn die getekend wordt is het stukje van 2 naar 3. Om het stukje van 3 naar 4 te tekenen gooi je punt 1 dus weg, en plak je het volgende punt erachter. Zo kun je door je hele grafiek heengaan, en hoef je ook niet moelijk te doen om tussenliggende controlpoints uit te rekenen, zoals dat bij een bezier wel moet.

Ik zal even de definitie van de catmull-rom curve opzoeken, moment
.edit:

a = 2 * x₁ - f * (x₀ - x₁ - x₂ - x₃)
b = f * (2 * x₀ + x₁ - 2 * x₂ - x₃) - 3 * (x₁ - x₂)
c = f * (x₂ - x₀)
d = x₁
x(t) = a*t³ + b*t² + c*t + d

(
Of met Horner's rule, minder vermenigvuldigingen en dus sneller:
x(t) = ((a * t + b ) * t + c) * t + d
)

.edit: oh, vergeet ik nog bij te zeggen: de f in deze is een soort van "curvyness" parameter, daarmee kun je bepalen hoe vloeiend de lijn loopt. Ik geloof dat een f van 1 of 0.5 de standaard catmull-rom geeft

[ Voor 45% gewijzigd door .oisyn op 20-02-2004 23:06 ]

[jvdmeer]

.oisyn schreef op 20 februari 2004 @ 22:05:
Met curves/splines kan het wel goed. De Catmull-Rom spline lijkt me het best hier, die gaat door alle opgegeven punten.

Ik heb inmiddels even mee zitten zoeken en ik denk dat ik inderdaad verder moet richting "Catmull"-spline. Zeker als ik het linker schermpje zie van dit voorbeeld

.oisyn schreef op 20 februari 2004 @ 22:05:Het punt is echter alleen dat je ∆x niet constant is, waardoor je een 2d curve moet gebruiken (gegeven een variabele, dan is je resultaat een x- en y-coördinaat)

Als ik het goed begrijp, krijg je dus na ingave van x₁,y₁...x₄,y₄ 2 formules, waarmee je via 1 enkele parameter dus een x en een y krijgt:

x=f₁(p)
y=f₂(p)

.oisyn schreef op 20 februari 2004 @ 22:05:.edit: het lukt je sowieso niet om het in 1 functie te gooien, ik neem aan dat het alleen gaat om het tekenen? In dat geval is het niet zo erg dat je een 2D curve gebruikt

Bedoel je met "niet in 1 functie" dat je zoals ik net suggereer, twee formules krijgt? Of dat je na invoer van de variabele een hele reeks berekeningen moet maken voordat je de x en y weet?

Het gaat in mijn geval om een serie van ca. 2000 punten. waarbij ik de gekozen 4 of 6 punten als een soort van window over deze reeks wil laten lopen om een afgeronde vorm te krijgen. Afhankelijk van de invoer van de gebruiker is heb ik andere gegevens nodig. De meest waarschijnlijke keuze zal zijn dat ∆x standaard wordt gemaakt dat ik alle nieuwe y waarden nodig heb.
Of dat de lengte van het lijnstuk constant is, oftewel dat ik langs de gehele lijn alle nieuwe (x,y) nodig heb waarvoor geldt √(∆x²+∆ y²) = constant.

Is er ergens een duidelijke uitleg over Catmull-splines?

Kort samengevat, ik hoef er niet mee te tekenen, alleen te rekenen.

Bezier valt af, omdat deze niet dòòr de betreffende punten gaat.

[.oisyn]

jvdmeer schreef op 20 februari 2004 @ 22:50:
Bedoel je met "niet in 1 functie" dat je zoals ik net suggereer, twee formules krijgt? Of dat je na invoer van de variabele een hele reeks berekeningen moet maken voordat je de x en y weet?

ik bedoel met 1 functie dat je niet gewoon een f(x) zoals in jouw voorbeeld krijgt die je van begin tot eind uit kunt rekenen. Je krijgt per lijnstukje dus aparte formules.[/quote]

[jvdmeer]

Ga inderdaad even verder met Catmull. Heb inmiddels hier een pascal versie gevonden voor deze spline.

Ga nog kijken hoe ik die kan gebruiken.

Wiskunde is voor al teveel jaar geleden

Want ik zie even nog niet het verband tussen een kromme lijn en de matrix:

code:

-1   3  -3   1
 2  -5   4  -1
-1   0   1   0
 0   2   0   0

[.oisyn]

Die moet je vermenigvuldigen met de 3 controlpoints en de vector [t³, t², t, 1]

Nou weet ik alleen niet meer uit mijn hoofd wat de volgorde precies was, ik haal uit de matrix altijd de factoren voor t³, t², t en 1 zodat het snel en iteratief uit te rekenen is

Ik geloof dat het zo zat:

code:

                     [-1   3  -3   1]     [x0]
[t^3, t^2, t, 1]  *  [ 2  -5   4  -1]  *  [x1]
                     [-1   0   1   0]     [x2]
                     [ 0   2   0   0]     [x3]

Alleen als ik dit uitschrijf dan klopt het niet helemaal met wat ik hierboven schrijf
(en de control-point vector en t-vector omwisselen klopt al helemaal niet, dus dat is het sowieso niet)

[ Voor 8% gewijzigd door .oisyn op 23-02-2004 13:03 ]