Given a set of vertices with 3D spatial coordinates of size N and a maximum connection distance d, is there an efficient algorithm to find all the undirected edges connecting the vertices with distance less than d; loops are not considered. A naive approach would simply loop on all possible pairs, requiring N(N-1)/2 distance calculations. Is there an existing algorithm for finding all possible edges with scaling complexity less than O(N^2)?
1 Answers
Given a set of vertices with 3D spatial coordinates of size N and a maximum connection distance d, is there an efficient algorithm to find all the undirected edges connecting the vertices with distance less than d
Yes. Insert the vertex locations into a octree, then for each vertex search for vertices closer than d.
For the equivalent problem in 2D you can use a quadtree.
You can find C++ quadtree code at https://github.com/JamesBremner/quadtree
Example Usage:
// construct vector of random points
std::vector<cPoint> vp = random(count);
// construct quadtree of points
cCell quadtree(cPoint(0, 0), 100);
for (auto &p : vp)
quadtree.insert(p);
// quadtree search
// returns vector of all points within 2 by 2 box around point 10,10
auto fp = quadtree.find(cCell(cPoint(10, 10), 2));
Note that if the exact Euclidean distance is important, then post-processing is required to remove any points in the red regions.
For more details, check out the German tv mini-series 'Billion Dollar Code' available on Netflix.
Related