Application service

Geographic inverse coding

Reference: How to design and implement an address resolution service? Extended thinking:

  1. If open source OSM vector data is imported, how to compare the wrong vector data?
  2. Geohash geocoding (i.e. grid scheme) is adopted, and the idea of effective grid in this paper is applied. Since the inside of a grid may be above the administrative boundary (i.e. across administrative regions), how to plan the fine granularity of a grid?

Geographical fence

Geo-fencing algorithm analytical ray method to determine whether the point extends on the polygon

  1. Use r-tree index.

    1.1. Make an R-tree index for the geo-fence to narrow down the traversal range; 1.2. Traverse the fence and determine the point on the polygon. 1.3. Make r-tree index for the fence boundary, and finally make accurate intersection judgment for the edges after rough screening of R-tree.

  2. Java R tree implementation?

The index

A hash index

Fast and convenient index positioning, the time complexity is O(1) equivalent judgment query does not provide the range query index number should not be large

  • Geohash: Converts a latitude and longitude information into a string encoding that can be sorted and compared.

    • Features:

    A Geohash represents a rectangular region. The longer the length, the higher the accuracy.

    • Defect:

    The location points at the cube boundary points are close but belong to two different Geohash encodings. You can solve this problem by searching for the eight squares around the current square, increasing the query volume.

Index of the tree

  • R tree: Starting from the leaf node, the space is framed with the smallest rectangle, and the more the node goes up, the more space is enclosed, so as to divide the space.

    • Features:

    You can avoid the full convenience index of the Geohash and narrow down the traversal

tool

Redis GEO

API

  • Geoadd: Increases the coordinates of a geographic location.
  • Geopos: Obtain the coordinates of a geographic location
  • Geohash: Gets the geohash value for a geographical location.

Calculate distance:

  • Geodist: Gets the distance between two geographic locations.

Range search:

  • Georadius: Obtains a set of geographic locations within a specified range based on the given geographic location coordinates.

  • Georadiusbymember: Gets a collection of geographic locations within a specified range based on a given geographic location.

    Optional parameters:

    1. WITHCOORD: Pass the WITHCOORD argument, and the result will be returned with the latitude and longitude of the matching position.
    2. WITHDIST: Pass in the WITHDIST argument, and the result is returned with the distance from the matched location to the given geographic location.
    3. ASC | DESC: the default result is unordered, incoming ASC to sort from near to far, incoming DESC is ordered from far to near.
    4. WITHHASH: Pass the WITHHASH argument, and the result will be returned with the hash value of the matching position.
    5. COUNT COUNT: Pass in the COUNT argument to return a specified number of results.

    Ex: Find someone nearby

    def pin(user, longitude, latitude):
    """Record the geographical location of the user. """
    GEOADD('user-location-set', longitude, latitude, user)

def find_nearby(user, n):
    """Returns all other users within n kilometers of the specified user. """
    return GEORADIUSBYMEMBER('user-location-set', user, n, unit='km')
Copy the code

Spatial database

Selection: PostgreSQL, TSDB, MySQL, Elasticsearch

  • Trajectory tracking
  • Scope of the search
  • Spatial object relationship judgment

Open source mapping service OpenStreetMap

Data on territory and borders are not very accurate. The metadata parsing step is complex.

  • National vector data download
  • Administrative vector data download
  • Nominatim: Open source reverse geocoding service
  • Osmosis: parses OSM map data and supports data import into a Postgresql database

reference

  • Spatial Indexes: Why do we need spatial indexes
  • Spatial index: 2
  • Geohash distance estimation
  • Spatial index – Spatial index usage report for each database
  • Comparative Analysis of LBS Data Services (I)