mourner / Geokdbush
Licence: isc
The fastest spatial index for geographic locations in JavaScript
Stars: ✭ 251
Programming Languages
javascript
184084 projects - #8 most used programming language
Projects that are alternatives of or similar to Geokdbush
Polysnap
A work in progress polygon operations library with integer snap-rounding
Stars: ✭ 14 (-94.42%)
Mutual labels: algorithm, computational-geometry, fast
Delaunator
An incredibly fast JavaScript library for Delaunay triangulation of 2D points
Stars: ✭ 1,641 (+553.78%)
Mutual labels: algorithm, computational-geometry, fast
Kdbush
A fast static index for 2D points
Stars: ✭ 412 (+64.14%)
Mutual labels: algorithm, computational-geometry, fast
Delaunator Cpp
A really fast C++ library for Delaunay triangulation of 2D points
Stars: ✭ 244 (-2.79%)
Mutual labels: algorithm, computational-geometry
Ahocorasickdoublearraytrie
An extremely fast implementation of Aho Corasick algorithm based on Double Array Trie.
Stars: ✭ 695 (+176.89%)
Mutual labels: algorithm, fast
Turf
A modular geospatial engine written in JavaScript
Stars: ✭ 6,659 (+2552.99%)
Mutual labels: algorithm, computational-geometry
Earcut
The fastest and smallest JavaScript polygon triangulation library for your WebGL apps
Stars: ✭ 1,359 (+441.43%)
Mutual labels: algorithm, computational-geometry
Flatbush
A very fast static spatial index for 2D points and rectangles in JavaScript
Stars: ✭ 1,031 (+310.76%)
Mutual labels: algorithm, computational-geometry
Skeleton Tracing
A new algorithm for retrieving topological skeleton as a set of polylines from binary images
Stars: ✭ 241 (-3.98%)
Mutual labels: algorithm, computational-geometry
Turf Swift
A Swift language port of Turf.js.
Stars: ✭ 123 (-51%)
Mutual labels: algorithm, computational-geometry
Xseries
Library for cross-version Minecraft Bukkit support and various efficient API methods.
Stars: ✭ 109 (-56.57%)
Mutual labels: algorithm, fast
Data structure and algorithms library
A collection of classical algorithms and data-structures implementation in C++ for coding interview and competitive programming
Stars: ✭ 133 (-47.01%)
Mutual labels: algorithm, computational-geometry
Supercluster
A very fast geospatial point clustering library for browsers and Node.
Stars: ✭ 1,246 (+396.41%)
Mutual labels: algorithm, computational-geometry
Rbush
RBush — a high-performance JavaScript R-tree-based 2D spatial index for points and rectangles
Stars: ✭ 1,881 (+649.4%)
Mutual labels: algorithm, computational-geometry
Cavaliercontours
2D polyline library for offsetting, combining, etc.
Stars: ✭ 135 (-46.22%)
Mutual labels: algorithm, computational-geometry
Greinerhormann
Greiner-Hormann polygon clipping algorithm. Does AND, OR, XOR. Plays nicely with Leaflet. Handles non-convex polygons and multiple clipping areas. ~3kb footprint, no dependencies
Stars: ✭ 176 (-29.88%)
Mutual labels: algorithm, computational-geometry
Awesome Algorithm Books
📚 awesome algorithm books I've collected 【不定期更新】 搜集整理的算法书籍(经典算法、ML/DL算法、面试算法、比赛算法等)
Stars: ✭ 245 (-2.39%)
Mutual labels: algorithm
Bombardier
Fast cross-platform HTTP benchmarking tool written in Go
Stars: ✭ 2,952 (+1076.1%)
Mutual labels: fast
Projects
A list of awesome open source projects Vladimir Agafonkin is involved in.
Stars: ✭ 250 (-0.4%)
Mutual labels: computational-geometry
geokdbush
A geographic extension for kdbush, the fastest static spatial index for points in JavaScript.
It implements fast nearest neighbors queries for locations on Earth, taking Earth curvature and date line wrapping into account. Inspired by sphere-knn, but uses a different algorithm.
Example
var kdbush = require('kdbush');
var geokdbush = require('geokdbush');
var index = kdbush(points, (p) => p.lon, (p) => p.lat);
var nearest = geokdbush.around(index, -119.7051, 34.4363, 1000);
API
geokdbush.around(index, longitude, latitude[, maxResults, maxDistance, filterFn])
Returns an array of the closest points from a given location in order of increasing distance.
-
index
: kdbush index. -
longitude
: query point longitude. -
latitude
: query point latitude. -
maxResults
: (optional) maximum number of points to return (Infinity
by default). -
maxDistance
: (optional) maximum distance in kilometers to search within (Infinity
by default). -
filterFn
: (optional) a function to filter the results with.
geokdbush.distance(longitude1, latitude1, longitude2, latitude2)
Returns great circle distance between two locations in kilometers.
Performance
This library is incredibly fast.
The results below were obtained with npm run bench
(Node v7.7.2, Macbook Pro 15 mid-2012).
benchmark | geokdbush | sphere-knn | naive |
---|---|---|---|
index 138398 points | 69ms | 967ms | n/a |
query 1000 closest | 4ms | 4ms | 155ms |
query 50000 closest | 31ms | 368ms | 155ms |
query all 138398 | 80ms | 29.7s | 155ms |
1000 queries of 1 | 55ms | 165ms | 18.4s |
Note that the project description data, including the texts, logos, images, and/or trademarks,
for each open source project belongs to its rightful owner.
If you wish to add or remove any projects, please contact us at [email protected].