# Interpolation Algorithms

Page 1 of 1

## 4 Replies - 4020 Views - Last Post: 11 May 2010 - 06:28 PM

### #1 Louisda16th

• dream.in.assembly.code

Reputation: 15
• Posts: 1,967
• Joined: 03-August 06

# Interpolation Algorithms

Posted 04 May 2010 - 11:31 PM

In my project, I need to use interpolation to find points near a given point and use these to calculate an approximate derivative. So if I have points y = {10, 13, 14, 11, 9} for x = 0 to 5 and I need to find the derivative at (x,y) = (2,14), I use interpolation find the values of y at x = 1.9 and 2.1. Then I find the difference of the two values and divide by 0.2.

The algorithm I used for interpolation is Newton's divided differences.

Now this works for most cases where the points seem to fit in a function y = polynomial of x.

However for curves such as this:

Newton's divided differences cannot be used since there are two values of y for the same value of x.

My question is, what algorithm would work in such cases?

I basically need to use this in feature point extraction of a face. These kind of curves occur at the lips and eyes.

Is This A Good Question/Topic? 0

## Replies To: Interpolation Algorithms

### #2 Gloin

• Expert Schmexpert...

Reputation: 235
• Posts: 4,489
• Joined: 04-August 08

## Re: Interpolation Algorithms

Posted 08 May 2010 - 06:44 AM

I'm assuming that currently you're interpolating using a function y=f(x) where x is discretized over time. What you should do instead to interpolate over two functions, x=f(t) and y=g(t) where t denotes the time.

### #3 Louisda16th

• dream.in.assembly.code

Reputation: 15
• Posts: 1,967
• Joined: 03-August 06

## Re: Interpolation Algorithms

Posted 08 May 2010 - 06:49 AM

Yes, I did do something like that. The face has points marked on it manually (called landmark points). And the coordinates of these points are stored. Each of these is assigned to a number which is basically the index of the landmark point. I made the coordinates x and y functions of these points. Although these indexes are integers, during interpolation, I calculated the coordinates of point number say 11.9 and 12.1 to calculate the derivate at point number 12. Will that work? I hope I made sense .

This post has been edited by Louisda16th: 08 May 2010 - 06:50 AM

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11039
• Posts: 41,325
• Joined: 27-December 08

## Re: Interpolation Algorithms

Posted 11 May 2010 - 05:44 PM

You can use the Mean Value Theorem to estimate at x = 12. It looks something like: f'© = (y2-y1)/(x2-x1).

Also, as much as I enjoy using parametric equations as Gloin suggested, why don't you evaluate your function inverting the axes. That is, use the y-axis as the x-axis and vice versa for evaluating the function (to compensate for a function not being able to have two equal y-coordinates). When you go to graph the function in your program, just place the x- and y-coordinates where they should normally go. So for example, given f(x) = x^2, evaluate f(x) using the y-coordinate as the param to get x (so you're evaluating the inverse of the inverse function). Then plug in (x,y) to draw.

### #5 Louisda16th

• dream.in.assembly.code

Reputation: 15
• Posts: 1,967
• Joined: 03-August 06

## Re: Interpolation Algorithms

Posted 11 May 2010 - 06:28 PM