geoid – Efficient storage and queriying of geographic data
1 Converting to and from Latitude/  Longitude
2 Storing and Retrieving from a SQLite database
3 Generating Test Data
4 API Documentation
5 Waypoint Alignment

geoid – Efficient storage and queriying of geographic data

Alex Harsányi

 (require geoid) package: geoid

The geoid library allows representing latidude/longitude coordinates using 64-bit integers. The integer values are ordered to preseve locality, which means that these IDs can be stored in databases and used to query and efficiently retrieve locations which are in a geographic region.

This library is inspired by the S2 Geometry library, in the sense that the integer IDs are determined in the same way. Until this libary has its own introduction section, you can read S2 Cell Hierarchy to understand how geoids work. What this library calls geoids, are called cells by the S2 libary.

Also, while inspired by the S2 library, this Racket module is an independent implementation that does not generate compatible IDs and does not aim to have the same API and functionality as that library.

1 Converting to and from Latitude/Longitude


(lat-lng->geoid lat lng)  exact-integer?

  lat : real?
  lng : real?
(geoid->lat-lng geoid)  
real? real?
  geoid : exact-integer?
Convert a geographic coordinate (latidude, longitude) to and from a geoid. The returned geoid will be at the highest level of precision (level 0), but geoid->lat-lng will also accept geoids at a lower precision (a level higher than 0).

geoid->lat-lng will return the latitude/longitude coordinates corresponding to the center of the geoid and this will introduce an error in the conversion from latitude/longitude to geoid and back. For geoids at level 0, emprirical testing showed this to be less than 9.75 millimeters, which is sufficient for the type of applications intended for this libary. Note that this error is not constant accross the globe, and 9.75 millimeters is the maximum error seen.


(lat-lng-rect geoid)  
real? real? real? real?
  geoid : exact-integer?
Return the latitude / longitude rectangle which encloses the geoid. The four values returned are: minimum latitude, minimum longitude, maximum latitude, maximum longitude. The bounds are slightly extended, to ensure all leaf geoids are inside the bounding box.

The bounding box encloses the geoid minimally, but geoids and bounding boxes don’t overlap exactly, so the bounding box will always be bigger than then geoid and there will be other geoids which are inside the bounding box, but not in the geoid.

2 Storing and Retrieving from a SQLite database

Convert a geoid into an integer suitable for storage into a SQLite database, or convert an integer stored in the database back into a geoid.

Geoids are unsigned 64 bit values, and more than half of them have the highest bit set. SQLite will store numbers as signed 64 bits and convert unsigned 64 bit numbers greater than the maximum signed 64 bit value to floating point numbers, loosing precision. This means that geoids cannot be stored directly into a SQLite database.

These pair of functions subtract 263 from the geoid (or add that value back) to make sure the value is stored correctly. The ordering of the geoids is preserved, so they can still be used to index geograpic information.

3 Generating Test Data


