How the route is drawn on maps between points?

[enshu]

Hi, I have to write a paper for my studies on how a route is drawn on maps e.g. GoogleMaps/BingMaps between selected markers. It is not about determining the optimal/shortest route, but how a line is drawn running perfectly along the streets and not, for example, next to them or cutting through the entire map with a straight line from point to point, also in corners to be a smooth arc. I have searched for information on this topic but cannot find anything that explains it. Could you please help me find some literature, maybe a scientific publication or an article, or keywords by which I can find something on this subject.

Thank you in advace

 

[sdifox]

GIS road network consists of line segments. They are just using a subset of the whole map.

 

[enshu]

GIS road network consists of line segments. They are just using a subset of the whole map.

Hi, thanks sdifox for the information about GIS. It has helped me to find a starting point, but I am still missing some information.

I have found that Google has an API such as "Snap to Roads" which, by collecting location points e.g. from GPS, matches them to the nearest road, and has the ability to turn on interpolation to fill in the points between the collected GPS positions so that the road line is smooth e.g. in curves.

The second API from Google is "Nearest Road", which can be given various points that do not necessarily connect into a path, and it will connect them into a route.

Similar API is provided by Microsoft.
Documentation of the API's describe only basicly what this service do, and what parameters needs to be provided, and what output we will receive.

As I understand, both Google and Microsoft have their own databases (like GIS with road network in form of line segments) with information about the exact location of roads and they match with the points sent as parameters. Unfortunately I can't find anything about that :/

So my 2 questions are:
1. Does Google and Microsoft have thier own GIS System, with database with location of all roads?
2. How it works when we send a request, because as on screen below we miss lots of information from GPS, and interpolation will not help in this case, so how the missing part of the road was found?

 

[sdifox]

They have their own gis, although the starting point is probably a data vendor and public sources.

I don't know what you mean by missing a lot of information from your gps, all you need is lat long from your gps. What you see on the screen is a very small subset of the data they have.

 

[enshu]

They have their own gis, although the starting point is probably a data vendor and public sources.

I don't know what you mean by missing a lot of information from your gps, all you need is lat long from your gps. What you see on the screen is a very small subset of the data they have.

What I wanted to say by the missing GPS information is that in the left image which shows the raw GPS data we don't have any positions (lat, long) on the turns marked with arrows, and somehow they were marked by this API as in the right image.

 

[sdifox]

What I wanted to say by the missing GPS information is that in the left image which shows the raw GPS data we don't have any positions (lat, long) on the turns marked with arrows, and somehow they were marked by this API as in the right image.

Raw gis data is a bunch of numbers. What you are seeing is a graphical representation. Unless you have the shapefile you don't know what level of detail is actual data and what is interpreted.

Road network is also a lot of data.

 

[mxnerd]

Used Google My Maps to draw a route between Ralphs and Vons supermarkets and exported the route as KML file.

Apparently you have to use hundreds of coordinates to draw the route.

Save the following code as KML file and upload it to and you can view it online at

KML, KMZ Viewer with Drive

KML, KMZ Viewer is a tool that views the .kml, .kmz file in your browser. Free online tool to view KML, KMZ files from the web on a Google map. You can open KML, KMZ files from URL, Google Drive or from your computer.

kmlviewer.nsspot.net

or yours Google My Maps

