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

Andreas Plesch andreasplesch at gmail.com
Mon Jun 6 16:26:29 PDT 2016


Hi Mike,

I admit that the convenience of just using firebase (up to 1GB data) was a
main motivation to look into tiled json elevation format. Json is
convenient because it can be easily digested on a web page.

But it would not be very useful if the format would be tied to firebase. So
I was glad to see that json is well supported by the nosql databases:

https://en.wikipedia.org/wiki/Document-oriented_database

most of which are opensource. I did not try any but it could be pretty
straightforward to set up one such as mongodb. I would not be surprised if
there are some free cloud offerings as well to try out, sort of similar to
firebase but without the  broadcasting.

After learning how to produce and digest the 36x36 tiles, I found that they
tend to be too small, and require too many connections to firebase to cover
a reasonable area. This may not be a problem if you run your own server.
Also, the jumps between zoom levels may be too large but I am not sure
about that.

So I did fall back to the  256x256 tiles used for slippy maps, with the
same spherical mercator based power of two hierarchy, this time base64
encoded. It took me while to figure out how to use gdal to generate the
tiles but I did. However, 65536 points take up a lot of memory on a web
page. GPUs can handle it, even mobile, but javascript is inefficient and
the size of the json itself at  and data store is problematic, perhaps only
on mobile. I tried some things with typed arrays which helps but in the end
I do want to get into fiddling for performance too much.

I can put scripts and workflows on github for both the 36x36 tiles and the
256x256 tiles.

Andreas







On Mon, Jun 6, 2016 at 12:04 PM, Mike McCann <mccann at mbari.org> wrote:

> Hello Andreas,
>
> This indexing scheme appears to be a nice design; using base 36 is clever.
>
> I'm currently working with a 5 cm grid of ocean bathymetry, so an 11 cm
> resolution tiling solution is "close enough" for this use case.
>
> I tried examining your example at https://heights-database.firebaseio.com/
> but am getting an "error completing the request" message.
>
> Are there suitable locally-hosted open source json database solutions?
>
> -Mike
>
> --
> Mike McCann
> Software Engineer
> Monterey Bay Aquarium Research Institute
> 7700 Sandholdt Road
> Moss Landing, CA 95039-9644
> Voice: 831.775.1769  Fax: 831.775.1736 http://www.mbari.org
>
> On May 26, 2016, at 11:39 AM, Andreas Plesch <andreasplesch at gmail.com>
> wrote:
>
> 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
> _______________________________________________
> geospatial mailing list
> geospatial at web3d.org
> http://web3d.org/mailman/listinfo/geospatial_web3d.org
>
>
>


-- 
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/20160606/c6faaa74/attachment-0001.html>


More information about the x3d-public mailing list