(random-geoid level #:parent parent)  exact-integer?

  level : exact-integer?
  parent : (or/c exact-integer #f)
Generate a random geoid at the specified level. If parent is specified, the level has to be lower (mode detailed) than the parent and a geoid which is inside the parent will be generated.

This function is intended to generate geoids for unit tests.


(leaf-outline geoid    
  [#:steps steps    
  #:closed? closed?])  (listof exact-integer?)
  geoid : exact-integer?
  steps : (and/c integer? positive?) = 10
  closed? : boolean? = #t
Return a sequence of leaf geoids representing the outline of geoid. This can be used to obtain the outline of a geoid to display on a map.

steps specifies the number of geoids ot put on each side of the rectangle, while closed? specifies if the first geoid should be duplicated as the last element in the list, to close the loop.

As with leaf-corners, geoids are placed in counter-clockwise order, but there is no guarantee about the start corner of the loop.

4 API Documentation

Return the first and last valid integers that represent geoids. All integers between these two numbers are valid geoids, but they can be at different levels. Note that 0 is not a valid geoid.

See geoid-stride to determine the amount to add to a geoid to obtain the next geoid at the same level.

Returns an integer which is one bigger than the largest valid geoid (as returned by last-valid-geoid). The returned value is not a valid geoid.

This can be used to create half-open geoid ranges, for example by leaf-span.


(valid-geoid? geoid)  boolean?

  geoid : exact-integer?
Return true if geoid is a valid geoid. This is the same as testing that the geoid is between first-valid-geoid and last-valid-geoid, but shorter to type.


(geoid-level geoid)  (integer-in 0 30)

  geoid : exact-integer?
Return the level of this geoid – geoids can represent areas at increasing level of detail. The highest resolution is at level 0, and going up, geoids become 4 times bigger at each level. Level 30 is the top level, where the entire Earth surface is divided into 6 faces.

Geoids produced by lat-lng->geoid are at level 0 and you can use enclosing-geoid to obtain a geoid at a higher level.


(geoid-stride geoid)  exact-integer?

  geoid : exact-integer?
Return the integer step that must be added to a geoid to obtain another geoid at the same level. This can be used to generate valid geoids in sequence. Note that the geoids at the highest resolution (level 2) have a stride of 2, so you cannot simply incremenet geoids.


(enclosing-geoid geoid level)  exact-integer?

  geoid : exact-integer?
  level : (integer-in 0 30)
Return the geoid at level that contains the specified geoid. This function can be used to obtain the geoid at a lower resolution which contains a given point or geoid.

Return the four geoids at the lower level into which the current geoid can be split. An error is raised, if the supplied geoid is a leaf geoid, at level 0.

The returned geoids are not in any particular order.


(leaf-geoid? geoid)  boolean?

  geoid : exact-integer?
Return #t if geoid is a geoid at level 0 (highest level of detail). This is equivalent to checking if geoid-level returns 0, but faster.


(leaf-span geoid)  
exact-integer? exact-integer?
  geoid : exact-integer?
Returns the half-open geoid range that are valid geoids contained in geoid. The first value is the smallest leaf geoid which is inside this geoid, the second value is either the smallest leaf geoid which is not part of geoid, or the sentinel-geoid, whichever is smaller.

All geoids which are inside this geoid, regardless of level, are contained in the returned number range, so this range can be used to check if any geoid is inside this one.

The leaf span returned by this function can be used to search for geoids in an SQL query, however, if you do that, make sure you adjust them, as noted in the SQLite section above.


(leaf-span* geoids)

  (list-of (cons/c exact-integer? exact-integer?))
  geoids : (list-of exact-integer?)
Return a list of half open geoid ranges which define the valid geoids contained in all the geoids from geoids list. This is equivalent to calling leaf-span for each individual geoid in geoids and merging all the adjacent ranges together.

This function can be used to create more efficient queries if a geoid is inside a list of geoids. A common use case is to use adjacent-geoids to obtain the neighbours of a geoid and using leaf-span* to find the ranges for all geoids in this neighbourhood.


(contains-geoid? this-geoid other-geoid)  boolean?

  this-geoid : exact-integer?
  other-geoid : exact-integer?
Return true if the other-geoid is geographically inside this-geoid.

This a convenient function, but if you need to check lots of geoids, this will be slower than obtainging the leaf-span of this-geoid and checking of other geoids are inside the returned range.

Return the four leaf geoids which represent the corners of this geoid. The corners are returned in couter-clockwise order, but there is no guarante of which one is first (i.e. there is no guarantee that the list will start with the top-left corner)


(adjacent-geoids geoid)  (list-of exact-integer?)

  geoid : exact-integer?
Return the adjacent geoids which border geoid. The returned geoids will be at the same level as geoids.

Normally, 8 geoids are returned, but only 7 are returned if geoid is in a corner of a face and only 4 geoids if it is a face level geoid.


(approximate-area-for-geoid geoid)  real?

  geoid : exact-integer?
(approximate-area-for-level level)  real?
  level : (between/c 0 30)
Return the approximate area, in square meters, of geoid or level. The area is calculated by dividing the earth surface by the number of geoids at that level and it is approximate because there will be geoids with smaller area and larger area than this at each level.

These functions can be used to get a general idea of the surface covered by a geoid.


(distance-between-geoids g1 g2)  real?

  g1 : exact-integer?
  g2 : exact-integer?
Return the distance, in meters, on the Earth surface between the center of geoids g1 and g2. For leaf geoids this is a good appoximation for the distance between the locations represented by these geoids, since the size of a leaf geoid is approximately 8.5 millimeters.


(distance-from-geoid g)  (-> exact-integer? real?)

  g : exact-integer?
Return a function which can be used to calculate the distance on the Earth surface between the geoid g and another geoid. The returned function will accept a single geoid as an argument and will return the distance between that geoid and g.

If you need to calculate the distance between a single geoid and several others, it might be faster to use this function to construct a "distance function".

5 Waypoint Alignment


(waypoint-alignment-cost path1 path2)  real?

  path1 : (vectorof exact-integer?)
  path2 : (vectorof exact-integer?)
Return a number representing how similar path1 is to path2. The smaller the number the more similar the two paths are. Ideally, the cost of a path against itself should be zero, but, due to floating point errors, this is a small positive number.

This function returns the Dynamic Time Warping cost of the two paths.

NOTE: the alignment cost will depend not only on how close the two paths are to each other, but also on the length of the paths, so it is up to you to decide how to interpret the resulting cost and determine if the two paths are the same or not.