Data source and storage computing

takeaway

After reading this article, you will know:

1. Coordinate projection of Internet map; 2. How is the data source of Internet map organized? 3. How to calculate tile ID on 3D map; 4. What are the optimization schemes for data source processing

Coordinate system and projection

Geographic coordinate system generally refers to the coordinate system composed of longitude, latitude and altitude, which can mark any position on the earth. The geographic coordinate system is three-dimensional, and if we want to display it on a map or on a screen, we need to convert it to two dimensions, and that’s called projection. Common projections are EPSG: 4326 and EPSG:3857 Mercator.

EPSG: 4326 is the WGS84 coordinate system, which is spherical coordinate system. Horizontal line is equal latitude line, vertical line is equal longitude line, and the unit is degree. The zero longitude line is called the prime meridian, the longitude through Greenwich, England, minus west and plus east. The zero latitude line is the equator, minus south and positive north. The image below shows an unrolled 2d world map in WGS84 coordinate system, which is common in scenarios using GeoJSON data sources, but is not a projection of a map we see on the Internet.Common maps on the Internet are based onMercator projectionIs a variant of the prototype.

The Mercator projection was created by the Dutch cartographer Mercator in 1569. It imagined that the earth was enclosed in a hollow cylinder, and the equator was tangent to the cylinder. Then it imagined that there was a lamp at the center of the earth, projected the figure on the sphere onto the cylinder, and then unfolded the cylinder. This is a map of the world produced by the Mercator projection with zero standard parallels (the equator). (Above from Encyclopedia)

Mercator Projection for Internet Use, also known as Web Mercator (EPSG: 3785), which was first proposed by Google. Based on Mercator projection, the WGS84 coordinate system is projected to the square. The formula is as follows: the latitude of the projection is between [-85°, 85°]. The scope of the x axis and y axis are in [20037508.3427892, 20037508.3427892].

Code for reference:

Github.com/Leaflet/Lea…

Var SphericalMercator = {R: earthRadius, MAX_LATITUDE: 85.0511287798, project: function (latlng) { var d = Math.PI / 180, max = this.MAX_LATITUDE, lat = Math.max(Math.min(max, latlng.lat), -max), sin = Math.sin(lat * d); return new Point( this.R * latlng.lng * d, this.R * Math.log((1 + sin) / (1 - sin)) / 2 ); }, unproject: function (point) { var d = 180 / Math.PI; return new LatLng( (2 * Math.atan(Math.exp(point.y / this.R)) - (Math.PI / 2)) * d, point.x * d / this.R); }, bounds: (function () { var d = earthRadius * Math.PI; return new Bounds([-d, -d], [d, d]); }}) ()Copy the code

In addition, the commonly used domestic coordinate system and Mars coordinate system, Baidu coordinate system.

Mutual coordinate conversion of common map coordinate systems:

Blog.csdn.net/sinat_41838…

Knowing the projection and coordinate system to use, the next step is to understand what kind of data source you need.

Data source structure

A common source of data on the Internet is the tile pyramid model, which is a multi-resolution hierarchical model. From the bottom of the tile pyramid to the top, the resolution is lower and lower, but the geographical range of the representation is the same (from encyclopedia). The advantage of this is that you can display different geographical details at different map levels. Through the projection of the world map as a plane, the data source is cut and indexed by pyramid cutting at different zoom levels of the map, so as to better control the details displayed.

Knowing the organization of the data source, the next step is to calculate the index of tiles that the current window needs to load in relation to the camera and scene.

Tile data source loaded

Since the camera position and Angle in 3D map will affect the window range, the camera cone, camera coordinates and rotation need to be taken into account in the calculation.

1. First, the trapezoidal range of the window is calculated by the intersection of the camera’s viewing cone and XOZ plane, which is also the visible area.
2. Then calculate the trapezoidal bounding box range.
3. According to the coordinates of the bounding box range, the pyramid tiles with four corners are calculated, and the bounding box range of tile pyramid is obtained.
4. Calculates the index of the current window tile according to the tile pyramid bounding box.