<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://www.opengis.net/kml/2.2">
  <Document>
    <name>Directions from Ralphs to Vons, Sunset Boulevard, Pacific Palisades, CA, USA</name>
    <Style id="icon-1899-DB4436-nodesc-normal">
      <IconStyle>
        <color>ff3644db</color>
        <scale>1</scale>
        <Icon>
          <href>https://www.gstatic.com/mapspro/images/stock/503-wht-blank_maps.png</href>
        </Icon>
        <hotSpot x="32" xunits="pixels" y="64" yunits="insetPixels"/>
      </IconStyle>
      <LabelStyle>
        <scale>0</scale>
      </LabelStyle>
      <BalloonStyle>
        <text><![CDATA[<h3>$[name]</h3>]]></text>
      </BalloonStyle>
    </Style>
    <Style id="icon-1899-DB4436-nodesc-highlight">
      <IconStyle>
        <color>ff3644db</color>
        <scale>1</scale>
        <Icon>
          <href>https://www.gstatic.com/mapspro/images/stock/503-wht-blank_maps.png</href>
        </Icon>
        <hotSpot x="32" xunits="pixels" y="64" yunits="insetPixels"/>
      </IconStyle>
      <LabelStyle>
        <scale>1</scale>
      </LabelStyle>
      <BalloonStyle>
        <text><![CDATA[<h3>$[name]</h3>]]></text>
      </BalloonStyle>
    </Style>
    <StyleMap id="icon-1899-DB4436-nodesc">
      <Pair>
        <key>normal</key>
        <styleUrl>#icon-1899-DB4436-nodesc-normal</styleUrl>
      </Pair>
      <Pair>
        <key>highlight</key>
        <styleUrl>#icon-1899-DB4436-nodesc-highlight</styleUrl>
      </Pair>
    </StyleMap>
    <Style id="line-1267FF-5000-nodesc-normal">
      <LineStyle>
        <color>ffff6712</color>
        <width>5</width>
      </LineStyle>
      <BalloonStyle>
        <text><![CDATA[<h3>$[name]</h3>]]></text>
      </BalloonStyle>
    </Style>
    <Style id="line-1267FF-5000-nodesc-highlight">
      <LineStyle>
        <color>ffff6712</color>
        <width>7.5</width>
      </LineStyle>
      <BalloonStyle>
        <text><![CDATA[<h3>$[name]</h3>]]></text>
      </BalloonStyle>
    </Style>
    <StyleMap id="line-1267FF-5000-nodesc">
      <Pair>
        <key>normal</key>
        <styleUrl>#line-1267FF-5000-nodesc-normal</styleUrl>
      </Pair>
      <Pair>
        <key>highlight</key>
        <styleUrl>#line-1267FF-5000-nodesc-highlight</styleUrl>
      </Pair>
    </StyleMap>
    <Placemark>
      <name>Directions from Ralphs to Vons, Sunset Boulevard, Pacific Palisades, CA, USA</name>
      <styleUrl>#line-1267FF-5000-nodesc</styleUrl>
      <LineString>
        <tessellate>1</tessellate>
        <coordinates>
          -118.5238,34.04524,0
          -118.52366,34.04513,0
          -118.52363,34.04511,0
          -118.52361,34.04511,0
          -118.5236,34.0451,0
          -118.52359,34.04511,0
          -118.52358,34.04511,0
          -118.52357,34.04511,0
          -118.52356,34.04512,0
          -118.52355,34.04512,0
          -118.52347,34.04518,0
          -118.5233,34.0453,0
          -118.52387,34.04577,0
          -118.52397,34.04586,0
          -118.52427,34.04611,0
          -118.52451,34.04631,0
          -118.52456,34.04635,0
          -118.52466,34.04642,0
          -118.52471,34.04646,0
          -118.52517,34.04683,0
          -118.52544,34.04707,0
          -118.5255,34.04713,0
          -118.52583,34.04739,0
          -118.52596,34.04751,0
          -118.52611,34.04763,0
          -118.5262,34.0477,0
          -118.52628,34.04775,0
          -118.52645,34.04786,0
          -118.52649,34.04788,0
          -118.52656,34.04791,0
          -118.52664,34.04794,0
          -118.52678,34.04798,0
          -118.5269,34.04806,0
          -118.52706,34.04809,0
          -118.52715,34.0481,0
          -118.52735,34.04814,0
          -118.52739,34.04815,0
          -118.52753,34.04819,0
          -118.52754,34.04819,0
          -118.5276,34.04821,0
          -118.52761,34.04821,0
          -118.5277,34.04825,0
          -118.52773,34.04826,0
          -118.52785,34.04832,0
          -118.52788,34.04834,0
          -118.52791,34.04836,0
          -118.52796,34.04839,0
          -118.52797,34.0484,0
          -118.52802,34.04843,0
          -118.52815,34.04854,0
          -118.5282,34.04858,0
          -118.52829,34.04869,0
          -118.52834,34.04874,0
          -118.52837,34.04879,0
          -118.52841,34.04887,0
          -118.52844,34.04892,0
          -118.52849,34.04904,0
          -118.52855,34.04916,0
          -118.52859,34.04922,0
          -118.52864,34.04929,0
          -118.52867,34.04932,0
          -118.52872,34.04938,0
          -118.52877,34.04943,0
          -118.52884,34.0495,0
          -118.52892,34.04956,0
          -118.52894,34.04957,0
          -118.52902,34.04963,0
          -118.52908,34.04967,0
          -118.52926,34.04977,0
          -118.5294,34.04983,0
          -118.5296,34.04988,0
          -118.52972,34.04991,0
          -118.52982,34.04993,0
          -118.5299,34.04993,0
          -118.53003,34.04994,0
          -118.53006,34.04994,0
          -118.53026,34.04993,0
          -118.53037,34.04991,0
          -118.53045,34.0499,0
          -118.53057,34.04988,0
          -118.53067,34.04985,0
          -118.53082,34.04979,0
          -118.53085,34.04978,0
          -118.5309,34.04976,0
          -118.53106,34.04968,0
          -118.53114,34.04962,0
          -118.53121,34.04958,0
          -118.53132,34.04949,0
          -118.53139,34.04942,0
          -118.53154,34.04927,0
          -118.53158,34.04923,0
          -118.53164,34.04918,0
          -118.53172,34.04911,0
          -118.53181,34.04905,0
          -118.53198,34.04897,0
          -118.53204,34.04894,0
          -118.53212,34.04891,0
          -118.53218,34.04888,0
          -118.53232,34.04884,0
          -118.53239,34.04883,0
          -118.53244,34.04882,0
          -118.53251,34.0488,0
          -118.53262,34.04879,0
          -118.53273,34.04878,0
          -118.53286,34.04879,0
          -118.53301,34.04881,0
          -118.53311,34.04882,0
          -118.53322,34.04882,0
          -118.53333,34.04883,0
          -118.53341,34.04879,0
          -118.53361,34.04881,0
          -118.53428,34.04886,0
          -118.53479,34.04888,0
          -118.53517,34.04889,0
          -118.53544,34.04891,0
          -118.5357,34.04892,0
          -118.53592,34.04893,0
          -118.536,34.04893,0
          -118.53614,34.04893,0
          -118.5362,34.04893,0
          -118.53627,34.04892,0
          -118.53633,34.04891,0
          -118.53635,34.04891,0
          -118.53641,34.0489,0
          -118.53658,34.04887,0
          -118.53755,34.04866,0
          -118.53796,34.04858,0
          -118.53807,34.04858,0
          -118.53837,34.04852,0
          -118.53846,34.04851,0
          -118.53853,34.04851,0
          -118.5386,34.04851,0
          -118.5387,34.04852,0
          -118.53882,34.04855,0
          -118.53893,34.04858,0
          -118.539,34.04861,0
          -118.53907,34.04865,0
          -118.53925,34.04874,0
          -118.53931,34.04877,0
          -118.53938,34.0488,0
          -118.53944,34.04882,0
          -118.53953,34.04885,0
          -118.53967,34.04888,0
          -118.53985,34.0489,0
          -118.53993,34.04891,0
          -118.53998,34.04891,0
          -118.54002,34.04891,0
          -118.54007,34.04892,0
          -118.54018,34.04891,0
          -118.5402,34.04891,0
          -118.54027,34.04891,0
          -118.5404,34.04889,0
          -118.54051,34.04887,0
          -118.54058,34.04885,0
          -118.54063,34.04884,0
          -118.54081,34.04877,0
          -118.54096,34.04872,0
          -118.54098,34.04871,0
          -118.54104,34.04866,0
          -118.54114,34.04863,0
          -118.54171,34.04852,0
          -118.5419,34.04848,0
          -118.54223,34.04841,0
          -118.54279,34.04831,0
          -118.54295,34.04827,0
          -118.54308,34.04823,0
          -118.54314,34.0482,0
          -118.5432,34.04817,0
          -118.54324,34.04815,0
          -118.54329,34.04812,0
          -118.54342,34.04803,0
          -118.54349,34.04797,0
          -118.54354,34.04793,0
          -118.54358,34.04788,0
          -118.54362,34.04783,0
          -118.54368,34.04774,0
          -118.54372,34.04768,0
          -118.54375,34.04763,0
          -118.54376,34.04761,0
          -118.54377,34.04757,0
          -118.54379,34.04752,0
          -118.54382,34.04741,0
          -118.54384,34.04729,0
          -118.54384,34.04685,0
          -118.54383,34.0467,0
          -118.5438,34.04651,0
          -118.54372,34.04622,0
          -118.54372,34.04619,0
          -118.54371,34.04613,0
          -118.5437,34.04603,0
          -118.54369,34.04584,0
          -118.5437,34.04541,0
          -118.54372,34.04523,0
          -118.54375,34.04511,0
          -118.54376,34.04506,0
          -118.54378,34.04499,0
          -118.54391,34.04459,0
          -118.54399,34.04436,0
          -118.54401,34.04429,0
          -118.54404,34.04422,0
          -118.54406,34.04419,0
          -118.54408,34.04413,0
          -118.54412,34.04405,0
          -118.54414,34.04402,0
          -118.54417,34.04396,0
          -118.54421,34.0439,0
          -118.54426,34.04384,0
          -118.54431,34.04378,0
          -118.54437,34.04372,0
          -118.5445,34.0436,0
          -118.54452,34.04358,0
          -118.54458,34.04353,0
          -118.54464,34.04349,0
          -118.54471,34.04345,0
          -118.54478,34.04341,0
          -118.54483,34.04338,0
          -118.54491,34.04335,0
          -118.54504,34.0433,0
          -118.54549,34.04313,0
          -118.54624,34.04285,0
          -118.54767,34.04233,0
          -118.54783,34.04227,0
          -118.54803,34.0422,0
          -118.5487,34.04196,0
          -118.54876,34.04193,0
          -118.54905,34.04182,0
          -118.54913,34.04183,0
          -118.54929,34.04179,0
          -118.54975,34.04162,0
          -118.54992,34.04154,0
          -118.55012,34.04147,0
          -118.55014,34.04146,0
          -118.55036,34.04138,0
          -118.55045,34.04135,0
          -118.55059,34.0413,0
          -118.55071,34.04128,0
          -118.55088,34.04128,0
          -118.55097,34.04128,0
          -118.551,34.04128,0
          -118.55111,34.0413,0
          -118.55118,34.04132,0
          -118.55122,34.04133,0
          -118.55137,34.04139,0
          -118.55143,34.04142,0
          -118.5515,34.04147,0
          -118.55155,34.04151,0
          -118.5516,34.04155,0
          -118.55164,34.04159,0
          -118.55169,34.04167,0
          -118.55172,34.04171,0
          -118.55175,34.04177,0
          -118.55177,34.04182,0
          -118.55178,34.04185,0
          -118.55179,34.04189,0
          -118.5518,34.04194,0
          -118.55181,34.04199,0
          -118.55181,34.04201,0
          -118.55181,34.04204,0
          -118.55181,34.04207,0
          -118.55181,34.0421,0
          -118.55182,34.04213,0
          -118.55181,34.04216,0
          -118.5518,34.04223,0
          -118.55179,34.04227,0
          -118.55178,34.04233,0
          -118.55177,34.04234,0
          -118.55177,34.04236,0
          -118.55176,34.04239,0
          -118.55174,34.04242,0
          -118.55172,34.04246,0
          -118.5517,34.0425,0
          -118.55167,34.04254,0
          -118.55164,34.04259,0
          -118.55162,34.04262,0
          -118.55159,34.04264,0
          -118.55159,34.04265,0
          -118.55157,34.04267,0
          -118.55155,34.04269,0
          -118.55152,34.04271,0
          -118.55149,34.04274,0
          -118.55141,34.0428,0
          -118.55127,34.04291,0
          -118.55115,34.04299,0
          -118.55111,34.04303,0
          -118.55107,34.04308,0
          -118.55104,34.04312,0
          -118.55101,34.04316,0
          -118.55098,34.04321,0
          -118.55096,34.04326,0
          -118.55093,34.04333,0
          -118.55091,34.04339,0
          -118.5509,34.04345,0
          -118.55089,34.04348,0
          -118.55089,34.04355,0
          -118.55089,34.04362,0
          -118.55089,34.0437,0
          -118.55095,34.04394,0
          -118.55098,34.04399,0
          -118.55101,34.04404,0
          -118.55104,34.04409,0
          -118.55107,34.04412,0
          -118.55109,34.04415,0
          -118.55113,34.04419,0
          -118.55117,34.04423,0
          -118.55121,34.04426,0
          -118.55125,34.04429,0
          -118.5513,34.04433,0
          -118.55139,34.04437,0
          -118.55145,34.04439,0
          -118.5515,34.04441,0
          -118.55157,34.04443,0
          -118.55164,34.04445,0
          -118.55171,34.04446,0
          -118.55181,34.04448,0
          -118.55193,34.04448,0
          -118.55208,34.04446,0
          -118.55222,34.04442,0
          -118.55225,34.0444,0
          -118.55227,34.04439,0
          -118.55229,34.04436,0
          -118.55231,34.04434,0
          -118.55249,34.04426,0
          -118.55254,34.04422,0
          -118.55259,34.04419,0
          -118.55269,34.0441,0
          -118.55285,34.04395,0
          -118.55307,34.04376,0
          -118.55314,34.04369,0
          -118.55336,34.04343,0
          -118.55362,34.04309,0
          -118.55389,34.04265,0
          -118.55393,34.04258,0
          -118.55395,34.04253,0
          -118.55397,34.04247,0
          -118.55399,34.04241,0
          -118.55402,34.04228,0
          -118.55402,34.0422,0
          -118.55402,34.04211,0
          -118.55402,34.04203,0
          -118.55401,34.04192,0
          -118.554,34.04187,0
          -118.55397,34.04177,0
          -118.55393,34.0417,0
          -118.55389,34.04161,0
          -118.55387,34.04157,0
          -118.55374,34.0413,0
          -118.55372,34.04126,0
          -118.55372,34.04124,0
          -118.55371,34.04122,0
          -118.55368,34.04114,0
          -118.55367,34.04107,0
          -118.55367,34.04103,0
          -118.55366,34.041,0
          -118.55365,34.04095,0
          -118.55365,34.04083,0
          -118.55365,34.04076,0
          -118.55366,34.04075,0
          -118.55366,34.04072,0
          -118.55367,34.0407,0
          -118.55368,34.04067,0
          -118.55369,34.04064,0
          -118.5537,34.0406,0
          -118.55372,34.04055,0
          -118.55374,34.04051,0
          -118.55375,34.04048,0
          -118.55376,34.04047,0
          -118.55376,34.04046,0
          -118.55378,34.04041,0
          -118.55381,34.04037,0
          -118.55383,34.04034,0
          -118.55385,34.04031,0
          -118.55388,34.04028,0
          -118.5539,34.04026,0
          -118.55391,34.04025,0
          -118.55399,34.04017,0
          -118.5541,34.04007,0
          -118.55424,34.03993,0
          -118.55438,34.03981,0
          -118.55441,34.03977,0
          -118.55463,34.03956,0
          -118.55469,34.0395,0
          -118.55448,34.03932,0
          -118.55444,34.03921,0
          -118.55439,34.03908,0
          -118.55433,34.03887,0
          -118.55413,34.03889,0
          -118.55425,34.0392,0
        </coordinates>
      </LineString>
    </Placemark>
    <Placemark>
      <name>Ralphs</name>
      <styleUrl>#icon-1899-DB4436-nodesc</styleUrl>
      <Point>
        <coordinates>
          -118.5237969,34.0452417,0
        </coordinates>
      </Point>
    </Placemark>
    <Placemark>
      <name>Vons, Sunset Boulevard, Pacific Palisades, CA, USA</name>
      <styleUrl>#icon-1899-DB4436-nodesc</styleUrl>
      <Point>
        <coordinates>
          -118.554254,34.0391992,0
        </coordinates>
      </Point>
    </Placemark>
  </Document>
