[x3d-public] [geospatial] efficient json for 2d grid data
Mike McCann
mccann at mbari.org
Mon Jun 6 09:04:26 PDT 2016
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://web3d.org/pipermail/x3d-public_web3d.org/attachments/20160606/f2f2d7e2/attachment-0001.html>
More information about the x3d-public
mailing list