There should be a Kd-tree to search spot neighbors.
Closed this issue · 7 comments
This is important for performance (e.g. GUI responsivity: we need to quickly retrieve the spot closest to a click location).
This is tricky, because we allow for incremental model changes. The Kd-tree cannot be recomputed for each single change, otherwise the performance will degrade quickly, which is not the desired effect. A system to cache changes must be implemented, which is another issue.
all done
@tpietzsch Links please?
@ctrueden https://github.com/fiji/TrackMate3/tree/master/src/main/java/net/trackmate/kdtree is the KDTree
https://github.com/fiji/TrackMate3/tree/master/src/main/java/net/trackmate/spatial is the search building on top of KDTree plus changes, in particular https://github.com/fiji/TrackMate3/blob/master/src/main/java/net/trackmate/spatial/SpatialIndexData.java
@tpietzsch Thanks!
I didn't know that you were following TrackMate3.
Only very casually, unfortunately.
How come TrackMate3 needs a KDTree when ImgLib2 already has one? Different interfaces/frameworks/etc.?
There are quite a few KDTrees in this world. Weka has one. And so does ThunderSTORM though that one is lifted from Java ML.
This KDTree has the same interfaces as imglib2's (or rather the searches on it have). The difference is the objects that are stored in it. TrackMate3 is heavily based on PoolObjects (conceptually similar to imglib2 types; stored in Pools mapping to primitive arrays, similar to imglib2 Imgs but always 1D and can grow dynamically). This KDTree plays nice with them. It also stores its nodes as PoolObjects avoiding creating many Objects as imglib2 KDTree (and presumably weka and ThunderSTORM) does. But algorithms for building and searching the tree are pretty much the same.