How can I find the average of two 2D curves?

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.


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.


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.