This problem is quite complex... or it's a compilation of several problems... I can see at least two
- Which of points is first and which is last
- What is correct order of points
As a resolution of first I think we have to find 2 nearest points for every point and then look for a point which in nearest points of nearest points doesn't have this point (I know it sounds complicated)
Second problem - when we'll find start we have to point after point search for nearest till we reach the end...
Of course since we have no order given every resolution will be only guessing and this will not work for every set of points but if we get from the first to the last point, and there will be no points not included in the line, we can assume that our solution is correct.
As other resolutions could be some brute-force method - join points in every order and return first non-self-intersected line including all points, or use some genetic algorithm...
I'll try to write some plpgsql function as a first resolution POC later.