Infinite loop when inserting more than leafLimit duplicate points

[andreabedini]

Hi there,

thank you for the library. When I try to make an octree from my dataset of points, my program gets stuck and eventually runs out of memory.

After some troubleshoting, I came to the conclusion there is something wrong with the insertion logic. My dataset has many duplicate points in it, and at some point splitBy gets called with more than 16 identical points, at which point it starts looping.

He is a reproducible example:

import Linear.V3
import qualified Data.Octree as O

o = O.fromList $ replicate 17 (V3 1.0 2.0 3.0, ())

I understand the input is somehow patological but we need a way to handle it without crashing :-) I'll think some more about this tomorrow.

[andreabedini]

I have put Octree aside now but the tl;dr is that splitBy' assumes it's always possible to split points while clearly this is not the case when we only have duplicate points. The fromList function seems to be the one in charge of deciding when to split, while perhaps it should be splitBy. Just my 2c.