Based on the current map level, window range, and window size, you can infer the x, Y, and Z of the current grid tiles that need to be loaded.

The calculation of intersection between camera cone and plane can be referred to as follows:

/ * * * ray and plane intersection * @ param {*} ray {u} p0, * @ param plane {x} {p1, n} * @returns vec3 */ const rayPlaneIntersection = function(ray, plane) { const t = (new Vector3().copy(plane.n).dot(plane.p1) - new Vector3().copy(plane.n).dot(ray.p0)) / new Vector3().copy(plane.n).dot(ray.u) const p = new Vector3().copy(ray.p0).add(new Vector3().copy(ray.u).multiplyScalar(t)) @param {*} camera * @param {*} plane {p1, n} * @returns array [vec3,vec3,vec3,vec3] */ const cameraPlaneIntersection = function (camera, plane = { p1: New Vector3(0,0,0), n: new Vector3(0, 1, 0) }) { const D = 1000 const H = D * Math.tan(camera.fov / 2 * Math.PI / 180) const W = H * camera.aspect const FROM = camera.position const MAT = camera.matrix const bounds = [[W, H, -D], [-W, H, -D], [-W, -H, -D], [W, -H, -D]] return bounds.map((loc, index) => { const dir = new Vector3(... loc).applyMatrix4(MAT).sub(FROM) const ray = { p0: FROM, u: dir } return rayPlaneIntersection(ray, plane) }) }Copy the code

The XOZ plane of WebGL coordinate system is divided into grids loaded with tiles. The number of tiles in x and Y directions of z layer is POW (2, Z-1) respectively. By adjusting the distance between the camera and XOZ plane of tile, map tiles can be loaded according to different resolutions. After loading, fill the map tiles into the different grids.

Taking the tile numbering [0,0, z] in the upper left corner as an example, according to the Web Mercator transformation formula, the tile numbering X and y of LATLNG at any latitude and longitude at z level can be calculated as follows:

Const mapWidth = mapHeight = 20037508.3427892 * 2 function getTileNum (latLNG, z) { const tileSize = mapWidth / Math.pow(2, z - 1) const mercator = SphericalMercator.project(latlng) const x = Math.floor((mapWidth / 2 + mercator.x) / tileSize) const y = Math.floor((mapHeight / 2 - mercator.y) / tileSize) return { x, y } }Copy the code

The loading logic of vector tiles is similar to that of raster tiles, except that the pyramid segmentation is slightly different for different data source providers, and the calculation method is also adapted to local conditions.

Vector tile data source processing

Requests for raster tiles, usually with texture maps can be used directly, but vector tiles need to generate graphics according to the data.

The vector tile data source we use requests binary data. First of all, we need to obtain geographical information such as land, sea, functional surface, road, POI, road name and building surface in the data source through the first-layer data parsing according to the parsing rules negotiated with the server. Next comes the second level of data processing, which computes the tile data into vertices, faces, normal and UVs used for rendering. Finally, according to the style file, generate the material texture and so on, pass it to the Tile, add it to the Layer, complete a Tile loading, parsing, assembly, rendering.

LRU Cache

During parsing, the Tile is cached at the first level using the LRU (least recently used) caching mechanism. After the Source calculates the Tile ID, the Tile is first searched from the TileCache, and the TileCache is updated after the Tile is computed.

 class LRUCache {
  constructor (max, onRemove) {
    this.max = max
    this.onRemove = onRemove
    this.reset()
  }
  add (key, data) {
    if (this.has(key)) {
      this.order.splice(this.order.indexOf(key), 1)
      this.data[key] = data
      this.order.push(key)
    } else {
      this.data[key] = data
      this.order.push(key)

      if (this.order.length > this.max) {
        const removedData = this.getAndRemove(this.order[0])
        if (removedData) this.onRemove(removedData)
      }
    }
    return this
  }
  ...
}
Copy the code

The code can refer to Mapbox’s TileCache:

Github.com/mapbox/mapb…