mapbox / mapbox/geobuf

Lossy encoding of high-precision coordinates

Open
#96 9 comments 0 reactions 0 assignees View on GitHub
format design question
Dominant language
JavaScript
Stars
1k
Forks
86
PR merge metrics
No merged PRs in 30d

Description

I think the assertion in the README that the geobuf encoding is "lossless" is a bit ... _enthusiastic_.

Specifically, I've found these issues:
* maxPrecision is set to `1e6` and never changes
* numbers are rounded to double precision during JSON.parse
* the scaling factor to convert these decimal coordinates to sint64 and back again may lose data thanks to scale vs. precision

So, the first point: calling the codec "lossless", I would expect a roundtrip GeoJSON -> pbf -> GeoJSON would leave the input unchanged. Adding `t.same(geobuf.decode(pbf), geojson);` to the high-precision test will demonstrate the problem:

```
+++ found
--- wanted
"geometry": {
"coordinates": [
[
[
- 5425435.73308157
- 2012689.6354403072
+ 5425435.733082
+ 2012689.63544
]
[
- 5425333.066045091
- 2012658.8061882276
+ 5425333.066045
+ 2012658.806188
]
[
- 5425324.357915714
- 2012693.5183856217
+ 5425324.357916
+ 2012693.518386
]
[
- 5425426.519392735
- 2012720.2386971796
+ 5425426.519393
+ 2012720.238697
]
[
- 5425435.73308157
- 2012689.6354403072
+ 5425435.733082
+ 2012689.63544
]
]
]
"type": "Polygon"
```

This can be worked around by changing `encode.js` to set `maxPrecision = `. Ideally of course this would be determined based on the precision of the input data, or at least taking it as a parameter on the encode function.

However, this exposes the second issue: writing the decoded GeoJSON to a file does not (necessarily) match the input text, if the precision of the input exceeds the maxPrecision.

This is not really avoidable, I think - neither JSON nor GeoJSON specify precision, and it's not _incorrect_ per se. It's reasonable to say that "GeoJSON" is the parsed object representation and not the input string. But I would say it's important to emphasise that point as a caveat to the "lossless" statement.

Finally, and as an artifact of the first and second points, the third issue: Around or exceeding the boundary of the precision of a double (i.e. 1e16) it is possible to encounter an issue where we end up with two coordinates, each of which has the same appropriate precision (i.e. 16 significant figures), but with the geometry as a whole not safely encodable by geobuf. Take a Point:

```
[
0.01541290815946613,
154.1290815946613
]
```

The result of a round trip test on this with `maxPrecision = 1e16` (the actual max precision):

```
+++ found
--- wanted
"features": [
{
"geometry": {
"coordinates": [
- 0.01541290815946613
+ 0.0154129081594661
154.1290815946613
]
"type": "Point"
}
```

If we take instead of precision the scale of the numbers, i.e. the maximum number of digits after the decimal place (`maxPrecision = 1e17`/`e = 17`), the problem becomes that the larger element (154...) now overflows the size of sint64 and pbf complains: `Given varint doesn't fit into 10 bytes`.

Unfortunately I can't see any obvious solution to this. If geobuf insists on the scale * sint64 approach for coordinates, high-precision numbers are going to be tricky to encode losslessly.

A possible solution would be a more complex protobuf encoding similar to Java's BigDecimal, which uses BigInteger as the arbitrary precision integer value - this doesn't have the limitation of sint64, but a more appropriate protobuf type would have to be found (maybe just bytes with a well-defined size? or even string?).

Contributor guide

Open the contributing guide

Research direction

Start with encode.js and the high-precision test, then reproduce the GeoJSON-to-PBF-to-GeoJSON round trips described in the issue. Trace maxPrecision, JSON.parse, coordinate scaling, and sint64 limits; the work is done when the supported precision and lossless-encoding caveats are resolved or clearly covered by tests and documentation.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
data
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.