</kml>

and here is the result

 

[mxnerd]

Apparently you can use Google Map/Road/Direction API to draw the route with code. There are many tutorials on youtube.

Also someone at StackExchange answers part of your question.

https://gis.stackexchange.com/questions/44676/where-can-i-download-the-google-road-network-as-shapefile

 

[enshu]

Thank you guys, for all the informations. They are very helpful, I have a last question.
While we have a collection of data from GPS, which are not matching the roads in 100% is there some known algorithm that match this points with the road?
Like on example below I used Google Snap to Roads Demo, and selected some points on map (grey line) and API created a path (blue line)



I found some papers about "Map-Matching Algorithm" or "Map-Matching Method" which is about "In the proposed MDP-MM algorithm, the MDP technique is used to minimise the number of candidate routes maintained at each GPS point, while guaranteeing to determine the best matching route. "

Is that a good path to search?

 

[mxnerd]

No idea. See if this help.

snap to road open source - Google Suche

www.google.com

 

[mpo]

see next post

 

[mpo]

Sorry, a little late to help you directly. 99% of the time we rely on APIs from ESRI, etc. to keep the GPS on the correct route.

For the few times we have to rely on hand-coding logic, the basemaps we use have the road relations semi-built in. Yes, the roads are made up of a bunch of lines. But, the lines have a hierarchy. In your map snip above, Harris St. is made up of a bunch of smaller segments (Harris, start to Pirrama Rd; Pirrama Rd to service rd; etc. etc.)

