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

[Michael Steele]

Michael,

In case your interested in another example, there's also a quadtree in the
"gloss-algorithms" [1] package.

[1]: http://hackage.haskell.org/package/gloss-algorithms

On Thu, Aug 20, 2015 at 1:41 PM, Tikhon Jelvis <tikhon at jelv.is> wrote:

> Are you already familiar with lenses? From a glance at the code you
> linked, it will be hard to understand what's going on unless you are.
>
> Personally, my advice is to implement a simple, limited quadtree yourself.
> The first part of "Functional Programming with QuadTrees"[1] is basically a
> tutorial on quadtrees with code in Miranda—eminently readable for
> Haskellers. That's where I would start: write up the code from their
> examples in Haskell, play around with it and add an extra function or two
> to understand what's going on.
>
> Once you have an intuition for the underlying ideas, you can expand it to
> octtrees and more complex operations.
>
> [1]:
> http://conal.net/papers/warren-burton/Functional%20Programming%20and%20Quadtrees.pdf
>
> On Thu, Aug 20, 2015 at 1:30 PM, Michael Litchard <michael at schmong.org>
> wrote:
>
>> It looks like Octree is what I want if I can solve a particular problem.
>> First let me articulate what I am looking for.
>>
>> (1) Objects in 3-d space with no spatial extent. Collision is determined
>> by two objects occupying the same point.'
>>
>> (2) Efficient insert-delete-update
>>
>> #2 seems to be the problem. I found this library, thankfully. I believe
>> it's exactly what I am looking for, but for quadtrees.
>>
>> https://github.com/AshleyMoni/QuadTree
>>
>> I'm a little overwhelmed as this is a new data structure for me. I
>> believe if I can grok what is going on in this library, I can take these
>> ideas and extend them to the octree. I'm referring specifically to this
>> module
>>
>>
>> https://github.com/AshleyMoni/QuadTree/blob/master/Data/QuadTree/Internal.hs
>>
>> And these functions
>>
>> setLocation :: Eq a => Location -> a -> QuadTree a -> QuadTree a
>> setLocation = set . atLocation
>>
>> atLocation (Having difficulty cutting and pasting this to mail.)
>>
>> I'd like to be able to visualize how the tree is being compressed, it may
>> help to be able to see what happens to the tree when it's not compressed.
>>
>> Does anyone have a pointer or advice in how to break this library down in
>> parts to help me grok, in a way that will help me extend to octree?
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>
>>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>


-- 
-- Michael Steele
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150820/b512cdbb/attachment.html>