Dijkstra 3d path within a mask

[RosieFerr]

I have a 3D numpy array of 0s and 1s, which represents a thresholded mask. I would like to find the shortest path of point A within the mask to point B within the mask. Does the dijkstra 3d algorithm calculate the shortest path within the mask of 1s? Or does use background points with value 0 as a part of the path?

[william-silversmith]

Hi, thanks for writing in! The dijkstra algorithm here regards 0 as background and uses the value of foreground as weights. So if you use all ones, each move will be evenly weighted. However, the diagonals will not be handled specially (e.g. sqrt(2), sqrt(3)) since it is just looking at the field values.

Will

On Thu, May 11, 2023 at 9:01 AM RosieFerr @.***> wrote:

I have a 3D numpy array of 0s and 1s, which represents a thresholded mask. I would like to find the shortest path of point A within the mask to point B within the mask. Does the dijkstra 3d algorithm calculate the shortest path within the mask of 1s? Or does use background points with value 0 as a part of the path?

— Reply to this email directly, view it on GitHub https://github.com/seung-lab/dijkstra3d/issues/38, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATGQSKLTF3IZA6NCKWYTJDXFTPLFANCNFSM6AAAAAAX6DR3KA . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[RosieFerr]

Dear Will,

Thank you for the answer, but my question is still unclear to me: Does the algorithm calculate paths that include the background voxels?

[william-silversmith]

No, background voxels are excluded.

On Thu, May 11, 2023, 10:45 AM RosieFerr @.***> wrote:

Dear Will,

Thank you for the answer, but my question is still unclear to me: Does the algorithm calculate paths that include the background voxels?

— Reply to this email directly, view it on GitHub https://github.com/seung-lab/dijkstra3d/issues/38#issuecomment-1544120025, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATGQSKUGSQE3EWM3HTYHDDXFT3PJANCNFSM6AAAAAAX6DR3KA . You are receiving this because you commented.Message ID: @.***>

[RosieFerr]

Thank you!

[RosieFerr]

Hi William, I have tested your Dijkstra algorithm within my 3D numpy arrays of 0s and 1s however the algorithm still creates paths including the background voxels that have a value of 0. I have tried to increase the background voxel weights to for example 100 000 to avoid them as much as possible, but still if there is no other path possible the algorithm of course choses that voxel anyway. I was wondering if there is a way to make the algorithm completely avoid the background voxels and simply return no path possible if there is no path between two voxels on the foreground, instead of including background voxels as it does now...

[william-silversmith]

Hi Rosie,

My sincere apologies, it's been a while since I used it and forgot how I was using it. There's no concept of a background color in this implementation. However, if you use a floating point volume, you can replace 0 with np.inf and that might do it.

I am considering providing a more simple to use function since this is such a common request.

Will

On Thu, May 25, 2023, 10:19 AM RosieFerr @.***> wrote:

Hi William, I have tested your Dijkstra algorithm within my 3D numpy arrays of 0s and 1s however the algorithm still creates paths including the background voxels that have a value of 0. I have tried to increase the background voxel weights to for example 100 000 to avoid them as much as possible, but still if there is no other path possible the algorithm of course choses that voxel anyway. I was wondering if there is a way to make the algorithm completely avoid the background voxels and simply return no path possible if there is no path between two voxels on the foreground, instead of including background voxels as it does now...

— Reply to this email directly, view it on GitHub https://github.com/seung-lab/dijkstra3d/issues/38#issuecomment-1562995520, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATGQSKXWCZP6PUZRE2EFI3XH5S7HANCNFSM6AAAAAAX6DR3KA . You are receiving this because you commented.Message ID: @.***>

[RosieFerr]

Dear Will,

Thanks for the help!

Regards, Rosaria

[william-silversmith]

Hi Rosaria,

I've released a new version, 1.13.0, that has a (beta!) new function dijkstra.binary_dijkstra that will do what I think you are trying to accomplish. You can see how to use it on the front page.

Let me know if you have any questions.

Will

[RosieFerr]

Thank you! I will try it out in the coming days!

[turtleizzy]

We have discovered this issue when we try to calculate centerline using dijkstra3d, these two path are identical in the number of voxels (=length of path) but significantly different in euclidean arclen, the dark-blue line is generated by dijkstra3d.dijkstra.

I am wondering is it possible to add an optional anisotropy parameter to dijkstra3d.dijkstra function. The expected behavior could be 1) if anisotropy = None, the behavior will be identical to current dijkstra3d.dijkstra 2) if anisotropy is provided, the edge weight will be multiplied with euclidean distance factor ( sx, sy, sz, sqrt(sx**2 + sy**2), ... ) according to the anisotropy parameter.

[turtleizzy]

I have added a pull request for this feature.

[william-silversmith]

I added a test and merged the PR. Thank you so much @turtleizzy !

[william-silversmith]

All good! Thank you for the contribution!

On Tue, Dec 19, 2023, 3:39 AM Izzy Turtle @.***> wrote:

Ahhh sooorryy I’ve been quite busy that days and I completely forgot this issue >_<

— Reply to this email directly, view it on GitHub https://github.com/seung-lab/dijkstra3d/issues/38#issuecomment-1862337421, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATGQSOZCHMAYZKAGTHV7GTYKFHEHAVCNFSM6AAAAAAX6DR3KCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQNRSGMZTONBSGE . You are receiving this because you modified the open/close state.Message ID: @.***>