NodeJS library for geographic localization using k-gon clouds in fixed distance.
Many applications answer questions like:
- How many ATMs are within a 5 mile radius from where I am?
- How many banks can I walk to within a mile?
- How many Chipotle restaurants are near my hotel?
These questions are structured as how many Xs are near Y.
Or, given a fixed distance from some query coordinate, give me all locations.
brainiac structure solves this problem with an augmented BST based on
k, referring to the k-Gon clouds placed "about" every location coordinate, and
d, the fixed distance.
brainiac structure uses the haversine formula to compute distance between coordinates.
var b = ;var brain = b;// Add coordinatesbrain;brain;brain;brain;brain;brain;brain;brain;brain;brain;// Query against the structurevar query = brain// Return queries are of the following formatquery ===latitude: 41643112longitude: -88001369borders: ......
brainiac structure to some simple method of iterating through all location coordinates and computing distance to some query coordinate.
brainiac structure can be written as:
Search an augmented binary search tree for a longitude interval. Search some augmented binary search tree for a latitude interval over some longitude interval. For all members of a node's data set within that tree: Compare haversine distance to some query coordinate. If less than d, add to return list. Return return list.
Or, in a time complexity analysis as follows:
O(logn) + O(logn) + O(m)
m is the average density of these created "interval squares".