Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a curve interpolation problem.

I have two closed curves that are defined on an X,Y plane. How can I define a 3rd curve that is the average of those two? Programmatically, I have a list of points for each curve, let's say N1 for curve 1 and N2 for curve 2, where N1 != N2 (most likely).

When I say 'average', initially, I would like the contribution of each curve to the final curve to be identical. Eventually, I would like to be able to weight the contributions of each curve (i.e., have my interpolated curve be 'closer' to one curve than another).

How can I go about doing this?

In a 1D case, I believe that the problem is somewhat easier, like I could solve it using some kind of projection (although my linear algebra is really rusty at this point). Is that intuition somewhat correct, and therefore can be extended to the 2D case?

share|improve this question
    
Well, if the two curves have the implicit Cartesian equations $F(x,y)=0$ and $G(x,y)=0$, would $uF(x,y)+(1-u)G(x,y)=0$, $u$ an adjustable parameter, fit the bill? –  J. M. Oct 21 '10 at 16:26
1  
(a) I don't think this question is suitable for the scope of this website. You should consider asking at artofproblemsolving.com or math.stackexchange.com or at StackOverflow. (b) There are many ways of taking the average. Presumeably something is not satisfactory about averaging at fixed time? (given your list of points you can make a piecewise linear curve fitting the points with constant speed. Then just interpolate by averaging the values at each fixed time $t$) When you re-post the question to those other forums, please clarify your criterion for a good average. –  Willie Wong Oct 21 '10 at 16:30
2  
Okay, two comments: (1) IF you have a series of points with lines connecting them, you can insert a time function. For $t \in (0,1)$, let $\gamma_1(t) = (N_1t - [N_1t])P_{[N_1t] + 1} + ([N_1t] + 1 - N_1 t) P_{[N_1t]}$ where $[N_1t]$ is the integer part of $N_1t$, and $P_n$ is the $n$th point given out of the list of $N_1$. This way you get a parametrization of your curve using the time $t$. Then you can just take the average. (2) If this is not satisfactory, why not? There are many ways of taking averages between two curves. (cont'd) –  Willie Wong Oct 21 '10 at 16:48
3  
Suppose the two curves are in fact both the standard circle. If you parametrize them the same way their average is the standard circle. If you parametrize them so that the angle parameter is off by $\pi$ radians, the average "curve" is just the 0 point. So you need to specify whether you want a parmetric average of some sort of geodesic average or something like that. Which is why I asked you to specify what notion of "good average" you are using, and which you haven't answered. –  Willie Wong Oct 21 '10 at 16:50
1  
@mmr, You do not have a rigorous question yet. You can't get an answer unless you have a well defined question. There's no point to complaining that you don't have a "real 'answer'" when you do not have a real question that is well posed. Please define what you mean by the mapping from even a single set of points to a curve. In fact, I think you're wrong in using set: you need to provide an ordered list of points for $N_1$ and $N_2$. Unless, of course, you mean the best fit line $y=mx+b$ for the full set of points in each group. Please clarify, mmr. –  sleepless in beantown Oct 21 '10 at 21:50
show 8 more comments

3 Answers 3

up vote 9 down vote accepted

I think the keyword you need to find literature on your problem is morphing. There is an extensive computer graphics literature on this. Below is a figure from one paper selected almost at random: "Morphing Using Curves and Shape Interpolation Techniques" Johan, H.; Koiso, Y.; Nishita, T. in Computer Graphics and Applications, pp. 348 - 454, 2000. The 4th figure in the sequence could serve as the average you seek.
alt text
Another reference is "Multiresolution Morphing for Planar Curves," Hahmann, S. and Bonneau, G.-P. and Caramiaux, B. and Cornillac, M., Computing 79 (2007) 197-209. Using the key search terms, and Google Scholar with these two references, should bring you to a wealth of relevant literature.

See also this related MO question on the distance between two curves.

share|improve this answer
1  
wow, thanks for that! Never thought T2 was the key to my problem... –  mmr Oct 21 '10 at 19:46
    
T2? $\mbox{}$ –  Joseph O'Rourke Oct 21 '10 at 20:46
2  
@Joseph, Apparently, "Terminator". :) –  J. M. Oct 21 '10 at 21:17
    
