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

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

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ý