[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
Octree implementation.
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
1000-100000 objects),
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.
  Best regards
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150823/464744f8/attachment.html>

More information about the Haskell-Cafe mailing list