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)?
8
-
Are you trying to create a planar graph?user3386109– user33861092021-10-19 23:40:32 +00:00Commented Oct 19, 2021 at 23:40
-
This question has nothing to do with graphs. It is about 3D Euclidean distances.Lior Kogan– Lior Kogan2021-10-20 06:50:27 +00:00Commented Oct 20, 2021 at 6:50
-
This reminds me of 3D collision detection. If so start with bounding boxes.Guy Coder– Guy Coder2021-10-20 11:00:26 +00:00Commented Oct 20, 2021 at 11:00
-
@GuyCoder good point, this is the same problem as collision detection. Recursive boxing methods like quadtree can do this in N Log(N).mTesseracted– mTesseracted2021-10-20 13:07:20 +00:00Commented Oct 20, 2021 at 13:07
-
1@mTesseracted Since you already have an upvoted answer to the question as written, if you have a related question with extra requirements please ask it separately.kaya3– kaya32021-10-20 15:00:43 +00:00Commented Oct 20, 2021 at 15:00
|
Show 3 more comments
1 Answer
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.
4 Comments
mTesseracted
Do you know of any collision detection algorithms that have O(N) average case performance where the average case is each object only collides with a finite number of other objects?
kaya3
@mTesseracted If those are the constraints of your problem then you should have included them in the question. Please don't wait until someone has done the work to answer the question as you wrote it and then change what you're asking for.
Lior Kogan
Since the OP asks for a 3D solution, an octree is more appropriate.
ravenspoint
@LiorKogan Good point.