Algorithm for 2D Interpolation

I have 开发者_开发问答two shapes which are cross sections of a channel. I want to calculate the cross section of an intermediate point between the two defined points. What's the simplest (relatively simple?) algorithm to use in this situation?

P.S.: I came across several algorithms like natural neighbor and poisson, which seemed complex. I'm looking for a simple solution, which could be implemented quickly.

EDIT: I removed the word "Simplest" from the title since it might be misleading

---

This is simple:

1. On each cross section draw N points at evenly spaced intervals along the boundary of the cross-section.
2. Draw straight lines from the n-th point on cross-section 1 to the n-th point on cross-section 2.
3. Take off your new cross-section at the desired distance between the old cross-sections.

Simpler still:

1. Use one of the existing cross-sections without modification.

This second suggestion might be too simple I suppose, but I bet no-one suggests a simpler one !

EDIT following OP's comment: (too much for a re-comment)

Well, you did ask for a simple method ! I'm not sure I see the same problem with the first method as you do. If the cross sections are not too weird (probably best if they are convex polygons) and you don't do anything strange such as map the left side of one cross-section to the right side of the other (thereby forcing lots of crossing lines) then the method should produce some kind of sensible cross section. In the case you suggest of a triangle and a rectangle, suppose the triangle is sitting on its base, one vertex at the top. Map that point to, say, the top left corner of the rectangle, then proceed in the same direction (clockwise or anti-clockwise) around the boundaries of both cross-sections joining corresponding points. I don't see any crossing lines, and I see a well-defined shape at any distance between the two cross-sections.

---

Note there are some ambiguities about High Performance Mark's answers you will probably need to address and will define the quality of the output of his method. The most important one is, when you draw the n points on both cross-sections, what sort of correspondence do you determine between them, that is if you do it that way High Performance Mark suggested, then the order of labeling the points becomes important.

I suggest rotating (orthogonal) plane simultaneously through both cross sections, then the set of points which intersect that plane on one cross section just need to be matched to the set of points that intersect that plane on the other cross section. Hypothetically, there is no limit on the number of points in these sets, but it certainly reduces the complexity of the correspondence problem in the original situation.

---

Here is another try at the problem, which I think is a much better attempt.

Given the two cross-sections C_1, C_2

Place each C_i into a global reference frame with coordinate system (x,y) so that the way they are relatively situated makes sense. Split each C_i into an upper and lower curve U_i and L_i. The idea is going to be that you will want to continuously deform curve U_1 to U_2 and L_1 to L_2. (Note you can extend this method to split each C_i into m curves if you wish.)

The way to do this is as follows. For each T_i = U_i, or L_i sample n points, and determine the interpolating polynomial P{T_i}(x). As some one duly noted below, interpolating polynomials are susceptible to oscillation especially at the endpoints. Instead of the interpolating polynomial, one may instead use the least squares fit polynomial which would be much more robust. Then define the deformation of the polynomial P{U_1}(x) = a_0 + a_1 * x + ... + a_n * x^n to P{U_2}(x) = b_0 + b_1 * x + ... + b_n * x^n as Q{P{U_1},P{U_2}}(x, t) = ( t * a_0 + (1 - t ) b_0 ) + ... + (t * a_n + (1-t) * b_n ) * x^n where the deformation Q is defined over 0<=t<=1 where t defines at which point the deformation is at (i.e. at t=0 we are at U_2 and at t=1 we are at U_1 and at every other t we are at some continuous deformation of the two.) The exact same follows for Q{P{L_1},P{L_2}}(x, t). These two deformations construct you a continuous representation between the two cross-sections which you can sample at any t.

Note all this is really doing is linearly interpolation the coefficients of the interpolation polynomials of the two pieces of both cross-sections. Note also when spliting the cross-sections you should probably put the constraint that they must be split at end points that match up otherwise you may have "holes" in your deformation.

I hope thats clear.

edit: addressed the issue of oscillation in interpolating polynomials.