[Haskell-cafe] octree implementation - followup to "How to model outer space for a MUD"
Michal J Gajda
mgajda at mimuw.edu.pl
Sun Aug 23 05:09:32 UTC 2015
And if you search for Octree on Hackage, you would have also found my
It does not do re-balancing, but in this type of application you talk about
it may not be needed.
Funny part, is that implementation may be easier to read than algo
description I read first time:
It worked perfectly for my use cases (checking for collisions of
but (just in case) the initial creation from list structure make the octree
Note that balanced octree is supposed to be much faster than KD-tree, and
may be also faster than R-tree in memory, since it is very shallow
structure - log_8 between 10k and 1m changes only from below 5 to below 7!
I was also very happy with its cache behaviour, although in theory R-tree
could be better.
I am also extremely interested in making sure that Haskell has a good
choice of multidimensional metric data structures, so I am closely
following maintenance of kd-tree, Ashley´s, and Gloss´ quadtrees.
And if you really want to have re-balancing, please contact me on my email.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe