4
$\begingroup$

I'm trying to find a method that can take a collection of polylines, each described by a list of connected points on a plane, and find an "average" path through them. The input lines do not loop.

Essentially, I want to do something similar to that of taking multiple GPS routes which are individually subject to noise and producing a single smoothed average of them.

Are there any existing algorithms which can do this?

$\endgroup$
2
  • $\begingroup$ By polyline I presume you mean a piecewise linear curve? Or a more general marked curve? And you want a path through what, precisely? $\endgroup$
    – David Roberts
    May 9, 2012 at 8:46
  • $\begingroup$ Yes, a piecewise linear curve although not monotonically increasing on either axis. I'm aware that an "average" line is not well defined but I'm looking for a single path which is representative of the input lines. At present I have a scheme in place which finds the start and end points for the "average" line and then iteratively bisects the line and fits the mid point to the input lines. This works well for situations when the lines are straight or 'L' shaped but doesnt work for 'S' type shapes or nything more complex. $\endgroup$
    – Chris
    May 9, 2012 at 9:10

1 Answer 1

5
$\begingroup$

One of the most attractive distance measures between two curves is the Fréchet distance, which is the smallest leash length between a dog on one curve and its owner on the other. Algorithms for computing it have been studied since the mid-90's, perhaps starting with this paper:

H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. Intl. J. Computational Geometry and Applications, 5:75-91, 1995.

Two curves
[Image from Wouter Meulemans' web page.]

Once you have committed to this distance measure, it is natural to define a median curve as that which minimizes the maximum Fréchet distance between it and the curves in your collection. And indeed this has just been explored in a recent Ms. thesis:

Benjamin Raichel and Sariel Har-Peled. "The Fréchet Distance Revisited and Extended." 2012. (paper link).

The exact median curve of $k$ $n$-vertex polygonal chains can be computed in $O(n^k)$ time. But under a natural restriction that the curves are $c$-packed," the exponential time complexity is reduced to $O(n \log n)$ for a $(1+\epsilon)$-approximation. All of this is detailed in Raichel's thesis. I doubt there are existing implementations (because this is so new), but examining this literature should at the least provide you with one natural model of an "average" curve.

$\endgroup$

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.