Re: [Spatial] In-order traversal of the k-d tree

[Jakub K. <j....@gm...>]

Hi,

indeed, point_multiset<>::iterator is exactly what I've been looking for! Thank
you for the great examples and quick response.

Jakub

On 26.02.17 at 13:17 (UTC+0000), Sylvain Bougerel wrote:
> Hello Jakub,
> 
> I'm not sure I understand exactly but it seems you want to map
> N-dimensional data onto 1 dimension.
> 
> In spatial, there are 3 iterators that will do in-order traversal and
> provide some sort of mapping as a result. I will break them down below, I
> hope it helps.
> 
> 1) point_multiset<>:iterator, box_multiset<>::iterator, etc..
> The basic container's iterator will traverse the tree in-order, from
> left-most to right-most, with complete disregard for the invariant. So
> basically, considering a balanced 1D kdtree (thus looking like a normal
> tree):
> 
>                 4
>           /             \
>      2                     6
>   /     \                /      \
> 1      3              5       7
> 
> => iterating yields: 1, 2, 3, 4, 5, 6, 7
> 
> 2) mapping_iterator<>
> This iterator walks through all nodes as if they had been stored in a
> standard tree over a single dimension (of your choice). Using another tree
> as an example, but this time with 2 dimensions items (dimension ordering
> alternates with each depth):
> 
>                     (4, 1)                            ---- order against
> dimension 0
>              /                   \
>        (2, 4)                 (6, 5)               ----- order against
> dimension 1
>       /       \                 /        \
> (1, 2)   (3, 7)      (5, 3)      (7, 6)
> 
> => mapping iterator against dimension 0 yields: (1, 2), (2, 4), (3, 7), (4,
> 1), (5, 2), (6, 5), (7, 6)
> => mapping iterator against dimension 1 yields: (4, 1), (1, 2), (5, 3), (2,
> 4), (6, 5), (7, 6), (3, 7)
> 
> 3) ordered_iterator<>
> This iterator provides total ordering, in all dimension, such that if the
> same values are inserted into different trees, no matter in which order and
> how they are balanced, the iterator always yields results in the same
> order. With the following tree:
> 
>                     (2, 1)                            ---- order against
> dimension 0
>              /                   \
>        (1, 4)                 (2, 5)               ----- order against
> dimension 1
>       /       \                 /        \
> (1, 2)   (3, 7)      (2, 3)      (3, 6)
> 
> => ordered iterator yields: (1, 2), (1, 4), (2, 1), (2, 3), (2, 5), (3, 6),
> (3, 7)
> 
> 4) Final words,
> if you are looking for an ordering method that preserves locality, I think
> you really are just looking at the first iterator. The other tree are not
> meant to preserve locality, while the container's iterator will preserve
> the order in which the tree has placed each values.
> 
> I hope I was able to help you.
> 
> Regards,
> Sylvain