Calculating distance for each road ID returned in debug format

[larnacoeur]

Hi, as far as I understand, right now, in debug response format, Barefoot returns matched geometry along with a set of road IDs the car was travelling on (if I'm wrong, please correct me). I would like to know which points from returned geometry belongs to each road ID to calculate distances or percentage values of each road ID in every returned segment. Is there a way to modify Barefoot's response format to include such data?

Thanks in advance for your help!

[smattheis]

The debug format contains for each position sample the matched road id. Hence, it does not necessary include the full sequence of road ids that the car was traveling on. To output the complete sequence of road ids with its geometry you could modify the toDebugJSON method in src/main/java/com/bmwcarit/barefoot/matcher/MatcherKState.java to something similar to this (not tested):

JSONArray jsonpath = new JSONArray();
if (this.sequence() != null) {
    for (int i = 0; i < this.sequence().size(); ++i) {
        MatcherCandidate candidate = this.sequence().get(i);
        JSONObject jsoncandidate = new JSONObject();
        jsoncandidate.put("time", this.samples().get(i).time() / 1000);
        jsoncandidate.put("road", candidate.point().edge().id());
        jsoncandidate.put("frac", candidate.point().fraction());
        if (candidate.transition() != null) {
            JSONArray jsonroads = new JSONArray();
            for (int j = 0; j < candidate.transition().route().size(); ++j) {
                JSONObject tuple = new JSONObject();
                tuple.put("id", candidate.transition().route().get(j).id());
                tuple.put(
                        "geom",
                        GeometryEngine.geometryToWkt(candidate.transition().route().get(j)
                                .geometry(), WktExportFlags.wktExportLineString));
                jsonroads.put(tuple);
            }
            jsoncandidate.put("roads", jsonroads);
        } else {
            jsoncandidate.put("geom", GeometryEngine.geometryToWkt(candidate.point()
                    .geometry(), WktExportFlags.wktExportPoint));
        }
        jsonpath.put(jsoncandidate);
    }
}
return jsonpath;

Please note that for dense sampling of position measurement, this will include lots of redundant information, i.e., if positions match to the same road it will output geometry of the same road multiple times.

[larnacoeur]

That's what I've been looking for! Thank you very much!

[larnacoeur]

I have one last question here. Like you said, this solution isn't perfect as it gives lots of geometry duplicates. I'm handling it manually client-side right now. Last thing is that it returns too many points before route start point and after route end point. Is there any way to get rid of it?

[smattheis]

Can you please check if there are actually multiple samples at the last location, i.e. samples with different timestamps but nearly same GPS coordinates? If so, try increasing matcherMinDistance to something like 5 (meters). If not, I would need the input and result data to check what's the problem.

[larnacoeur]

I checked, you were right, there was multiple samples at the end of the route. I changed matcherMinDistance to 5, restarted Barefoot and even manually filtered out duplicate samples client-side, but the problem still exists and apears just as showed in the picture above. I'm wondering if it's caused by modifications I made to debug json response function. Can it be possible?

[smattheis]

The map matching seems to rank the opposite side of the road to be more likely and, hence, takes the route to the end of the road, makes a u-turn and goes back. Without a look into the data and the respective map, it's difficult to make give a hint. Also, I doubt that it's because of the output formatting.

Hint: It seems that your trace is actually approaching the destination, which seems to be the hospital. I guess the trace continues going on some unmapped road closer to the hospital and, hence, map matching ranks the other road side to be a more likely matching at some point in time. So it's actually a valid result since the map doesn't include the road or the intersection that the object is taking. You probably want the map matching to stop at that point, so you acutally need some kind of logic that detects the "mapped destination" of your trace. You could to the following:

Take the last measured position, search the nearest point on some road, and define this as the final destination. Then, discard all measurements at the end of the trace that have a larger distance to the final destination than some minimum reached before. As a little helper, see https://github.com/bmwcarit/barefoot#spatial-search for the road search and https://github.com/bmwcarit/barefoot#spatial-operations for distance calculation.

Addition: If you have traces with frequent destinations, you can define some hotspots and pre-process traces respectively with hotspots as final destinations once a trace reaches a certain radius of some hotspot. As a little helper for hotspot analysis, see https://github.com/bmwcarit/barefoot#spatial-cluster-analysis to approach it with spatial cluster analysis.

Rationale: This map matching behavior is a design decision that respects the direction of roads and traces. If we would neglect the direction, it would be easier for you here, but position measurement would result in unrealistic routes with unrealistic u-turns if deviations are little larger. Because of this decision, one has to handle the start/end of traces with unmapped roads specially, e.g. as described above.

[larnacoeur]

I understand this, thank you very much for detailed explaination. I'll handle route ends just like you said. My problem now is those geometry duplicates.. Until now I was just removing them, so if the two segments contained same road id I was putting its geometry to first segment. But the problem is, that, for my calculations to work I need matched segments to be exacltly matched with position samples. Do you think there is a way to achieve such output from Barefoot?

[smattheis]

I'm not sure what you mean: If you want the exact matched position of each sample with the respective road geometry, you can add the geometry of the road and also the exact position on the road like this:

JSONArray jsonpath = new JSONArray();
if (this.sequence() != null) {
    for (int i = 0; i < this.sequence().size(); ++i) {
        MatcherCandidate candidate = this.sequence().get(i);
        JSONObject jsoncandidate = new JSONObject();
        jsoncandidate.put("time", this.samples().get(i).time() / 1000);
        jsoncandidate.put("road", candidate.point().edge().id());
        jsoncandidate.put("frac", candidate.point().fraction());
        jsoncandidate.put("geom", GeometryEngine.geometryToWkt(candidate.point().edge()
                                .geometry(), WktExportFlags.wktExportLineString));
        jsoncandidate.put("point", GeometryEngine.geometryToWkt(candidate.point()
                                .geometry(), WktExportFlags.wktExportPoint));
        jsonpath.put(jsoncandidate);
    }
}
return jsonpath;

The timestamp should be sufficient to map it to your sample data. Of course, this doesn't give a continuous geometry of the path if there is no position sample matched to some road that, however, belongs to the path. Basically, all information is available. :)

[larnacoeur]

It's not what I mean :) Right now, Barefoot returns something like:

[{
    "time": 1471509059,
    "road": 124928716,
    "roads": [{
        "id": 105285935,
        "geom": "LINESTRING (19.463415 52.4350311, 19.4631816 52.4341445, 19.4631088 52.4338273, 19.4631016 52.4336454, 19.4631774 52.4335531)"
    }, {
        "id": 87873017,
        "geom": "LINESTRING (19.4631774 52.4335531, 19.463128 52.4334915, 19.4630595 52.4333102, 19.4629965 52.4330413)"
    }, {
        "id": 7458686,
        "geom": "LINESTRING (19.4629965 52.4330413, 19.4629416 52.4328331)"
    }, {
        "id": 7458688,
        "geom": "LINESTRING (19.4629416 52.4328331, 19.4629172 52.4327538)"
    }, {
        "id": 124928716,
        "geom": "LINESTRING (19.4629172 52.4327538, 19.4626956 52.4319333)"
    }],
    "frac": 0.3911227064395014
}, {
    "time": 1471509078,
    "road": 115904455,
    "roads": [{
        "id": 124928716,
        "geom": "LINESTRING (19.4629172 52.4327538, 19.4626956 52.4319333)"
    }, {
        "id": 115904455,
        "geom": "LINESTRING (19.4626956 52.4319333, 19.4631246 52.4318226, 19.4636378 52.4317542, 19.4640542 52.4317082)"
    }],
    "frac": 0.044380183209406954
}]

... As far as I understand it is the list of route segments between each pair of measured positions. But because of geometry duplicates I can't say which points in duplicated geometry belongs to which segment, which is crucial in my further computations. I need matched segments to start and end as close to the sample positions as possible. Do you know what I mean now? It's really hard to explain.

[smattheis]

The reading of your sample is as follows:

Sample with timestamp 1471509059 is matched on road 124928716, whereas sample with timestamp 1471509078 is matched on road 115904455. On the way from the first to the second, your object has taken the path consisting of road sequence 124928716,115904455. The respective geometries of the roads are included. The only thing that I understand that's missing in your output is the exact position on the road which is outputted if you add this line:

jsoncandidate.put("point",GeometryEngine.geometryToWkt(candidate.point().geometry(), WktExportFlags.wktExportPoint));

(Side note: The fraction frac determines exactly this point, given as offset along the road.)

The path to the first sample with timestamp 1471509059is the road sequence 1471509059,87873017,7458686,7458688,124928716, respectively.

Basically, there are no random duplicates. - They only occur because each path from one sample to the next includes start and end road.