We build in the logic, as long as we are traveling on Harris St, stay on Harris St. That may sound basic, but the GPS output is a cloud of points. There is error built into the process. Sometimes the GPS will resolve to a cross street. We'll tell the system to ignore that location unless the vehicle has turned.

 

[Cy_kkm]

To match a sequence of GPS readouts (each readout consists of: a point in some coordinate system where the car most likely is; confidence radius around the point, i.e. a circle around the point where the car can possibly be, to the given cutoff in variance—GPS receiver provides this information too; and the time when the measurements are taken, i. e., 4-tuples (q1, q2, r, t)) to a map (a collection of connected line segments with known starts and ends, as tuples (q1, q2), the Extended Kalman filter (EKF) is a very powerful algorithm. It augments the measurements with a model of constrained motion, such that the map is treated as part of the model, in addition to other restriction on possible motion. The model accounts for our "normal" known facts about normal traffic: vehicles move on streets, but rarely parallel to and 10m off a street for a long time; cars do not make sharp 90⁰ turns while traveling at 100km/h; cars cannot move at 300km/h; cars cannot accelerate 0 to 100 km/h in 1 second; cars do not cross randomly between parallel streets; etc. The model assigns a quantitative cost for violating each rule. For example, if the navigation erroneously calculated from the sequence of GPS points that you are driving on a close by but parallel street, the accumulated position error will exceed the cost of violating the "no jump" rule (the farther the jump, the more cost the model assigns to the jump), and your marker will jump on the nav screen to the correct street.

I'm sure you seen that effect: you're driving by directions and decide to exit the freeway (in case of using directions, the model also subtracts a hefty cost for following the precomputed direction path, i.e. it assumes that you're much more likely to follow the directions than not). The point on nav screen continues to track you on the freeway for a few second, but then the divergence between the computed and modeled positions exceeds the cost of a sudden jump, and you're moved, but... on a wrong ramp at a multilevel crossing! Then, in a couple seconds the model "realizes" you're not really following the ramp it put you on, and finally places you on the correct street, sometimes only when you exit the multilevel traffic tangle of ramps.

If the database also has posted speed limit information for streets, or, better yet, current traffic speed (Google maps show realtime traffic, as everyone who is driving with Maps (and didn't opt out) sends anonymized speed information to Google to aggregate), the model can also take this information into account. It will punish the computed trajectory for moving significantly faster than the traffic (or, at the least, much faster than the posted limit), correcting for the raw GPS measurement errors—but reasonably, as traffic speed may change quickly, and the average traffic info may be stale.

The model of motion can also be very simple, and this is how the topic is usually taught in ML or DSP courses: if you're driving across a salt plain in the Mojave desert, the only sensible model's assumption is that the vehicle keeps its speed and direction constant when you're unobserved by GPS and when aggregating measurements having a large uncertainty. This is the Ordinary Kalman filter (OKF). The simple case is essential for understanding, as it uses a linear basis; read about this algorithm first. It's a simple and elegant way to deal with measurement uncertainties in a simply constrained motion. The transition from OKF to EKF is a replacement of linear basis with a Hidden Markov basis. EKF is used in real street navigation systems, as it allows for arbitrary non-linear motion constraints.