Finds all closest pairs of overlapping spheres in a point cloud
Given a collection of spheres with equal radii, find all pairwise intersections.
First install using npm:
npm install n-body-pairs
Then use it as follows:
//Load the library, allocate initial data structure for searching in 3-dimensions with initial reserve capacity of 1000 points
var nbp = require("n-body-pairs")(3, 1000)
//Create some points
var points = [
[0, 0, 0],
[1, 0, 0],
[0, 1, 0],
[0, 0, 100000000],
[0, 0, 100000001]
]
//Report all pairs of points which are within 0.6 units of eachother
nbp(points, 0.6, function(i,j,d2) {
console.log("Overlap ("+i+","+j+") Distance=", Math.sqrt(d2), "Positions=", points[i], points[j])
})
//Prints:
//
// Overlap (0,3) Distance= 1 Positions= [ 0, 0, 0 ] [ 0, 0, 1 ]
// Overlap (2,0) Distance= 1 Positions= [ 0, 1, 0 ] [ 0, 0, 0 ]
// Overlap (1,0) Distance= 1 Positions= [ 1, 0, 0 ] [ 0, 0, 0 ]
// Overlap (4,5) Distance= 1 Positions= [ 0, 0, 100000000 ] [ 0, 0, 100000001 ]
//
var nbp = require("n-body-pairs")(dimension, capacity)
Allocates a data structure for performing n-body neighborhood queries.
dimension
is the dimension of the space to search in (default 2)capacity
is the initial size of the data structure to reserve (default 1000)Storage Complexity: O(capacity * 2^dimension)
nbp(points, radius, callback(a,b,d2))
Computes all pairwise overlaps. If the data structure does not have sufficient capacity, it is resized.
points
is an array of pointsradius
is the radius of the overlap querycallback(a,b,d2)
is a function which is called on each pair of overlapping points. If it returns a truthy value, then iteration is terminated. The parameters are as follows:
a
index of first pointb
index of second pointd2
squared distance between a
and b
Time Complexity: O(points.length * dimension * 2^dimension * log(points.length) + number of intersections)
nbp.capacity
Returns the size of the data structure (set to 0 to free memory. Set to change the reserve capacity of the data structure.
(c) 2013 Mikola Lysenko. BSD License