mapbox / mapbox/vector-tile-spec

Support 'correction-of-prediction' encoding for linestrings

Open
#137 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Future Release
Dominant language
No language data
Stars
1k
Forks
213
PR merge metrics
No merged PRs in 30d

Description

I am suggesting a new encoding type for linestrings which is smaller for objects that have minimal curvature, such as roads which generally continue in their previous direction.

The current approach is to encode the first point and then the delta for the following points. I tested a slightly different approach that is ~17% smaller (at least on the data I used). The idea is as follows. The first point is encoded in full, the second point is encoded as the delta of the first, and then all subsequent points are encoded as a 'correction-of-prediction'.

The first two points are identical to the current approach. To calculate the 3rd point (and subsequent points), a vector is drawn from the first to second point, that vector is then added to the second point(this is the prediction of where the 3rd point should be) and then the value that is encoded is used to correct the prediction. Mathematically

p1: encoded as (x1, y1), calculated as (x1, y1)
p2: encoded as (dx1, dy1), calculated as (x1 + dx1, y1 + dy1)
p3: encoded as (dx2, dy2), calculated as p2 + (p2-p1) + (dx2, dy2)

This works best for roads because they generally continue in their previous direction.

**Next step:**
Test this encoding on a larger dataset and compare results to current encoding.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the current linestring encoding described in the issue, then test the proposed correction-of-prediction encoding on a larger dataset. Compare its size with the current encoding and use those results to determine whether the proposed encoding should be added.

Written by the indexing model from the issue text.

Assessment

Domain
documentation
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.