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?
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.
[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.
Suppose you construct an x-axis-array and a y-axis-array each having around 1000 entries. Each point on each line will have two axis indexes (1000 * (x - x_min)) // (x_max - x_min), one for x and one for y. The x-axis-array and y-axis-array values at each index consist of an array of [line#, point#]. A reference to each point itself and its nearest neighbors will consist of the set intersection of that point's x-axis-array and y-axis-array values. In other words, the set of [line#, point#]'s common to both values. To capture less near neighbors, simply include x-index +/- 1 and y-index +/- 1, 2, 3, etc. Each initial line should be "densified" by computing points along each line segment to the required precision. In practice, this reduces the burden of finding the "shortest leash" by at least three or four orders of magnitude. Further (small) gains can be achieved by initial rough distances calculated as manhattan distance. The shortest pythagorean distance is guaranteed to be no more than 1.5 times the shortest manhattan distance if each were computed separately for each pair of points.
