Monday, March 23, 2015

3d - Algorithm to see if two voxels are interconnected


I'm looking for a good algorithms for the following problem: Given a 3D grid of voxels (which may be either empty or filled), if I pick two non-adjacent voxels, I want to know if they are connected to each other by other voxels.


For example (to illustrate the situation in 2D), where # is a filled square:


  1 2 3
a # # #
b # #
c # # #


If I pick a3 and c3, I want to determine as quickly as possible if they they are connected; if there is a path between a3 and c3 through filled pixels. (The real situation is in a 3D voxel grid, of course.)


I've looked at floodfill algorithms and path finding algorithms, but I'm not sure which to choose. Both do unneccesary work: Flood fill tries to fill all voxels, but this is not needed. Path-finding algorithms are usually concerned with finding the shortest path, which is also not necessary. I only need to know if there is a path.


What algorithm should I be using?


Edit: based on the comments, I think should add the following: the content of the voxels are not known in advance, and also, the algorithm is needed to detect if removal (emptying) of a voxel would cause the group of voxels to break into two or more smaller groups.



Answer



A* would work just fine. Path finding is what you want, finding the shortest path is just as fast (or faster) than finding any path at all. In this situation A* is likely the most suitable given you have a start and end point. this means you have the added heuristic to speed up the search.


With A* typically the first path you find is the shortest, so it's not doing extra work after it's already found a path.


enter image description here


For some optimizations, check out my answer here.


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...