Lack of consideration of number of lanes on highway portions lead to bad snapping in Map Matching

[laurent-chriqui]

Describe the bug
When the route is a highway with a large number of lanes, the points are not snapped on the correct road when the gps_accuracy is set to low values such as 15m.

Because OSM places the way roughly in the the middle of the actual multi lane road, points sometimes are not snapped on certain portions because GH doesn't take into account the number of lanes and hence the width of that road portion. And this can lead to broken sequences.

To Reproduce
Run map matching with gps_accuracy=15 and the following GPX file

<?xml version="1.0" encoding="UTF-8"?>\n<gpx xmlns="http://www.topografix.com/GPX/1/1" xmlns:gpxtpx="http://www.garmin.com/xmlschemas/TrackPointExtension/v1" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.topografix.com/GPX/1/1 http://www.topografix.com/GPX/1/1/gpx.xsd" version="1.1" creator="gpx.py -- https://github.com/tkrajina/gpxpy">\n  <trk>\n    <trkseg>\n      <trkpt lat="43.7213062" lon="4.1842265">\n        <time>2022-11-15T18:03:34+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>27.540000000000003</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7205676" lon="4.1878799">\n        <time>2022-11-15T18:04:35+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7182404" lon="4.1854886">\n        <time>2022-11-15T18:05:06+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.719211" lon="4.1826475">\n        <time>2022-11-15T18:05:36+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>17.82</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7229836" lon="4.181233">\n        <time>2022-11-15T18:06:06+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7271002" lon="4.1788537">\n        <time>2022-11-15T18:06:37+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7259377" lon="4.1778398">\n        <time>2022-11-15T18:07:07+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7245266" lon="4.1663032">\n        <time>2022-11-15T18:07:37+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7237127" lon="4.1527792">\n        <time>2022-11-15T18:08:08+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7182891" lon="4.1399795">\n        <time>2022-11-15T18:08:39+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7113779" lon="4.1287405">\n        <time>2022-11-15T18:09:10+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.7039516" lon="4.1178695">\n        <time>2022-11-15T18:09:40+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.697838" lon="4.1059378">\n        <time>2022-11-15T18:10:10+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.696463" lon="4.0913813">\n        <time>2022-11-15T18:10:41+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.693038" lon="4.0785319">\n        <time>2022-11-15T18:11:11+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.689549" lon="4.0640863">\n        <time>2022-11-15T18:11:42+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6856738" lon="4.0506326">\n        <time>2022-11-15T18:12:12+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6800437" lon="4.0391233">\n        <time>2022-11-15T18:12:43+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6765424" lon="4.0279658">\n        <time>2022-11-15T18:13:13+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6734005" lon="4.0176153">\n        <time>2022-11-15T18:13:44+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.670977" lon="4.0125738">\n        <time>2022-11-15T18:14:14+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6672738" lon="4.0072607">\n        <time>2022-11-15T18:14:44+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6603084" lon="3.9998478">\n        <time>2022-11-15T18:15:15+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6545083" lon="3.9922369">\n        <time>2022-11-15T18:15:46+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6491267" lon="3.9836212">\n        <time>2022-11-15T18:16:16+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6436133" lon="3.9754174">\n        <time>2022-11-15T18:16:46+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </exten9sions>\n      </trkpt>\n      <trkpt lat="43.6358844" lon="3.9705343">\n        <time>2022-11-15T18:17:17+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6290018" lon="3.96602">\n        <time>2022-11-15T18:17:47+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6225519" lon="3.9576182">\n        <time>2022-11-15T18:18:18+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6179214" lon="3.9493805">\n        <time>2022-11-15T18:18:49+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6141007" lon="3.9436283">\n        <time>2022-11-15T18:19:19+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6101974" lon="3.9384315">\n        <time>2022-11-15T18:19:50+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6080267" lon="3.9339111">\n        <time>2022-11-15T18:20:20+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6079773" lon="3.9310966">\n        <time>2022-11-15T18:20:51+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6083647" lon="3.9271085">\n        <time>2022-11-15T18:21:22+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>17.82</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6073482" lon="3.9248241">\n        <time>2022-11-15T18:21:52+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.606642" lon="3.9223599">\n        <time>2022-11-15T18:22:23+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n      <trkpt lat="43.6059944" lon="3.9212103">\n        <time>2022-11-15T18:22:54+0100</time>\n        <extensions>\n          <gpxtpx:accuracy>15</gpxtpx:accuracy>\n        </extensions>\n      </trkpt>\n    </trkseg>\n  </trk>\n</gpx>

The point at time step 20 gets only snapped on the road ref A9, instead of A709 as well leading to a broken sequence at time step 25 when the roads fully diverge.

Expected behavior
The A709 at the toll gate is per OSM 16 lanes wide, taking that into account would allow to estimate the road width and therefore snap the point on the right road.

Screenshots & Logs
Here is a screenshot illustrating the problem.

Here is the GeoJSON to visualize the whole trace.

{
  "type": "FeatureCollection",
  "features": [
    {
      "geometry": {
        "coordinates": [
          [
            4.184227,
            43.721306
          ],
          [
            4.18788,
            43.720568
          ],
          [
            4.185489,
            43.71824
          ],
          [
            4.182647,
            43.719211
          ],
          [
            4.181233,
            43.722984
          ],
          [
            4.178854,
            43.7271
          ],
          [
            4.17784,
            43.725938
          ],
          [
            4.166303,
            43.724527
          ],
          [
            4.152779,
            43.723713
          ],
          [
            4.139979,
            43.718289
          ],
          [
            4.128741,
            43.711378
          ],
          [
            4.11787,
            43.703952
          ],
          [
            4.105938,
            43.697838
          ],
          [
            4.091381,
            43.696463
          ],
          [
            4.078532,
            43.693038
          ],
          [
            4.064086,
            43.689549
          ],
          [
            4.050633,
            43.685674
          ],
          [
            4.039123,
            43.680044
          ],
          [
            4.027966,
            43.676542
          ],
          [
            4.017615,
            43.6734
          ],
          [
            4.012574,
            43.670977
          ],
          [
            4.007261,
            43.667274
          ],
          [
            3.999848,
            43.660308
          ],
          [
            3.992237,
            43.654508
          ],
          [
            3.983621,
            43.649127
          ],
          [
            3.975417,
            43.643613
          ],
          [
            3.970534,
            43.635884
          ],
          [
            3.96602,
            43.629002
          ],
          [
            3.957618,
            43.622552
          ],
          [
            3.949381,
            43.617921
          ],
          [
            3.943628,
            43.614101
          ],
          [
            3.938432,
            43.610197
          ],
          [
            3.933911,
            43.608027
          ],
          [
            3.931097,
            43.607977
          ],
          [
            3.927109,
            43.608365
          ],
          [
            3.924824,
            43.607348
          ],
          [
            3.92236,
            43.606642
          ],
          [
            3.92121,
            43.605994
          ]
        ],
        "type": "LineString"
      },
      "properties": {
        "deviceId": "dfebaacb-9837-4b5b-b78b-3fd294cc2d17",
        "endDate": "2022-11-15 18:22:54 +0100",
        "eventId": "33194ac5d3c7e5e75c6ef2fff1b633c0729758ef774c2ecaa574fb26693ee512",
        "startDate": "2022-11-15 18:03:34 +0100",
        "stroke": "blue"
      },
      "type": "Feature"
    },
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "coordinates": [
          4.012692714858903,
          43.67086517479349
        ],
        "type": "Point"
      }
    },
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "coordinates": [
          4.012270800371908,
          43.67119340723403
        ],
        "type": "Point"
      }
    }
  ]
}

Also the new error message for broken sequence is wrong in this case because it indicates Step 5, instead of step 25. I think we should record the maxTimeStep and use that instead of qe.timeStep (Error message).
Also we should probably refer to the original point index instead of the timestep which is after filtering of points and therefore is not always right in case some points were filtered out.

[michaz]

Thanks!

The main part is a "won't fix", I'm afraid. Streets, in this context, are going to remain lines rather than boxes. The gps_accuracy value needs to maintain enough slack for that.

Will fix the index in the error message.