1

How to project the journey onto the street?

  • The black polyline is inaccurate GPS data received from a mobile device, which positions the user trajectory inside the buildings, when it was actually on the road.
  • The gray square pin is a sample inaccurate position at 59.436543,24.742133
  • The green circled pin is the origin at 59.4367469,24.742495
  • The green starred pin is the destination at 59.436377,24.742235
  • The red crossed pin is what I would like to calculate as the more accurate position estimate?

getting-the-right-angles

here's the geojson data pictured above

What's the formula?

One way to get X would be to draw a straight line between the origin and the destination (the green line) and then draw a perpendicular line to the inaccurate position from that green line.. but I have no idea what algorithm is needed to implement that?

function align(inaccurLat, inaccurLon, originLat, originLon, destinLat, destinLon) {
  // ???
  return [alignedLat, alignedLon];
}
  • What code would return the coordinates of X using the known coordinates of the circled pin, the starred pin and the square pin?
  • The calculation should work regardless of where the inaccurate square position is: it might be on the left of the green line, but it might also be on the right of the green line, or in fact above the green line (above the origin).
  • The function would ideally be in JavaScript, but I could do the translation to JavaScript myself if needed.
  • It should work offline.

Looking for a simple map matching algorithm

Furthermore, I can draw many green lines, because I have many origin and destination pairs available to me as the reference points representing road segments that do not curve too much - as depicted in the image below:

segment-references-available

2

The term you are looking for, presumably is: Map Matching

There are a couple of different approaches to solve this problem, like a point-to-point-, point-to-curve-algorithm, etc. See this paper for more information. The basis of these simple, naive algorithms are calculations and comparisons of distances between single line segments and/or points. This means you have one segment of your grey user track and calculate the distance to all green segments of your road data. The green track with the smallest distance to your user track is now probably the track where the user really drives or walks. Instead of segments you can also compare only single points of your data.

But please keep in mind, that there can be errors if the user track is too far away from the original road or if there are many roads in the area.

With these approaches you match the trajectory of the user to the nearest road. For better results you can of course incorporate more factors like speed, direction of movement, etc. into your algorithm.

However Mapbox offers also an API, which you can use directly from you application. For more information see e.g. their blog post on this topic.

| improve this answer | |
  • Thank you! The pdf is rather heavy for someone like me, I was hoping that someone would help me by explicating the simplest formula with the inputs I have described (note that I have edited the question). I also added that the function should work offline, so I cannot use any remote APIs unfortunately. – Cel Jun 1 '17 at 14:26
  • 2
    Have a look at some open source implementations and/or at wikipedia: en.wikipedia.org/wiki/Map_matching – Karussell Jun 1 '17 at 15:14
  • 1
    @Cel I added an short explanation of these simple algorithms to my answer – tallistroan Jun 1 '17 at 17:19
1

To return the Red X the green line would have to be drawn correct and attributed with the To/Froms for both sides for the geocoding to interpolate this address. First you need spatially correct ranged roads. Second the address still may not be placed in the correct location as they may not have used GIS to address the buildings. Strange as it seems, some people assign their own address and it sticks putting the interpolated address and the "Real" address at different locations.

Due to the quality of different GPS units and their errors, where they place you may easily be 5-15 meters from the real location. When we GPS streetlights or signs we try to place them within 6 feet, at that difference if they can't find the streetlight or sign it's not really an accuracy issue.

Now to come up with code that will adjust bad data? I often see spatial road data 50 feet off on one street and then 150 feet off in the other direction a street over. You would have to adjust every street and that is expensive and time consuming.

| improve this answer | |
  • I have the correct "road" coordinates available in the form of the origin latitude&longitude and destination latitude&longitude. And am not looking for address, but X should also be latitude&longitude (on the green line). I do not really follow you I'm afraid, so still looking for the function :) – Cel Jun 1 '17 at 12:50
  • 1
    Roads are often segmented (ranged) with starting and ending addresses, this is used to interpolate addresses base on the number of addresses and the length of the road. You don't have this, so if you have the distance between each green point, and the distance from the starting point to the gray point and the distance from the end point to the gray point you can use ratios to determine the distance between. But I'm not sure how to place it along the line between the points. However if the road curves and your plotting a straight line, it will take you off the road just like you started with. – Bill Chappell Jun 1 '17 at 13:07
  • Thanks, I think I understand better now (: Please see my edited question, I'm still hoping for a relatively simple formula for the requirements I have described, something like X = f ( □lat, □lon, Olat, Olon, *lat, *lon ) – Cel Jun 1 '17 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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