Mixing
Formula or Algorithm to Draw curved lines between points
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I'm developing a script to connect point with curved lines.
The points are in ascendent order in x-axis like this:
I'm studying Bezier Curves, but I don't think it's the best solution (see https://www.geogebra.org/m/qcnExXbn):
But, instead of straight lines, I just would like to connect these points in a smooth way.
Could anyone help me with a formula or algorithm?
algorithms curves
asked Aug 3 at 22:49
Rogério Dec
1166
 |Â
show 8 more comments
up vote
1
down vote
favorite
I'm developing a script to connect point with curved lines.
The points are in ascendent order in x-axis like this:
I'm studying Bezier Curves, but I don't think it's the best solution (see https://www.geogebra.org/m/qcnExXbn):
But, instead of straight lines, I just would like to connect these points in a smooth way.
Could anyone help me with a formula or algorithm?
algorithms curves
asked Aug 3 at 22:49
Rogério Dec
1166
Why have you decided Bezier curves (aka cubic splines) are not what you want? It's good enough for Postscript's CurveTo...
– David C. Ullrich
Aug 3 at 23:05
Is this close to what you're looking for? en.wikipedia.org/wiki/Polynomial_interpolation
– Robert Howard
Aug 3 at 23:19
@David C. Ullrich I'm not wanting to use Bezier Curves because I need the line to "touch" the point and the Bezier Curve will just stay between the points, on average, without reaching them completely.
– Rogério Dec
Aug 3 at 23:20
1
@Robert Howard, it seems to be quite so. Thank you!
– Rogério Dec
Aug 3 at 23:22
You're certainly welcome! I'm going to post an answer about it, too, just so this question doesn't sit in the "unanswered" queue for ages.
– Robert Howard
Aug 3 at 23:25
 |Â
show 8 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'm developing a script to connect point with curved lines.
The points are in ascendent order in x-axis like this:
I'm studying Bezier Curves, but I don't think it's the best solution (see https://www.geogebra.org/m/qcnExXbn):
But, instead of straight lines, I just would like to connect these points in a smooth way.
Could anyone help me with a formula or algorithm?
algorithms curves
asked Aug 3 at 22:49
Rogério Dec
1166
I'm developing a script to connect point with curved lines.
The points are in ascendent order in x-axis like this:
I'm studying Bezier Curves, but I don't think it's the best solution (see https://www.geogebra.org/m/qcnExXbn):
But, instead of straight lines, I just would like to connect these points in a smooth way.
Could anyone help me with a formula or algorithm?
algorithms curves
asked Aug 3 at 22:49
Rogério Dec
1166
edited Aug 4 at 0:02
asked Aug 3 at 22:49
Rogério Dec
1166
asked Aug 3 at 22:49
Rogério Dec
1166
asked Aug 3 at 22:49
Rogério Dec
1166
1166
Why have you decided Bezier curves (aka cubic splines) are not what you want? It's good enough for Postscript's CurveTo...
– David C. Ullrich
Aug 3 at 23:05
Is this close to what you're looking for? en.wikipedia.org/wiki/Polynomial_interpolation
– Robert Howard
Aug 3 at 23:19
@David C. Ullrich I'm not wanting to use Bezier Curves because I need the line to "touch" the point and the Bezier Curve will just stay between the points, on average, without reaching them completely.
– Rogério Dec
Aug 3 at 23:20
1
@Robert Howard, it seems to be quite so. Thank you!
– Rogério Dec
Aug 3 at 23:22
You're certainly welcome! I'm going to post an answer about it, too, just so this question doesn't sit in the "unanswered" queue for ages.
– Robert Howard
Aug 3 at 23:25
 |Â
show 8 more comments
Why have you decided Bezier curves (aka cubic splines) are not what you want? It's good enough for Postscript's CurveTo...
– David C. Ullrich
Aug 3 at 23:05
Is this close to what you're looking for? en.wikipedia.org/wiki/Polynomial_interpolation
– Robert Howard
Aug 3 at 23:19
@David C. Ullrich I'm not wanting to use Bezier Curves because I need the line to "touch" the point and the Bezier Curve will just stay between the points, on average, without reaching them completely.
– Rogério Dec
Aug 3 at 23:20
1
@Robert Howard, it seems to be quite so. Thank you!
– Rogério Dec
Aug 3 at 23:22
You're certainly welcome! I'm going to post an answer about it, too, just so this question doesn't sit in the "unanswered" queue for ages.
– Robert Howard
Aug 3 at 23:25
Why have you decided Bezier curves (aka cubic splines) are not what you want? It's good enough for Postscript's CurveTo...
– David C. Ullrich
Aug 3 at 23:05
Why have you decided Bezier curves (aka cubic splines) are not what you want? It's good enough for Postscript's CurveTo...
– David C. Ullrich
Aug 3 at 23:05
Is this close to what you're looking for? en.wikipedia.org/wiki/Polynomial_interpolation
– Robert Howard
Aug 3 at 23:19
Is this close to what you're looking for? en.wikipedia.org/wiki/Polynomial_interpolation
– Robert Howard
Aug 3 at 23:19
@David C. Ullrich I'm not wanting to use Bezier Curves because I need the line to "touch" the point and the Bezier Curve will just stay between the points, on average, without reaching them completely.
– Rogério Dec
Aug 3 at 23:20
@David C. Ullrich I'm not wanting to use Bezier Curves because I need the line to "touch" the point and the Bezier Curve will just stay between the points, on average, without reaching them completely.
– Rogério Dec
Aug 3 at 23:20
1
1
@Robert Howard, it seems to be quite so. Thank you!
– Rogério Dec
Aug 3 at 23:22
@Robert Howard, it seems to be quite so. Thank you!
– Rogério Dec
Aug 3 at 23:22
You're certainly welcome! I'm going to post an answer about it, too, just so this question doesn't sit in the "unanswered" queue for ages.
– Robert Howard
Aug 3 at 23:25
You're certainly welcome! I'm going to post an answer about it, too, just so this question doesn't sit in the "unanswered" queue for ages.
– Robert Howard
Aug 3 at 23:25
 |Â
show 8 more comments
3 Answers
3
active
oldest
votes
up vote
1
down vote
Cubic Bezier spline is perfectly suitable
to smoothly connect the points.
Given an ordered sequence of $n$ points
$p_0,dots p_n-1$, we need to define $n$
cubic Bezier segments.
The points on the $k$-th segment are defined
parametrically as
beginalign
s_k(t)=&a_k(1-t)^3+3b_k(1-t)^2t+3c_k(1-t)t^2+d_k t^3
,quad tin[0,1]
tag1label1
.
endalign
The first and second derivatives of eqref1 are given by
beginalign
s_k'(t)=&3((b_k-a_k)(1-t)^2+2(c_k-b_k)(1-t)t+(d_k-c_k)t^2)
tag2label2
,\
s_k''(t)=&6((a_k-2b_k+c_k)(1-t)+(b_k-2c_k+d_k)t)
tag3label3
.
endalign
So, we need to define $a_k,b_k,c_k,d_k$
that satisfy
(all indices here are taken $mod,n$):
beginalign
s_k'(0)=s_k-1'(1)&Rightarrow
&quad b_k-a_k =&d_k-1-c_k-1
\
s_k+1'(0)=s_k'(1)&Rightarrow
&quad b_k+1-a_k+1=&
d_k-c_k
\
s_k''(0)=s_k-1''(1)&Rightarrow
&quad c_k-2b_k+a_k=&
d_k-1-2c_k-1+b_k-1
endalign
Excluding $c_k-1$
and using
$d_k=a_k+1$,
we arrive at $ntimes n$ linear system
for $b_k$:
beginalign
b_k-1+4b_k+b_k+1=4a_k+2a_k+1
tag4label4
\
textfor k=0,dots,n-1
.
endalign
Then $c_k$ can be easily found:
beginalign
c_k&=2a_k+1-b_k+1
.
endalign
Example:
In case if the curve is not closed,
you can try this answer.
answered Aug 4 at 0:58
g.kov
5,5171716
You should include a plot going thhrough the points in the OP. I can't figure out a way to post my eps file...
– David C. Ullrich
Aug 4 at 1:05
add a comment |Â
up vote
1
down vote
I've actually done a lot of curve drawing "by hand" - all the curves in the figures in Complex Made Simple were drawn using PostScript's curveto function, which is Bezier curves. If you try polynomial interpolation I predict you won't like the results - the curve passing though $p_1,dots p_n$ has funny wiggles near $p_1$ due to the exact location of the other points.
I don't know what you're talking about when you say Bezier curves don't touch the points. A bezier curve is specified by four points; it passes through two of those points exactly, and the tangent vectors at those two endpoints are determined by the two "control points". The interface in terms of "control points" makes no sense to me - I wrote code to convert endpoints and tangent vectors at endpoints to endpoints and control points.
You don't say in what sense you want to "draw" this curve. If you want to write PostScript, here's what to do.
Say you want a curve $c:[0,1]toBbb R^2$ with $c(0)=(x,y)$, $c(1)=(xx,yy)$, $c'(0)=(dx,dy)$ and $c'(1)=(dxx,dyy)$. The following two lines of PostScript give you exactly that:
x y moveto
x+dx/3 y+dy/3 xx-dxx/3 y-dyy/3 xx yy curveto
Not that text literally - you want strings giving the numeric value of expressions. For exammple if $(x,y)=(0,0)$, $(xx,yy)=(1,1)$, $(dx,dy)=(1,1)$ and $(dxx,dyy)=(2,3)$ you'd say
0 0 moveto
0.3333 0.3333 0.3333 0 1 1 curveto
I actually did that to get a curve passing through those points.
Then I found this thing doesn't recognize eps as an image format.
Here's a screen shot.
(This was tedious enough - your points $A,B,dots$ are just marked
with X's.):
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
I edited my question and put a picture of a Bezier Curve simulation for you to understand. You will notice that the lines are "between" the dots and do not "touch" them ...
– Rogério Dec
Aug 4 at 0:04
When I said you should use Bezier curves I didn't mean that you'd get good results if you did it totally wrong.
– David C. Ullrich
Aug 4 at 0:23
add a comment |Â
up vote
0
down vote
Given an arbitrary set of $n$ points, it's possible to find the equation of a unique polynomial of degree at most $n-1$ that passes through all $n$ points.
Let's consider a very simple example; say we we wanted to find the parabola that passes through the points $(-4,2)$, $(-2,-1)$, and $(1,1)$.
The general equation of a parabola is $$y=ax^2+bx+c$$ so we can substitute the $x$- and $y$-coordinates of the three points we have to create a system of three equations with three unknowns, like so:
$$beginalign
2&=16a-4b+c \
-1&=4a-2b+c \
1&=a+b+c
endalign$$
Solving this system, we find that $a=frac1330$, $b=frac1110$, and $c=frac-815$. The parabola $y=frac1330x^2+frac1110x-frac815$ does indeed pass cleanly through all three points, so we're done.
And of course, you could do this with a system of six equations with six unknowns as well, but that would just take a little longer than this example.
Edit:
Mathematica reveals that the interpolating polynomial for those six points is approximately
$$y=1.51771x^5-10.5198x^4+23.6478x^3-17.2688x^2-0.696339x+2.81946$$
The graph of that function looks like this:
answered Aug 3 at 23:42
Robert Howard
1,241620
Have you actually done this, with more than three points? In my experience interpolating polynomials don't give the results one wants here - they have funny wiggles in funny directions.
– David C. Ullrich
Aug 3 at 23:50
I admit I've never used interpolation to find anything higher than a third-degree polynomial, but it's always worked well for me in those relatively simple cases. What do you mean by "funny wiggles?"
– Robert Howard
Aug 3 at 23:53
Take the points in his figure, find the interpolating polynomial and draw it - you'll see what I mean.
– David C. Ullrich
Aug 4 at 0:19
Come on! I went to some trouble to make an eps file showing what the Bezier looks like - show us what you get using polynomial interpolation..
– David C. Ullrich
Aug 4 at 1:23
I see how one could call the local extrema "funny wiggles," but it does connect the points in a smooth way, like the OP asked for. If, on the other hand, he was really after a closed curve all along, then I agree that polynomial interpolation is certainly not the way to go.
– Robert Howard
Aug 4 at 2:21
 |Â
show 2 more comments
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Cubic Bezier spline is perfectly suitable
to smoothly connect the points.
Given an ordered sequence of $n$ points
$p_0,dots p_n-1$, we need to define $n$
cubic Bezier segments.
The points on the $k$-th segment are defined
parametrically as
beginalign
s_k(t)=&a_k(1-t)^3+3b_k(1-t)^2t+3c_k(1-t)t^2+d_k t^3
,quad tin[0,1]
tag1label1
.
endalign
The first and second derivatives of eqref1 are given by
beginalign
s_k'(t)=&3((b_k-a_k)(1-t)^2+2(c_k-b_k)(1-t)t+(d_k-c_k)t^2)
tag2label2
,\
s_k''(t)=&6((a_k-2b_k+c_k)(1-t)+(b_k-2c_k+d_k)t)
tag3label3
.
endalign
So, we need to define $a_k,b_k,c_k,d_k$
that satisfy
(all indices here are taken $mod,n$):
beginalign
s_k'(0)=s_k-1'(1)&Rightarrow
&quad b_k-a_k =&d_k-1-c_k-1
\
s_k+1'(0)=s_k'(1)&Rightarrow
&quad b_k+1-a_k+1=&
d_k-c_k
\
s_k''(0)=s_k-1''(1)&Rightarrow
&quad c_k-2b_k+a_k=&
d_k-1-2c_k-1+b_k-1
endalign
Excluding $c_k-1$
and using
$d_k=a_k+1$,
we arrive at $ntimes n$ linear system
for $b_k$:
beginalign
b_k-1+4b_k+b_k+1=4a_k+2a_k+1
tag4label4
\
textfor k=0,dots,n-1
.
endalign
Then $c_k$ can be easily found:
beginalign
c_k&=2a_k+1-b_k+1
.
endalign
Example:
In case if the curve is not closed,
you can try this answer.
answered Aug 4 at 0:58
g.kov
5,5171716
You should include a plot going thhrough the points in the OP. I can't figure out a way to post my eps file...
– David C. Ullrich
Aug 4 at 1:05
add a comment |Â
up vote
1
down vote
Cubic Bezier spline is perfectly suitable
to smoothly connect the points.
Given an ordered sequence of $n$ points
$p_0,dots p_n-1$, we need to define $n$
cubic Bezier segments.
The points on the $k$-th segment are defined
parametrically as
beginalign
s_k(t)=&a_k(1-t)^3+3b_k(1-t)^2t+3c_k(1-t)t^2+d_k t^3
,quad tin[0,1]
tag1label1
.
endalign
The first and second derivatives of eqref1 are given by
beginalign
s_k'(t)=&3((b_k-a_k)(1-t)^2+2(c_k-b_k)(1-t)t+(d_k-c_k)t^2)
tag2label2
,\
s_k''(t)=&6((a_k-2b_k+c_k)(1-t)+(b_k-2c_k+d_k)t)
tag3label3
.
endalign
So, we need to define $a_k,b_k,c_k,d_k$
that satisfy
(all indices here are taken $mod,n$):
beginalign
s_k'(0)=s_k-1'(1)&Rightarrow
&quad b_k-a_k =&d_k-1-c_k-1
\
s_k+1'(0)=s_k'(1)&Rightarrow
&quad b_k+1-a_k+1=&
d_k-c_k
\
s_k''(0)=s_k-1''(1)&Rightarrow
&quad c_k-2b_k+a_k=&
d_k-1-2c_k-1+b_k-1
endalign
Excluding $c_k-1$
and using
$d_k=a_k+1$,
we arrive at $ntimes n$ linear system
for $b_k$:
beginalign
b_k-1+4b_k+b_k+1=4a_k+2a_k+1
tag4label4
\
textfor k=0,dots,n-1
.
endalign
Then $c_k$ can be easily found:
beginalign
c_k&=2a_k+1-b_k+1
.
endalign
Example:
In case if the curve is not closed,
you can try this answer.
answered Aug 4 at 0:58
g.kov
5,5171716
You should include a plot going thhrough the points in the OP. I can't figure out a way to post my eps file...
– David C. Ullrich
Aug 4 at 1:05
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Cubic Bezier spline is perfectly suitable
to smoothly connect the points.
Given an ordered sequence of $n$ points
$p_0,dots p_n-1$, we need to define $n$
cubic Bezier segments.
The points on the $k$-th segment are defined
parametrically as
beginalign
s_k(t)=&a_k(1-t)^3+3b_k(1-t)^2t+3c_k(1-t)t^2+d_k t^3
,quad tin[0,1]
tag1label1
.
endalign
The first and second derivatives of eqref1 are given by
beginalign
s_k'(t)=&3((b_k-a_k)(1-t)^2+2(c_k-b_k)(1-t)t+(d_k-c_k)t^2)
tag2label2
,\
s_k''(t)=&6((a_k-2b_k+c_k)(1-t)+(b_k-2c_k+d_k)t)
tag3label3
.
endalign
So, we need to define $a_k,b_k,c_k,d_k$
that satisfy
(all indices here are taken $mod,n$):
beginalign
s_k'(0)=s_k-1'(1)&Rightarrow
&quad b_k-a_k =&d_k-1-c_k-1
\
s_k+1'(0)=s_k'(1)&Rightarrow
&quad b_k+1-a_k+1=&
d_k-c_k
\
s_k''(0)=s_k-1''(1)&Rightarrow
&quad c_k-2b_k+a_k=&
d_k-1-2c_k-1+b_k-1
endalign
Excluding $c_k-1$
and using
$d_k=a_k+1$,
we arrive at $ntimes n$ linear system
for $b_k$:
beginalign
b_k-1+4b_k+b_k+1=4a_k+2a_k+1
tag4label4
\
textfor k=0,dots,n-1
.
endalign
Then $c_k$ can be easily found:
beginalign
c_k&=2a_k+1-b_k+1
.
endalign
Example:
In case if the curve is not closed,
you can try this answer.
answered Aug 4 at 0:58
g.kov
5,5171716
Cubic Bezier spline is perfectly suitable
to smoothly connect the points.
Given an ordered sequence of $n$ points
$p_0,dots p_n-1$, we need to define $n$
cubic Bezier segments.
The points on the $k$-th segment are defined
parametrically as
beginalign
s_k(t)=&a_k(1-t)^3+3b_k(1-t)^2t+3c_k(1-t)t^2+d_k t^3
,quad tin[0,1]
tag1label1
.
endalign
The first and second derivatives of eqref1 are given by
beginalign
s_k'(t)=&3((b_k-a_k)(1-t)^2+2(c_k-b_k)(1-t)t+(d_k-c_k)t^2)
tag2label2
,\
s_k''(t)=&6((a_k-2b_k+c_k)(1-t)+(b_k-2c_k+d_k)t)
tag3label3
.
endalign
So, we need to define $a_k,b_k,c_k,d_k$
that satisfy
(all indices here are taken $mod,n$):
beginalign
s_k'(0)=s_k-1'(1)&Rightarrow
&quad b_k-a_k =&d_k-1-c_k-1
\
s_k+1'(0)=s_k'(1)&Rightarrow
&quad b_k+1-a_k+1=&
d_k-c_k
\
s_k''(0)=s_k-1''(1)&Rightarrow
&quad c_k-2b_k+a_k=&
d_k-1-2c_k-1+b_k-1
endalign
Excluding $c_k-1$
and using
$d_k=a_k+1$,
we arrive at $ntimes n$ linear system
for $b_k$:
beginalign
b_k-1+4b_k+b_k+1=4a_k+2a_k+1
tag4label4
\
textfor k=0,dots,n-1
.
endalign
Then $c_k$ can be easily found:
beginalign
c_k&=2a_k+1-b_k+1
.
endalign
Example:
In case if the curve is not closed,
you can try this answer.
answered Aug 4 at 0:58
g.kov
5,5171716
edited Aug 4 at 1:40
answered Aug 4 at 0:58
g.kov
5,5171716
answered Aug 4 at 0:58
g.kov
5,5171716
answered Aug 4 at 0:58
g.kov
5,5171716
5,5171716
You should include a plot going thhrough the points in the OP. I can't figure out a way to post my eps file...
– David C. Ullrich
Aug 4 at 1:05
add a comment |Â
You should include a plot going thhrough the points in the OP. I can't figure out a way to post my eps file...
– David C. Ullrich
Aug 4 at 1:05
You should include a plot going thhrough the points in the OP. I can't figure out a way to post my eps file...
– David C. Ullrich
Aug 4 at 1:05
You should include a plot going thhrough the points in the OP. I can't figure out a way to post my eps file...
– David C. Ullrich
Aug 4 at 1:05
add a comment |Â
up vote
1
down vote
I've actually done a lot of curve drawing "by hand" - all the curves in the figures in Complex Made Simple were drawn using PostScript's curveto function, which is Bezier curves. If you try polynomial interpolation I predict you won't like the results - the curve passing though $p_1,dots p_n$ has funny wiggles near $p_1$ due to the exact location of the other points.
I don't know what you're talking about when you say Bezier curves don't touch the points. A bezier curve is specified by four points; it passes through two of those points exactly, and the tangent vectors at those two endpoints are determined by the two "control points". The interface in terms of "control points" makes no sense to me - I wrote code to convert endpoints and tangent vectors at endpoints to endpoints and control points.
You don't say in what sense you want to "draw" this curve. If you want to write PostScript, here's what to do.
Say you want a curve $c:[0,1]toBbb R^2$ with $c(0)=(x,y)$, $c(1)=(xx,yy)$, $c'(0)=(dx,dy)$ and $c'(1)=(dxx,dyy)$. The following two lines of PostScript give you exactly that:
x y moveto
x+dx/3 y+dy/3 xx-dxx/3 y-dyy/3 xx yy curveto
Not that text literally - you want strings giving the numeric value of expressions. For exammple if $(x,y)=(0,0)$, $(xx,yy)=(1,1)$, $(dx,dy)=(1,1)$ and $(dxx,dyy)=(2,3)$ you'd say
0 0 moveto
0.3333 0.3333 0.3333 0 1 1 curveto
I actually did that to get a curve passing through those points.
Then I found this thing doesn't recognize eps as an image format.
Here's a screen shot.
(This was tedious enough - your points $A,B,dots$ are just marked
with X's.):
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
I edited my question and put a picture of a Bezier Curve simulation for you to understand. You will notice that the lines are "between" the dots and do not "touch" them ...
– Rogério Dec
Aug 4 at 0:04
When I said you should use Bezier curves I didn't mean that you'd get good results if you did it totally wrong.
– David C. Ullrich
Aug 4 at 0:23
add a comment |Â
up vote
1
down vote
I've actually done a lot of curve drawing "by hand" - all the curves in the figures in Complex Made Simple were drawn using PostScript's curveto function, which is Bezier curves. If you try polynomial interpolation I predict you won't like the results - the curve passing though $p_1,dots p_n$ has funny wiggles near $p_1$ due to the exact location of the other points.
I don't know what you're talking about when you say Bezier curves don't touch the points. A bezier curve is specified by four points; it passes through two of those points exactly, and the tangent vectors at those two endpoints are determined by the two "control points". The interface in terms of "control points" makes no sense to me - I wrote code to convert endpoints and tangent vectors at endpoints to endpoints and control points.
You don't say in what sense you want to "draw" this curve. If you want to write PostScript, here's what to do.
Say you want a curve $c:[0,1]toBbb R^2$ with $c(0)=(x,y)$, $c(1)=(xx,yy)$, $c'(0)=(dx,dy)$ and $c'(1)=(dxx,dyy)$. The following two lines of PostScript give you exactly that:
x y moveto
x+dx/3 y+dy/3 xx-dxx/3 y-dyy/3 xx yy curveto
Not that text literally - you want strings giving the numeric value of expressions. For exammple if $(x,y)=(0,0)$, $(xx,yy)=(1,1)$, $(dx,dy)=(1,1)$ and $(dxx,dyy)=(2,3)$ you'd say
0 0 moveto
0.3333 0.3333 0.3333 0 1 1 curveto
I actually did that to get a curve passing through those points.
Then I found this thing doesn't recognize eps as an image format.
Here's a screen shot.
(This was tedious enough - your points $A,B,dots$ are just marked
with X's.):
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
I edited my question and put a picture of a Bezier Curve simulation for you to understand. You will notice that the lines are "between" the dots and do not "touch" them ...
– Rogério Dec
Aug 4 at 0:04
When I said you should use Bezier curves I didn't mean that you'd get good results if you did it totally wrong.
– David C. Ullrich
Aug 4 at 0:23
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I've actually done a lot of curve drawing "by hand" - all the curves in the figures in Complex Made Simple were drawn using PostScript's curveto function, which is Bezier curves. If you try polynomial interpolation I predict you won't like the results - the curve passing though $p_1,dots p_n$ has funny wiggles near $p_1$ due to the exact location of the other points.
I don't know what you're talking about when you say Bezier curves don't touch the points. A bezier curve is specified by four points; it passes through two of those points exactly, and the tangent vectors at those two endpoints are determined by the two "control points". The interface in terms of "control points" makes no sense to me - I wrote code to convert endpoints and tangent vectors at endpoints to endpoints and control points.
You don't say in what sense you want to "draw" this curve. If you want to write PostScript, here's what to do.
Say you want a curve $c:[0,1]toBbb R^2$ with $c(0)=(x,y)$, $c(1)=(xx,yy)$, $c'(0)=(dx,dy)$ and $c'(1)=(dxx,dyy)$. The following two lines of PostScript give you exactly that:
x y moveto
x+dx/3 y+dy/3 xx-dxx/3 y-dyy/3 xx yy curveto
Not that text literally - you want strings giving the numeric value of expressions. For exammple if $(x,y)=(0,0)$, $(xx,yy)=(1,1)$, $(dx,dy)=(1,1)$ and $(dxx,dyy)=(2,3)$ you'd say
0 0 moveto
0.3333 0.3333 0.3333 0 1 1 curveto
I actually did that to get a curve passing through those points.
Then I found this thing doesn't recognize eps as an image format.
Here's a screen shot.
(This was tedious enough - your points $A,B,dots$ are just marked
with X's.):
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
I've actually done a lot of curve drawing "by hand" - all the curves in the figures in Complex Made Simple were drawn using PostScript's curveto function, which is Bezier curves. If you try polynomial interpolation I predict you won't like the results - the curve passing though $p_1,dots p_n$ has funny wiggles near $p_1$ due to the exact location of the other points.
I don't know what you're talking about when you say Bezier curves don't touch the points. A bezier curve is specified by four points; it passes through two of those points exactly, and the tangent vectors at those two endpoints are determined by the two "control points". The interface in terms of "control points" makes no sense to me - I wrote code to convert endpoints and tangent vectors at endpoints to endpoints and control points.
You don't say in what sense you want to "draw" this curve. If you want to write PostScript, here's what to do.
Say you want a curve $c:[0,1]toBbb R^2$ with $c(0)=(x,y)$, $c(1)=(xx,yy)$, $c'(0)=(dx,dy)$ and $c'(1)=(dxx,dyy)$. The following two lines of PostScript give you exactly that:
x y moveto
x+dx/3 y+dy/3 xx-dxx/3 y-dyy/3 xx yy curveto
Not that text literally - you want strings giving the numeric value of expressions. For exammple if $(x,y)=(0,0)$, $(xx,yy)=(1,1)$, $(dx,dy)=(1,1)$ and $(dxx,dyy)=(2,3)$ you'd say
0 0 moveto
0.3333 0.3333 0.3333 0 1 1 curveto
I actually did that to get a curve passing through those points.
Then I found this thing doesn't recognize eps as an image format.
Here's a screen shot.
(This was tedious enough - your points $A,B,dots$ are just marked
with X's.):
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
edited Aug 4 at 2:27
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
answered Aug 3 at 23:47
David C. Ullrich
53.8k33481
53.8k33481
I edited my question and put a picture of a Bezier Curve simulation for you to understand. You will notice that the lines are "between" the dots and do not "touch" them ...
– Rogério Dec
Aug 4 at 0:04
When I said you should use Bezier curves I didn't mean that you'd get good results if you did it totally wrong.
– David C. Ullrich
Aug 4 at 0:23
add a comment |Â
I edited my question and put a picture of a Bezier Curve simulation for you to understand. You will notice that the lines are "between" the dots and do not "touch" them ...
– Rogério Dec
Aug 4 at 0:04
When I said you should use Bezier curves I didn't mean that you'd get good results if you did it totally wrong.
– David C. Ullrich
Aug 4 at 0:23
I edited my question and put a picture of a Bezier Curve simulation for you to understand. You will notice that the lines are "between" the dots and do not "touch" them ...
– Rogério Dec
Aug 4 at 0:04
I edited my question and put a picture of a Bezier Curve simulation for you to understand. You will notice that the lines are "between" the dots and do not "touch" them ...
– Rogério Dec
Aug 4 at 0:04
When I said you should use Bezier curves I didn't mean that you'd get good results if you did it totally wrong.
– David C. Ullrich
Aug 4 at 0:23
When I said you should use Bezier curves I didn't mean that you'd get good results if you did it totally wrong.
– David C. Ullrich
Aug 4 at 0:23
add a comment |Â
up vote
0
down vote
Given an arbitrary set of $n$ points, it's possible to find the equation of a unique polynomial of degree at most $n-1$ that passes through all $n$ points.
Let's consider a very simple example; say we we wanted to find the parabola that passes through the points $(-4,2)$, $(-2,-1)$, and $(1,1)$.
The general equation of a parabola is $$y=ax^2+bx+c$$ so we can substitute the $x$- and $y$-coordinates of the three points we have to create a system of three equations with three unknowns, like so:
$$beginalign
2&=16a-4b+c \
-1&=4a-2b+c \
1&=a+b+c
endalign$$
Solving this system, we find that $a=frac1330$, $b=frac1110$, and $c=frac-815$. The parabola $y=frac1330x^2+frac1110x-frac815$ does indeed pass cleanly through all three points, so we're done.
And of course, you could do this with a system of six equations with six unknowns as well, but that would just take a little longer than this example.
Edit:
Mathematica reveals that the interpolating polynomial for those six points is approximately
$$y=1.51771x^5-10.5198x^4+23.6478x^3-17.2688x^2-0.696339x+2.81946$$
The graph of that function looks like this:
answered Aug 3 at 23:42
Robert Howard
1,241620
Have you actually done this, with more than three points? In my experience interpolating polynomials don't give the results one wants here - they have funny wiggles in funny directions.
– David C. Ullrich
Aug 3 at 23:50
I admit I've never used interpolation to find anything higher than a third-degree polynomial, but it's always worked well for me in those relatively simple cases. What do you mean by "funny wiggles?"
– Robert Howard
Aug 3 at 23:53
Take the points in his figure, find the interpolating polynomial and draw it - you'll see what I mean.
– David C. Ullrich
Aug 4 at 0:19
Come on! I went to some trouble to make an eps file showing what the Bezier looks like - show us what you get using polynomial interpolation..
– David C. Ullrich
Aug 4 at 1:23
I see how one could call the local extrema "funny wiggles," but it does connect the points in a smooth way, like the OP asked for. If, on the other hand, he was really after a closed curve all along, then I agree that polynomial interpolation is certainly not the way to go.
– Robert Howard
Aug 4 at 2:21
 |Â
show 2 more comments
up vote
0
down vote
Given an arbitrary set of $n$ points, it's possible to find the equation of a unique polynomial of degree at most $n-1$ that passes through all $n$ points.
Let's consider a very simple example; say we we wanted to find the parabola that passes through the points $(-4,2)$, $(-2,-1)$, and $(1,1)$.
The general equation of a parabola is $$y=ax^2+bx+c$$ so we can substitute the $x$- and $y$-coordinates of the three points we have to create a system of three equations with three unknowns, like so:
$$beginalign
2&=16a-4b+c \
-1&=4a-2b+c \
1&=a+b+c
endalign$$
Solving this system, we find that $a=frac1330$, $b=frac1110$, and $c=frac-815$. The parabola $y=frac1330x^2+frac1110x-frac815$ does indeed pass cleanly through all three points, so we're done.
And of course, you could do this with a system of six equations with six unknowns as well, but that would just take a little longer than this example.
Edit:
Mathematica reveals that the interpolating polynomial for those six points is approximately
$$y=1.51771x^5-10.5198x^4+23.6478x^3-17.2688x^2-0.696339x+2.81946$$
The graph of that function looks like this:
answered Aug 3 at 23:42
Robert Howard
1,241620
Have you actually done this, with more than three points? In my experience interpolating polynomials don't give the results one wants here - they have funny wiggles in funny directions.
– David C. Ullrich
Aug 3 at 23:50
I admit I've never used interpolation to find anything higher than a third-degree polynomial, but it's always worked well for me in those relatively simple cases. What do you mean by "funny wiggles?"
– Robert Howard
Aug 3 at 23:53
Take the points in his figure, find the interpolating polynomial and draw it - you'll see what I mean.
– David C. Ullrich
Aug 4 at 0:19
Come on! I went to some trouble to make an eps file showing what the Bezier looks like - show us what you get using polynomial interpolation..
– David C. Ullrich
Aug 4 at 1:23
I see how one could call the local extrema "funny wiggles," but it does connect the points in a smooth way, like the OP asked for. If, on the other hand, he was really after a closed curve all along, then I agree that polynomial interpolation is certainly not the way to go.
– Robert Howard
Aug 4 at 2:21
 |Â
show 2 more comments
up vote
0
down vote
up vote
0
down vote
Given an arbitrary set of $n$ points, it's possible to find the equation of a unique polynomial of degree at most $n-1$ that passes through all $n$ points.
Let's consider a very simple example; say we we wanted to find the parabola that passes through the points $(-4,2)$, $(-2,-1)$, and $(1,1)$.
The general equation of a parabola is $$y=ax^2+bx+c$$ so we can substitute the $x$- and $y$-coordinates of the three points we have to create a system of three equations with three unknowns, like so:
$$beginalign
2&=16a-4b+c \
-1&=4a-2b+c \
1&=a+b+c
endalign$$
Solving this system, we find that $a=frac1330$, $b=frac1110$, and $c=frac-815$. The parabola $y=frac1330x^2+frac1110x-frac815$ does indeed pass cleanly through all three points, so we're done.
And of course, you could do this with a system of six equations with six unknowns as well, but that would just take a little longer than this example.
Edit:
Mathematica reveals that the interpolating polynomial for those six points is approximately
$$y=1.51771x^5-10.5198x^4+23.6478x^3-17.2688x^2-0.696339x+2.81946$$
The graph of that function looks like this:
answered Aug 3 at 23:42
Robert Howard
1,241620
Given an arbitrary set of $n$ points, it's possible to find the equation of a unique polynomial of degree at most $n-1$ that passes through all $n$ points.
Let's consider a very simple example; say we we wanted to find the parabola that passes through the points $(-4,2)$, $(-2,-1)$, and $(1,1)$.
The general equation of a parabola is $$y=ax^2+bx+c$$ so we can substitute the $x$- and $y$-coordinates of the three points we have to create a system of three equations with three unknowns, like so:
$$beginalign
2&=16a-4b+c \
-1&=4a-2b+c \
1&=a+b+c
endalign$$
Solving this system, we find that $a=frac1330$, $b=frac1110$, and $c=frac-815$. The parabola $y=frac1330x^2+frac1110x-frac815$ does indeed pass cleanly through all three points, so we're done.
And of course, you could do this with a system of six equations with six unknowns as well, but that would just take a little longer than this example.
Edit:
Mathematica reveals that the interpolating polynomial for those six points is approximately
$$y=1.51771x^5-10.5198x^4+23.6478x^3-17.2688x^2-0.696339x+2.81946$$
The graph of that function looks like this:
answered Aug 3 at 23:42
Robert Howard
1,241620
edited Aug 4 at 2:20
answered Aug 3 at 23:42
Robert Howard
1,241620
answered Aug 3 at 23:42
Robert Howard
1,241620
answered Aug 3 at 23:42
Robert Howard
1,241620
1,241620
Have you actually done this, with more than three points? In my experience interpolating polynomials don't give the results one wants here - they have funny wiggles in funny directions.
– David C. Ullrich
Aug 3 at 23:50
I admit I've never used interpolation to find anything higher than a third-degree polynomial, but it's always worked well for me in those relatively simple cases. What do you mean by "funny wiggles?"
– Robert Howard
Aug 3 at 23:53
Take the points in his figure, find the interpolating polynomial and draw it - you'll see what I mean.
– David C. Ullrich
Aug 4 at 0:19
Come on! I went to some trouble to make an eps file showing what the Bezier looks like - show us what you get using polynomial interpolation..
– David C. Ullrich
Aug 4 at 1:23
I see how one could call the local extrema "funny wiggles," but it does connect the points in a smooth way, like the OP asked for. If, on the other hand, he was really after a closed curve all along, then I agree that polynomial interpolation is certainly not the way to go.
– Robert Howard
Aug 4 at 2:21
 |Â
show 2 more comments
Have you actually done this, with more than three points? In my experience interpolating polynomials don't give the results one wants here - they have funny wiggles in funny directions.
– David C. Ullrich
Aug 3 at 23:50
I admit I've never used interpolation to find anything higher than a third-degree polynomial, but it's always worked well for me in those relatively simple cases. What do you mean by "funny wiggles?"
– Robert Howard
Aug 3 at 23:53
Take the points in his figure, find the interpolating polynomial and draw it - you'll see what I mean.
– David C. Ullrich
Aug 4 at 0:19
Come on! I went to some trouble to make an eps file showing what the Bezier looks like - show us what you get using polynomial interpolation..
– David C. Ullrich
Aug 4 at 1:23
I see how one could call the local extrema "funny wiggles," but it does connect the points in a smooth way, like the OP asked for. If, on the other hand, he was really after a closed curve all along, then I agree that polynomial interpolation is certainly not the way to go.
– Robert Howard
Aug 4 at 2:21
Have you actually done this, with more than three points? In my experience interpolating polynomials don't give the results one wants here - they have funny wiggles in funny directions.
– David C. Ullrich
Aug 3 at 23:50
Have you actually done this, with more than three points? In my experience interpolating polynomials don't give the results one wants here - they have funny wiggles in funny directions.
– David C. Ullrich
Aug 3 at 23:50
I admit I've never used interpolation to find anything higher than a third-degree polynomial, but it's always worked well for me in those relatively simple cases. What do you mean by "funny wiggles?"
– Robert Howard
Aug 3 at 23:53
I admit I've never used interpolation to find anything higher than a third-degree polynomial, but it's always worked well for me in those relatively simple cases. What do you mean by "funny wiggles?"
– Robert Howard
Aug 3 at 23:53
Take the points in his figure, find the interpolating polynomial and draw it - you'll see what I mean.
– David C. Ullrich
Aug 4 at 0:19
Take the points in his figure, find the interpolating polynomial and draw it - you'll see what I mean.
– David C. Ullrich
Aug 4 at 0:19
Come on! I went to some trouble to make an eps file showing what the Bezier looks like - show us what you get using polynomial interpolation..
– David C. Ullrich
Aug 4 at 1:23
Come on! I went to some trouble to make an eps file showing what the Bezier looks like - show us what you get using polynomial interpolation..
– David C. Ullrich
Aug 4 at 1:23
I see how one could call the local extrema "funny wiggles," but it does connect the points in a smooth way, like the OP asked for. If, on the other hand, he was really after a closed curve all along, then I agree that polynomial interpolation is certainly not the way to go.
– Robert Howard
Aug 4 at 2:21
I see how one could call the local extrema "funny wiggles," but it does connect the points in a smooth way, like the OP asked for. If, on the other hand, he was really after a closed curve all along, then I agree that polynomial interpolation is certainly not the way to go.
– Robert Howard
Aug 4 at 2:21
 |Â
show 2 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2871559%2fformula-or-algorithm-to-draw-curved-lines-between-points%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Why have you decided Bezier curves (aka cubic splines) are not what you want? It's good enough for Postscript's CurveTo...
– David C. Ullrich
Aug 3 at 23:05
Is this close to what you're looking for? en.wikipedia.org/wiki/Polynomial_interpolation
– Robert Howard
Aug 3 at 23:19
@David C. Ullrich I'm not wanting to use Bezier Curves because I need the line to "touch" the point and the Bezier Curve will just stay between the points, on average, without reaching them completely.
– Rogério Dec
Aug 3 at 23:20
1
@Robert Howard, it seems to be quite so. Thank you!
– Rogério Dec
Aug 3 at 23:22
You're certainly welcome! I'm going to post an answer about it, too, just so this question doesn't sit in the "unanswered" queue for ages.
– Robert Howard
Aug 3 at 23:25