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

[Sylvain B. <syl...@gm...>]

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


On Sun, Feb 26, 2017 at 8:19 PM Jakub Klinkovský <j....@gm...> wrote:

> Hi,
>
> I'm looking for a library that would allow to do an in-order traversal of a
> balanced k-d tree. This is useful in applications where an ordering of
> points
> preserving spatial locality is necessary, see e.g. this comment on SO:
> http://stackoverflow.com/a/499230/4180822
>
> The Spatial library is by far the closest match I could find as it
> provides the
> "ordered_iterator" and "mapping_iterator" iterators, which sort the values
> along
> a specified dimension. (By the way, what is the difference between these
> two
> iterators?) It seems that the container's "iterator" and "const_iterator"
> do
> some simple traversal of the tree, but is it in-order? Or have I missed
> some
> iterator for in-order traversal?
>
> I'd appreciate any help with this or other suggestions.
>
> Thanks,
> Jakub Klinkovský
>
> ------------------------------------------------------------------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, SlashDot.org! http://sdm.link/slashdot
> _______________________________________________
> Spatial-main mailing list
> Spa...@li...
> https://lists.sourceforge.net/lists/listinfo/spatial-main
>