@J.M.: In the context of Michael's mention of geodesics, I thought the 'T' must refer to 'Teichmüller'! :-) This only reveals the depth of my cluelessness, but having it explained as 'Terminator' does not enlighten me. Perhaps it is best let this issue pass... –  Joseph O'Rourke Oct 21 '10 at 22:48
1  
In the animation world, this is also known as "tweening" (because we're constructing "in-betweens") or key-framing. en.wikipedia.org/wiki/Key_frame –  bubba 6 hours ago
show 3 more comments

One way to define an average could start as follows: you first introduce a metric on the space of all curves, i.e. a way of telling the distance between two curves (there should be a natural way to do this for curves in the Euclidean plane). Then you try to find a shortest path in this space connecting the two curves (a geodesic), and call the curve lying half ways the average. Since you are actually considering polygons with a fixed number of vertices, the "space of all curves" is finite dimensional so things might be more computable. I assume this leads to some interesting mathematics but I don't what has been done in this area. Maybe you can find some more information in this article of Younes, Michor, Shah and Mumford.

share|improve this answer
    
apparently, I can't even vote up without 15 rep. In any event, thanks-- now I know what a geodesic is, and can look at some work there. –  mmr Oct 21 '10 at 19:26
add comment

Please clarify your question: rigorously define what you mean by curve and line.

@mmr, thus far, in the way you've defined your question, you do not have two 2-dimensional curves, you don't even have a curve or line defined for each individual set. What you do have are two sets of points in 2-d space, $N_1$, and $N_2$. You also have not stated that the number of points in each set is the same or different, thus the cardinality of both sets is not necessarily the same.

Now how are you defining the "curves" or line-segments for each set of points? If you do not have a definition which maps from the set of points $N_1$ to either a line or line-segment in $\mathbb{R^2}$ or a curve in $\mathbb{R^2}$, then there is no point in trying to define a new function which defines the average or a new function which parametrizes the weighted average of a line which interpolates the two so-called "lines" defined by $N_1$ and $N_2$.

Your function mapping from the point set to the "curve" you desire needs to defined, first of all, for a single set of points.

  • You could define it as the best fit line of the form $y=mx+b$ with fit defined as the least-squares fit.

  • You could define it as the piece-wise linear union of the line segments joining the points in the set; but in that case, you need to provide an ordering or sequence to the points in each set, so that there is no ambiguity about the direction and order of the line-segments. In this case, there is no requirement that the two sets be of the same ordinality: you could define a parametric point along each piece-wise-linear line segment with $0$ corresponding to the starting point in $N_1$ and $N_2$ and $1$ corresponding to the ending point in $N_1$ and $N_2$ and with $0 \le f \le 1$ defining the point partially along the euclidean length of the two line segments (or any other length which you would like to devise), and $0 \le p \le 1$ defining the weighting between lines $N_1$ and $N_2$ with $p=0$ denoting the line $N_1$ and $p=1$ denoting the line $N_2$. Then $p=0.5$ with $f$ varying from $0$ to $1$ would define the average of the two piece-wise-linear lines $N_1$ and $N_2$.

  • if the sets have the same cardinality, you could define a parametric curve in $t$ for each of the two lines, whether you define it as a bezier curve, a cubic spline, some other form of spline, where you end up with the functions for each line wher $t$ varies from $0$ to $1$:

($x_1, y_1) = ( f_1(t), g_1(t)$) and

($x_2, y_2) = ( f_2(t), g_2(t)$),

allowing you to create the weighted average line $$(x_a, y_a) = (p f_1(t)+(1-p)f_2(t), p g_1(t) + (1-p) g_2(t) ), $$ where $p=0$ gives all of the weight to line 1 defined by $N_1$ and $p=1$ gives all the weigth to line 2 defined by $N_2$

Even if the two sets have the same number of points in them, the order in which the points are specified, and the order in which they are mapped to each other, will modify the "average" line between them and thus change the definition of the "interpolated" weighted average between them.

If you do not bother to specify rigorously the domain and range of your question, I don't think that you can really complain that

...I have three answers, but no real 'answers' to the question...

as you do in the comments to your own question.

If you decide to define your question rigorously, perhaps I (and others) could provide a rigorous answer.

share|improve this answer
1  
I apologize for the lack of rigor; until I had read your explanation, I didn't quite realize the extent of the possibilities. Even so, I've hit many of the problems you've described; namely, I realize I need to order the sets (ie, figure out the order of points, and if necessary, reorder one set to match another), find a good 'start point', and since I know that the cardinality doesn't match, define some a distance-based time parameterization, as per @Willie's comments. –  mmr Oct 21 '10 at 22:01
    
mmr will probably have to worry about the best parametrization of the two point-sets also. If he chooses the wrong parametrization, his curve may well end up with kinks (sections of high curvature) or cusps where there shouldn't be. –  J. M. Oct 22 '10 at 1:11
    
OK, now I need to look up the various kinds of parametrization. It seems like this is actually a hard problem, then, not just something that can get fired off easily. –  mmr Oct 22 '10 at 16:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.