10
$\begingroup$

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?

$\endgroup$
13
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 21, 2010 at 16:26
  • 1
    $\begingroup$ (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. $\endgroup$ Oct 21, 2010 at 16:30
  • 2
    $\begingroup$ 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) $\endgroup$ Oct 21, 2010 at 16:48
  • 4
    $\begingroup$ 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. $\endgroup$ Oct 21, 2010 at 16:50
  • 2
    $\begingroup$ @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. $\endgroup$ Oct 21, 2010 at 21:50

4 Answers 4

12
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ wow, thanks for that! Never thought T2 was the key to my problem... $\endgroup$
    – mmr
    Oct 21, 2010 at 19:46
  • $\begingroup$ T2? $\mbox{}$ $\endgroup$ Oct 21, 2010 at 20:46
  • 3
    $\begingroup$ @Joseph, Apparently, "Terminator". :) $\endgroup$ Oct 21, 2010 at 21:17
  • 1
    $\begingroup$ @Joseph-- Sorry, didn't mean to be completely obscure. It's just that when I hear the term 'morphing', the first thing that comes to mind is the T1000, the enemy from Terminator 2 that was a CG-rendered character in many scenes that pioneered the use of morphing in movies. Basically, as soon as I read 'morphing' in your answer, it was a huge epiphany, that the movie and my problem could be related. $\endgroup$
    – mmr
    Oct 22, 2010 at 4:38
  • 2
    $\begingroup$ 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 $\endgroup$
    – bubba
    Jul 24, 2014 at 13:45
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – mmr
    Oct 21, 2010 at 19:26
3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – mmr
    Oct 21, 2010 at 22:01
  • $\begingroup$ 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. $\endgroup$ Oct 22, 2010 at 1:11
  • $\begingroup$ 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. $\endgroup$
    – mmr
    Oct 22, 2010 at 16:10
2
$\begingroup$

Excellent question! The answer was not known last year.

The following recent paper may have the answer you need:

"Average curve of n smooth planar curves" by Sati, Rossignac, Seidel, Wyvill, Musuvathy. Computer-Aided Design. Volume 70 Issue C, January 2016, Pages 46-55.

http://dl.acm.org/citation.cfm?id=2831700

It presents a fast, linear cost, construction that works very well when the curves are "compatible" (reasonably parallel). The paper also talks about how to use weighted averaging for blending and morphing between several curves.

The solution is independent of the order of the input curves and does not assume any given parameterization (like the timing that one of the comments mentions).

  • Jarek
$\endgroup$
1
  • $\begingroup$ It appears that the work which you mention only applies to averaging smooth Jordan curves. The OP has not imposed any constraints beyond closedness (and in particular the curves could self-intersect). Could you explain why the results of your paper actually apply in this case? $\endgroup$ Mar 16, 2016 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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