How to interpolate polyline or line from points?

Question

We have a lot of points, but with no timestamps to create ways. For now, I've created a sample of the way the points traverse. It's in here, this way can be compared with a Google one.

I haven't found a proper function in PostGIS or a tool in Python to do so. Does anyone have any hints for how I can accomplish this? Remember the points have no timestamps or another way to be ordered, and we do not have a way to follow, just the points and from those we want to generate the polyline.

We have about 500,000 points in the country to work with, and we want to trace some new ways where there are not still in OSM.

The first task we want to address is to interpolate the ways.

Preferably we would work with PostGIS or libs in python. The hard thing is to "isolate" in some way the points that could conform a way.

Answer 1

A good general-purpose solution could begin with a Euclidean minimum spanning tree. This is fast and easy to compute, using a greedy algorithm to link closest vertices together. There should be no problem processing many millions of vertices all at once. You can then isolate specific routes by eliminating the longest edges in the tree or by "exploding" the tree at its higher-order vertices.

As an example, consider this extract from your map:

The red points were manually digitized to recreate this portion of the data; I purposely digitized them out of order. The green lines are the result of the EMST calculation. You can see they do a good job of linking the points as our eye would, even to the point of isolating the outlying point near the "Cienaga de Oro" label. Such outliers can be found in post-processing the tree by exploding it into its branches and eliminating very short branches.

References

This implementation is based on code published in

Derrick Wood, "Data Structures, Algorithms, & Performance" (Addison-Wesley, 1993), Section 13.4.4.

See also

Preparata & Shamos, "Computational Geometry" (Springer-Verlag, 1985), Section 6.1.