Interpolation of Isolines

[medeek]

Computational Geometry Problem:

You have two isolines defined by a finite number of coordinate points (x,y) spaced at fairly regular intervals. You then place a random point between these two isolines, at some known coordinate (x1,y1). What is the most accurate method of linear interpolation to determine the value of the point between the isolines?

The inaccuracy in determining the value is due to the approximate nature of the discrete points defining the isolines. However, there are ways to deal with this. I have a devised a fairly simple algorithm for doing this however I would be interested to see what others might come up with and whether it might provide a more accurate and less computationally expensive method than my own.

 

[GregLocock]

"What is the most accurate method of /linear interpolation/ to determine the value of the point between the isolines? "

I spotted your problem. linear interpolation between two arbitrary isolines is equivalent to tesselating the response surface with planar triangles. However computationally efficient it might be, it is not going to be satisfactory for many people.

Anyway in pseudo code


find two points on isolineA that are the closest to x1y1, nearestA and 2ndA
find two points on isolineB that are the closest to x1y1, nearestB and 2ndB
if(does x1y1 lie on a direct line between nearestA and nearestB?)==1

easy maths​

else

decide how to chuck one of those points away
solve the trivial remaining problem.​

Cheers

Greg Locock


New here? Try reading these, they might help FAQ731-376

http://eng-tips.com/market.cfm?

 

[jhardy1]

There's no single "correct" answer to your question.

One obvious technique would be linear interpolation, by "tessellating" the data points with triangles (as GregLocock suggests), but there is more than one way to tessellate any given set of data points, and they can yield different linear interpolations. As a trivial example, consider the following 4 data points:

A: (0,0,0)
B: (1,0,1)
C: (1,1,0)
D: (0,1,1)

It is desired to know the z coordinate at the centroid of these 4 sample points - i.e. at (x,y) = (0.5,0.5).
What do YOU think the "correct" z coordinate should be? (Have a go and work it out on paper before reading forward.)

a) Suppose we tessellate as two triangles ABD and BCD. This yields a "ridge" running from top-left to bottom-right, and the interpolated z coordinate is 1.0.
b) Suppose we instead tessellate as two triangles ABC and ACD. This yields a "valley" running from bottom-left to top-right, and the interpolated z coordinate is 0.0.
c) Taking a simple weighted mean of all 4 adjacent data points would yield a z coordinate of 0.5.

Which is "correct"?

Cubic B-splines will tend to interpolate a uniformly-dense data set smoothly and predictably, but the programming is rather more complex than simple linear interpolation - only you can decide whether the additional "burden" is justifiable for your needs. (Mathcad can do this on a uniform grid of sample data points using the "cspline" function, for example.)

http://julianh72.blogspot.com

 

[medeek]

My solution:

Sorry the image is not very clear.

 

[Denial]

Two comments.
(1)[ ] Your diagram shows h1 and h2 being (very close to) parallel to each other.[ ] Your method does not actually assume that they are parallel, but it probably becomes increasingly problematic as they move further away from being parallel.[ ] Draw yourself an extreme case, verging on the degenerate, and see how you like it.
(2)[ ] Your final formula needs h1 and h2 reversed in its numerator.

 

[medeek]

The diagram coincidentally ended up showing h1 and h2 parallel however you are correct they will probably not be parallel.

I've switched h1 and h2.

If the spacing of the isoline points is considerably less than the spacing of the isolines and the radii of curvature of any isoline feature then my algorithm should not encounter the degenerate case, would you agree?

 

[Denial]

My immediate reaction is that with point-spacing that satisfies those two requirements you should avoid any serious degeneracies.[ ] However this might merely be a failure of imagination on my part.

 

[jhardy1]

"If the spacing of the isoline points is considerably less than the spacing of the isolines and the radii of curvature of any isoline feature then my algorithm should not encounter the degenerate case, would you agree?"

That's probably a fair generalisation, provided the assumptions are valid, but be warned:

If you are 100% certain that your data is always going to be "well-conditioned", then a relatively simple algorithms may be very reliable. However, if there is any chance that the data sets that you will apply your algorithm may sometimes be "poorly conditioned" so as to invalidate your assumptions, it might be safer to apply a more "robust" general algorithm that can generate "sensible" solutions even on very coarse, arbitrarily-spaced data points.

E.g. consider the ground elevation contours on a topographical map that represent a narrow, steep-sided "spur" (or a deep gully) - these "isolines" will be closely-spaced, and will have very tight radii at the tip of the spur / top of the gully. Are features such as this possible in your data? How would your algorithm perform in such areas?

http://julianh72.blogspot.com