I have a data of points along the streets, I would like to turn those dots into simple coloured lines. Any pointers what this problem may be called or any algorithms that can help me solve this?
I was hoping to use PostGIS
functions to do this but I'm open to suggestions, this is a data from a .shp
file.
Edit1: Updated the picture to demonstrate ideal solution of this problem.
Drawing the line would be purely based on the distance between those points, there's nothing else that I can use to group them by. Ideally this would be points at max specified distance along the projected line? And by projected line I mean find 1st point then next one nearest to it then project a line and check if there are any points on this line at max distance to any of those already on the line.
Best Answer
You can use a recursive query to explore nearest neighbor of each point starting from each detected end of lines you want to build.
Prerequisites : prepare a postgis layer with your points and another with a single Multi-linestring object containing your roads. The two layers must be on the same CRS. Here is the code for the test data-set I created, please modify it as needed. (Tested on postgres 9.2 and postgis 2.1)
Here are the steps:
Generate for each point the list of every neighbors and theirs distance that meet theses three criteria.
Distance must not exceed a user defined ratio of the distance from the nearest neighbor (this should accommodate better to irregular digitalization than fixed distance)This part was actually too hard to implement, sticked to fixed search radiusLet's call this table "the graph"
Select end of line point by joining to the graph and keeping only point that have exactly one entry in the graph.
Let's call this table "eol" (end of line)
easy? that the reward for doing a great graph but hold-on things will go crazy at next step
Set up a recursive query that will cycle from neighbors to neighbors starting from each eol
Let's call this table "recurse_eol"
Keep only longest line for each start point and remove every exact duplicate path Example : paths 1,2,3,5 AND 5,3,2,1 are the same line discovered by it's two differents "end of line"
Manually checks remaining errors (isolated points, overlapping lines, weirdly shaped street)
Updated as promised, I still can't figure out why sometimes recursive query don't give exact same result when starting from opposite eol of a same line so some duplicate may remain in result layer as of now.
Feel free to ask I totally get that this code need more comments. Here is the full query: