static-range-query
Fast n-dimensional orthogonal range searches for static point sets
npm install static-range-query
Want to see pretty graphs? Log in now!
6 | downloads in the last week |
17 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.0.2 last updated a year ago |
License | MIT |
Keywords | range, static, search, orthogonal, box, n-dimension, 2d, 3d, geometry, math, query |
Repository | git://github.com/mikolalysenko/static-range-query.git (git) |
Dependencies | bfs-tree-layout, inorder-tree-layout, lower-bound, upper-bound, bit-twiddle |
Dependents | mikolalysenko-hoarders |
static-range-query
Given a collection of points in n-dimensional space, preprocesses these points so that orthogonal range queries can be computed efficiently. Internally, this library is built using range trees.
Example
var preprocess = require("static-range-query")
//Generate 10000 4D points
var D = 4, N = 10000
var points = new Array(N)
for(var i=0; i<N; ++i) {
var p = new Array(D)
for(var j=0; j<N; ++j) {
p[j] = Math.random() * 1000
}
points[i] = p
}
//Construct query data structure
var rangeQuery = preprocess(points)
//Now execute a range query!
rangeQuery([2, 5, 0.25, -10], [10, 50, 5, 30], function(i) {
console.log("In range: ", i , points[i])
})
Install
npm install static-range-query
API
var rangeQuery = require("static-range-query")(points)
Preprocesses the point set so that orthogonal range queries can be evaluated efficiently.
points
is an array of points (each point is represented as a tuple of D numbers)
Returns A rangeSearch()
function (see below) which evaluates range queries on the point set.
Time Complexity O(points.length * log(points.length)^points[0].length)
Space Complexity O(points.length * log(points.length)^points[0].length)
Notes Internally, this function builds a range tree and binds it to the query method
rangeQuery(lo, hi, cb(index))
Evaluates a range query on the point set.
lo
is a lower bound on the bounding rectangle to queryhi
is an upper bound on the bounding rectangle to querycb
is a callback which gets called once per each point in the range with the index of a point.
Time Complexity O(log(points.length)^points[0].length + k)
where k
is the number of points processed in the range.
Note The points are visited in lexicographic order
Other Note You can terminate the search early by returning true
from cb
, for example:
rangeQuery([0, 0, 0], [100, 100, 100], function(i) {
if(i === 100) {
console.log("found it!")
return true
}
//Continue processing ....
return false
})
Credits
(c) 2013 Mikola Lysenko. MIT License