2

I have two polylines, the first consists of individual GPS traces and the second is a series of road network poylines.

I wish to match the GPS trace polyline to that of a road network polyline or series of polylines in order to pass the time attribute from the GPS traces to the road network poyline(s). Of course, for a range of accuracy related reasons the GPS trace does not perfectly match the road network.

This may be visually inspected. The blue line shows the GPS trace polyline and the gray represents the road network polylines.

enter image description here

Due to the complexity of road junctions and directionality restrictions, a nearest neighbour match for the range of coordinates within the polyline won't work.

An example GPS trace polyline looks like this:

GPS_trace = [   
"polyline_decoded":[
          [51.5201035,-0.0965073],[51.5201,-0.09651],[51.52004,-0.09693],[51.5201406,-0.096996]],
"duration":15]

An example road polyline looks like this:

road_network_link = [
"polyline" : [
[51.5223,-0.0965],[51.521,-0.097],[51.52,-0.0979],[51.5212,-0.0970]]
"id" : "10200A"]

This appears to be the problem a good solution - https://developers.google.com/maps/documentation/roads/snap but I'd prefer to try myself first.

I have a large amount of GPS polylines and I am thus looking for a matching process that scales well. I'm aware this functionality exists in ArcGIS and QGIS.

My first inclination is to perform a shortest path algorithm for the GPS polyline points via the road link network network. Can anyone point me in the right direction?

Improve this question
3
  • 1
    What is your question? To try and determine what you are asking I looked for a question mark without success.
    – PolyGeo ♦
    Oct 12, 2016 at 12:32
  • Thanks PolyGeo. I edited my post. I realise this is quite general and I am looking for some pointers in the right direction.
    – LearningSlowly
    Oct 12, 2016 at 14:32
  • 1
    Take the centroid of each road segment and snap that to the gps route.
    – Hornbydd
    Oct 12, 2016 at 16:27

1 Answer 1

Reset to default
1

I created route, placed points on it 250 m apart, and randomly spread them from original position using normal distribution with standard deviation of 30 m:

Input

Iterations:

  1. Compute shortest path along network between 2 network nodes nearest to first and last “GPS” points
  2. Count number of links in that path, that are more than 100 m away from GPS points
  3. Break if none (assume path found), otherwise increase the cost of travel through selected links by factor of 100 and go to 1

After 3 iterations:

Iterations

Algorithm converged to this solution:

enter image description here

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.