mapbox / mapbox/nepomuk

Shape -> Line Matchings In presence of Loops

Open
#88 0 comments 0 reactions 0 assignees View on GitHub
Backend Bug
Dominant language
C++
Stars
24
Forks
7
PR merge metrics
No merged PRs in 30d

Description

screen shot 2017-04-10 at 12 20 34

In our responses, we would like to be able to output the geometry of intermediate legs along a line. Sadly, the shapes and stop locations do not line up. Usually, the stop locations are close to the shape of a line, but not located on it.

For the majority of lines, this does not pose a problem, since we can simply find the closest location on the shape to report when asking for the geometry between stops.

In presence of circles, this matching might not be correct/unique anymore, as we try to show with the above picture. In a small scenario:

```
a -- b -- c
g f |
e -- d
```

The line itself could provide a shape `abcdeba` while the stops go `abcdefg`. For `f,g` we can find the frist `b` and `a` instead of the second one, without any knowledge which would be correct.

To make things even worse, if we should see a line `abcdeba` instead of `abcdefg`, we would split this into two lines `abcde` `ba` with a hidden transfer between `e` and `b`. Both would refer to the same geometry, though.

For a correct mapping we need to ensure that the geometry we report is lined up with the stops. This can probably only be done by considering all stops and the full shape at the same time.

I imagine localising more or less clear candidates (ones which are clearly separated from the rest of the geometry, since only one very close candidate exists). Then we can assign intermediate stops to the closest element between these ranges.

The issue itself is located to the geometry_annotation_factory.cpp and should be pretty much self-contained.

- [ ] when resolved, remove check for offsets in geometry annotation (referenced by issue)

Contributor guide

Open the contributing guide

Research direction

Start with geometry_annotation_factory.cpp and trace how stops are matched to the full shape, especially around loops and repeated geometry. Review the offset check referenced in the issue. Done means intermediate-leg geometry remains correctly aligned with stops in looped shapes and the obsolete offset check can be removed.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.