Interpolate or find a point in a point array fast?

Question

0.00/5 (No votes)

See more:

Hi,

I'm still new to vb.net and have come up against another problem that should be easy to solve but after much time I still can't workout how to do it right.

I have a large 1d array of points which have unique Y's and varying X's and I want to linearly interpolate an X when provided with a Y.

I have got it working by finding the nearest point via an iterating counter through the array. Unfortunately it is too slow. I did see that .NET has the array.find with predicate but I couldn't see a sensible way of passing the known Y to the predicate?

Any suggestions gratefully received !

Thanks.

Posted 24-Mar-12 9:12am

codetowns

Add a Solution

Comments

Sergey Alexandrovich Kryukov 24-Mar-12 18:35pm

You did not property describe your data. Is it sorted by X or not? (Or by Y.) Are X points placed uniformly (this is not redundant question, it's often the case in many cases of data acquisition)? What's the problem with predicate? What array function did you try?
--SA

codetowns 25-Mar-12 6:34am

Apologies and thanks for the reply.

It is sorted low to high in Y but is not uniform. X has a range of around + 50 to - 50. So it is something like:

15,1
25,3
-15,5
-17,6
5,9
10,21
etc.

I tried the array.find but it appeared to me that the predicate function only took a point (and not the required Y without a public variable), and also would fail on a missing Y. It sounds stupid I know but I guess this is my problem of being self taught! Perhaps there is a suitable array method?

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

MarqW · Accepted Answer · 2012-03-25T23:19:00

Solution 1

If you use a List(Of Point) instead of an array, you can use

VB

Points.Where(Function(p) p.Y = 34).First.X

Alternatively, if your Y is not excepted to be in the array, look up how to calculate the equation of a line ( y = mx + c ) and use this against a couple of points from your array, then you can use this to calculate an X for any value of Y

Posted 25-Mar-12 23:19pm

MarqW

Updated 25-Mar-12 23:22pm

v2

Comments

codetowns 26-Mar-12 8:40am

I was unaware of that 'points.where' function - interesting. As the straight line method was needed anyway (as you said y = mx + c)I decided to do the binary search method in the end. Thanks for the reply!

CPallini · Accepted Answer · 2012-03-25T23:30:00

Solution 2

Since your array is sorted you may implement a binary search[^].

Posted 25-Mar-12 23:30pm

CPallini

Comments

codetowns 26-Mar-12 8:42am

Yes, many thanks for that link!

I've now got it searching in halves until it finds a point. Failing that it knows the two nearest ones for interpolation.

CPallini 26-Mar-12 8:48am

You are welcome.
:-)