[Haskell-cafe] octree implementation - followup to "How to model outer space for a MUD"

[Michal J Gajda]

Hi,

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.
http://hackage.haskell.org/package/Octree

Funny part, is that implementation may be easier to read than algo
description I read first time:
http://hackage.haskell.org/package/Octree-0.5.4.2/docs/src/Data-Octree-Internal.html
.

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
balanced.
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
    Michal
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150823/464744f8/attachment.html>