Tangent of the curve [to be generated by a set of points]

[Kevin]

I have a set of points in 2D space. I want to find the tangent in every point(Especially the first and last points) in the curve generated by the points. I do not have the equation to the curve.

My thoughts:
I was thinking of doing the interpolation[Cubic Interpolation] on the points to get the curve equation. And later finding the derivative of the curve at the required point to get the tangent. But this method fails because the existing interpolation methods don't need to find the equation of the curve. They have an approximate method which generates the next set of points without the equation. I don't know how to find the derivative by that particular method mainly because I don't understand it.

Please post your thoughts on this, any other method you'd follow, or any links I can follow and help me out. Thanks. :)

[Hans-Bernhard Bröker]

On 06.10.2012 08:29, Kevin wrote:
> I have a set of points in 2D space. I want to find the tangent in
> every point(Especially the first and last points) in the curve
> generated by the points.

That's impossible, because there is no such thing as "the" curve under
that definition. There are infinitely many such curves. You have to
narrow down the selection of curves to a single one before you can being
computing any tangents.

For a start, a set is unordered by definition. I.e. it's not defined
which order your curve would visit those points in. Actually, you
haven't even specified if the curve is supposed to go through all those
points, or just be influenced by their positions somewhat loosely.

[Nobody]

On Fri, 05 Oct 2012 23:29:56 -0700, Kevin wrote:

> I have a set of points in 2D space. I want to find the tangent in every
> point(Especially the first and last points) in the curve generated by the
> points. I do not have the equation to the curve.
>
> My thoughts:
> I was thinking of doing the interpolation[Cubic Interpolation] on the
> points to get the curve equation. And later finding the derivative of the
> curve at the required point to get the tangent. But this method fails
> because the existing interpolation methods don't need to find the equation
> of the curve. They have an approximate method which generates the next set
> of points without the equation. I don't know how to find the derivative by
> that particular method mainly because I don't understand it.

The interpolation algorithm determines the coefficients from the position
and tangent at each end of the segment, and the tangents are typically
chosen as half the difference between the point after the current point
and the point before it, i.e. the tangent at p[n] is (p[n+1]-p[n-1])/2.

[This ensures that a sequence of points in a straight line interpolate to
a straight line; if the points are evenly spaced, the interpolation will
be linear.]

If you only need the tangent at the initial set of points, you don't
actually need to find the equation for the curve.

If you need the tangent at an arbitary point within a curve segment, the
coefficients for each segment are determined as follows.

Given:

p(x) = c3.x^3 + c2.x^2 + c1.x + c0

the derivative is:

p'(x) = 3.c3.x^2 + 2.c2.x + c1

So:

p(0) = c0
p(1) = c3 + c2 + c1 + c0
p'(0) = c1
p'(1) = 3.c3 + 2.c2 + c1
=>
c0 = p(0)
c1 = p'(0)
c2 = 3.p(1) - 3.p(0) - p'(1) - 2.p'(0)
c3 = p'(1) + p'(0) - 2.p(1) + 2.p(0)

Using:
p(0) = p[n]
p(1) = p[n+1]
p'(0) = (p[n+1]-p[n-1])/2
p'(1) = (p[n+2]-p[n])/2
=>
c0 = p[n]
c1 = (p[n+1] - p[n-1])/2
c2 = -(p[n+2] - p[n])/2 + 2.p[n+1] - 3.p[n] + p[n-1]
c3 = (p[n+2] - p[n])/2 + (p[n+1] - p[n-1])/2 - 2.p[n+1] + 2.p[n]

[Sonic 414]

@ Hans-Bernhard Bröker

Thanks for Replying :)

The curve is supposed to go through all the points. If you plot the points in a graph paper, the first point or starting point in the curve is the one which is the point which is the leftmost point in the bottom half [With the Origin in the midpoint of the graph paper ). The last point will be the rightmost point in the bottom half . Considering I have a ordered set/list (I'm using the term set loosely on the basis that it's a collection, if you'd like i can change the term to 'ordered list') of points in this configuration , with the curve starting at the start point (the first point in the set) , passing through all the other points in the set, and ending at the end point(last point in the set) , how do you propose a solution ? :)


@Nobody [Hope there is somebody there ^_^' ]
Thanks for the equations. I believe what you proposed is the definition and derivation of Cubic Hermite Spline [ I may be wrong, _my_ whole knowledge about splines/curves comes from some pages in the internet ^_^' ].
There are a couple of reasons I didn't want to use this approach.
The main reason being that the tangents are predetermined. As you said :
<quote>

and the tangents are typically chosen as half the difference between the
point after the current point and the point before it, i.e. the tangent at
p[n] is (p[n+1]-p[n-1])/2.

</quote>
If the tangents are calculated in this method,
i) How do you propose to calculate the tangent at P[0] , where there is no P[-1] ? .
ii) If the tangent is calculated in this method, there is no reason to calculate the curve. The reason I wanted a curve was to have consider the global information ( the shape of the curve ) in the calculation of the curve. I believe that the shape of curve should affect the tangent at any point even if it is minute.
So Is there any other method? ^_^'

[Hans-Bernhard Bröker]

On 15.10.2012 08:32, Sonic 414 wrote:
> The curve is supposed to go through all the points. If you plot the
> points in a graph paper, the first point or starting point in the
> curve is the one which is the point which is the leftmost point in
> the bottom half [With the Origin in the midpoint of the graph paper
> ). The last point will be the rightmost point in the bottom half .

That settles 2 points --- what about all the others?

> Considering I have a ordered set/list (I'm using the term set loosely
> on the basis that it's a collection, if you'd like i can change the
> term to 'ordered list')

What I would like doesn't matter. It's _your_ task, so _you_ have to
know which way those points are supposed to be ordered. If they're in an
unordered container, you need to sort it according to some criterion
before going on.

> how do you propose a solution ?

Pick a type of spline, apply it, and evaluate your tangents from that.

[Noskosteve]

On Saturday, October 6, 2012 1:29:56 AM UTC-5, Sonic 414 wrote:
> I have a set of points in 2D space. I want to find the tangent in every point(Especially the first and last points) ... Thanks. :)

