[x3d-public] efficient json for 2d grid data

Thu May 26 11:39:57 PDT 2016

I think I settled on a json structure for a tiled elevation grid which came
out quite a bit different than originally anticipated.

Since json is text based, I am using base 36 for numbering to compress a
bit. So in addition to numerical digits, the letters a-z are also used. JS
has builtin functions to convert from and to base 36. The fundamental unit
is micro-degrees which corresponds to about 110km/1000000 = 0.11m.
Combined, this means a 6 digit coordinate can resolve down to 11 cm.

Tiles are 36 by 36 cells. A tile can be sparse, eg. not all cell values
need to be specified. However, in order to make it easy for a tile consumer
to fill in gaps, at least one value in a tile needs to (should) be provided.

The size of a tile depends on the zoom level. Zoom level 5 tiles are 36
microdegrees long on each side. Zoom level 4 tiles are 36x36 zoom level 5
tiles large, eg. each side is 36x36 = 1296 microdegrees long, eg. about
140m. Zoom level 3 tiles are about 5 km long on each side.

Here is a table of tile sizes:

z | edge | in meters
5 | 36   | 4
4 | 1296 | 143
3 | 46 656| 5132
2 |1 679 616|185km
1 |60 466 176| 6651km

The size of each cell in a tile is 1/36 of the tile size (or the size the
tile of the next higher zoom level).

The json structure is

/z/lon/lat/cell_lon/cell_lat

z is the zoom factor
lon/lat is the location of the tile shortened to z digits
cell_lon/cell_lat is the position of an elevation within the tile

A level 2 tile would be
/2/23/2

Its location is from 230000,20000 to 23z000,2z000 in microdegrees. This
comes out to be
parseInt(230000,36)/1000000 = 125.9712 degrees E, 3.359232 N to
127.60416 E, 4.992192 N

A query or lookup like heights[2][32][2] returns all populated cells in the
36x36 tile. The consumer then can easily reconstruct the position of each
reported cell.

A path like
/2/23/2/8/7 returns a single datum. It looks up the elevation at
238000, 27000 in microdegrees.

Reversely, the procedure to extract an elevation at a given location
(144.5678, 44.1245) is:

1) decide on resolution(zoom level), depends on json data base, say 3 (143m
cell resolution).
2) convert to microdegrees
lon =longitude * 1e6
3) truncate to zoomlevel-1 and convert to base 36
lon = Math.round(lon/Math.pow(36,z-1))*Math.pow(36,z-1).toString(36)
(2e2l00, q9r00)
3) determine tile to use according to zoom level:
/3/2e2/q9/
4) lookup elevation in tile
/3/2e2/q9/l/r
5) if successful done, if not get whole tile /3/2e2/q9
and traverse for nearest neighbour or inverse distance weighted average
possibly get surrounding tiles as well for more sophisticated interpolation.
The advantage of a tiled grid would be to first get the whole tile to avoid
connecting twice.
Or to get the whole tile set by just /3/

It would be nice to attach meta information to tile sets and perhaps single
tiles.

I uploaded such a tiled elevation json database of California with zoom
levels up to 3 (but only 1km resolution, eg. 3 tiles are sparse) to

https://heights-database.firebaseio.com/

with public read access for experimentation.

-Andreas

On Wed, May 25, 2016 at 4:33 PM, Andreas Plesch <andreasplesch at gmail.com>
wrote:

> Hi,
>
> given the json x3d activity and availability of firebase as performant,
> easy to use, online json database engine, I started to think about a json
> structure for tiled elevation grid data.
>
> As an example dataset I am using a global 1km (30 arcsecond) resolution
> dataset, cut down to the continental U.S. or California.
>
> The simplest structure is an untiled, flat list like this:
> { "lon1:lat1" : elev1,
>   "lon2:lat2" : elev2,
>  ... }
> I transformed the dataset to this structure, and uploaded the json to
> firebase. It works as expected, eg. you can query the database but you need
> to know the exact keys, or array of keys for an area. It is actually pretty
> fast.
>
> This where tiling comes in. My favorite idea sofar is to use the digits of
> lon.,lat. as hierarchical keys, with an addtional key "h" for the actual
> data. For a three by three digit, one degree grid, It would look like this:
>
> {"0:0" : {"h": h00_ave,
>           "0:0" : { "h": h00_ave,
>                     "0:0" : { h: elev },
>                     "0:1" : { h: elev }, ...
>                     "9:9" : { h: elev }
>                   },
>           "0:1" : { "h": h01_ave,
>                     "0:0" : { h: elev },
>                     "0:1" : { h: elev }, ...
>                     "9:9" : { h: elev }
>                   }, ...
>           "9:9" : { "h": h99_ave,
>                     "0:0" : { h: elev },
>                     "0:1" : { h: elev }, ...
>                     "9:9" : { h: elev }
>                   }
>   "0:1" : {"h": h01_ave, //100N does not actually exist
>           "0:0" : { ... }, ...
>           "9:9" : { ... }
>          }, ...
>  "9:9" : { ... }
> }
>
> The elev. data are actual elevation, the h??_ave value are representative
> (average) elevation for a complete tile.
>
> A json path to an elevation at 123E longitude and 40N latitude looks like
> this:
> /1:0/2:4/3:0/h
> A json path to all elevations in the area between 120 and 129E longitude
> and 40 and 49N latitude is:
> /1:0/2:4/
> This path refers to an object:
> { "h": 356, //average elevation in this area
>   "0:0" : {"h": 344 }, // ...
>   "9:9" : {"h": 377 }
> }
>
> which has all grid point elevations in this 10x10 degree tile.
> So 129E,049N has an elevation of 377.
>
> Hm, there is an issue. A json path
> /2:0/
> would refer to an area between 200E,000N to 299E,099N and would require
> loading all of the subtree although we are only interested in the h??_ave
> values.
>
> -Andreas
>
> Thinking out loud: This probably means putting the tile level first in the
> hierarchy like in slippy maps. The tile level would be the number of
> significant digits.
> /3/0:0  //average for 000:000 to 099:099
> /2/0:0  //average for 000:000 to 009:009
> /2/1:0  //average for 010:000 to 019:009
> /2/ // all averages in 10x10 cells
> /1/222:89 // data in 222:89
> /1/ // all data in 1x1 cells
> looks better ...
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> --
> Andreas Plesch
> 39 Barbara Rd.
> Waltham, MA 02453
>

-- 
Andreas Plesch
39 Barbara Rd.
Waltham, MA 02453
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://web3d.org/pipermail/x3d-public_web3d.org/attachments/20160526/c900c278/attachment-0001.html>