Somic414,
Reading the other posts I think you have some of your answer. I may be able to add something of value. However, tangents at the points are, indeed, not absolute. That is, there is no one answer, just like there is also no one curve.

First, for any method you choose, *you* will be on your own to determine the tangents at the ends. That is, you can make them anything you want. This is because virtually all these methods use the adjacent points to determine the tangents at a given point. Therefore, to get the curve to intercept the ends data points additional points must be added to the data. Some methods add these points in the background - that is unbeknownst to the user (my appendix examples for these curves do this). It sounds to me that you'll have to draw the curve, then play with the end tangents to get what you like.

Methods that "will do what you ask" are the Catmul-Rom (fixed 'curviness') and Kochanek-Bartels (K-B) (user variable 'curviness'). These methods will provide you with the tangents at each point - if you know how to extract them and my book should give you what you need to do it. The Catmul-Rom sets its own tangents based on the two adjacent points. The K-B does the same, but you have the ability to adjust them – either all in the same manner, or individually – in other words, you can make the tangent anything you want at each point.
For these you must simply add one additional point (of your choosing) at each end to help you (graphically) set the end tangent. These will be the (-1) point and the (N+1) point and they *may* be equal to the original end points.
I see that I used the term 'slope' instead of 'tangent' in the appendix.

The *CUBIC* piecewise LaGrange method I developed is similar, but I believe the others are better.

There are 2-D curves in my Appendix showing the behavior of almost every type I included.

Background and downloads are here:
http://home.comcast.net/~k9dci/site/?/page/Piecewise_Polynomial_Interpolation/

Direct download links:
Text
http://k9dci.home.comcast.net/~k9dci/Book/Manuscript_Ver_9b.pdf 1.9M

Appendix Catmul-Rom pg 153; K-B pg
http://k9dci.home.comcast.net/~k9dci/Book/Appendix_Ver_8b.pdf 1.7M

Happy fishing...
--
73, Steve, K9DCI USN (Vet) MOT (Ret) Ham (Yet)

Give a man a fish and you feed him for a day. TEACH a man to fish and you just increased your bait shop market.

[Noskosteve]

On Friday, October 26, 2012 8:07:52 PM UTC-5, Noskosteve wrote to Sonic 414:

Appendix Catmul-Rom pg 153; K-B pg 169
http://k9dci.home.comcast.net/~k9dci/Book/Appendix_Ver_8b.pdf 1.7M

OOPS !! K-B on Appendix Pg 169

[Sonic 414]

Wow. Thanks Steve. It seems to be a great book. It would have been wonderful if I saw it earlier -_-'' .. I kind of stumbled my way around it and made myself a C# program to learn about splines. If you have a Basis Matrix for the particular spline model, you'd be able to watch what happens with different t values and points. If you want it, have little C# knowledge and have VS 2010 , I can share it with you . ^_^ ..

Thanks again for the book :)

and thanks to everyone who replied. \(^_^)/

Kevin

[Noskosteve]

Steve Writes:
Yikes!
Good thing I stumbled across this. I infrequently read c.g.a any more. I came to do another book plug. I see postings are much less these days.(I yahoo Groups a lot, but not on Graphics) Best to contact me via my site Contact Page:
http://k9dci.home.comcast.net/

I'm glad you got something out of the book. I hear little about anyone seeing it. A publisher rep said he might like to get it onto print, but that never came to be...yet.

A - I don't 'do' C. It's weird. I'm now doing a lot of VBA behind Excel.

B - Haven't a clue what a VS 2010 is. Read my posts a short time ago about the Bezier circle approx and the Weiestrauss thing for how I did the book's graphics and how I got the book to my site.

C - I'm an RF Development Engineer turned Manager (retired) and do computer stuff on the side/hobby and got into "splines" due to my laser graphics hobby. It's all xplained on my site and in the book.

D - Like your C program, I wrote a "Laser Image Editor" on a Mac in the 80's which did all the curves in the book using uSoft Quick Basic 1.0. It never did any images that I ported to the show system, only curve studies and the figures for the book. Put in the Basis and play!

Cheers, Steve N.

[Nobody]

On Sat, 03 Nov 2012 20:44:31 -0700, Noskosteve wrote:

> B - Haven't a clue what a VS 2010 is.

VS = Visual Studio, Microsoft's integrated development environment.
VS 2010 = the 2010 version.