orthogonal range search with rage max query

[Paul Harris]

I'm not sure if you got a reply, so here is a brief one

On 28/01/2008, Steffen Heyne <heyne at informatik.uni-freiburg.de> wrote:
> Hi,
>
> through wikipedia I've found your implementation of an kd-tree. Thank
> you for your work!
>
> I want to use your class for an (2D-) orthogonal range search, i.e. I
> give two 2D-points and a method should return all points within a given
> rectangle ((x1,y1),(x2,y2)). Which member I have to use for this
> purpose? "find_within_range()"?
>

yeah something like that.   set up a range and pass it to the
function.  i detailed how to do this for a different use-case in a
recent email on this mailing list.

> Second question: is it possible to extend the node's data structure with
> own types and to traverse the tree nodes to manipulate these data? The

manipulate - sometimes i store pointers to the data in the tree.  then
you can const_cast the const away and edit the node.  however, if you
change its location, you'll have to remove and readd it to the tree so
it will be in the right spot.

> problem I have is that I need an efficent access to the maximum within a
> given range, i.e. each point has a certain weight and a query should
> return the point with the maximum weight within a range (range max
> query) (in addition only the maximum of a certain set of "activated"

you could try the visit_* methods.  it'll call your functor for every
node within the range.  then you can write a functor to remember the
node with the maximum weight.

> points within a range). During the insertion of the points one have to
> update a max variable of the nodes to achieve this. Do you have any
> other ideas for a range-max query with a kd-tree?

if you are always looking for something of a certain range, then
maybe you could make it a 3d search, the 3rd dimension being the weight.

then, and i'm not sure if it currently supports this, do a search to
find the Nearest point Within a range.  i think find_nearest() will
allow you to pass it a point (the target) and a range (your search
limit).

then your range would be:
X: the search x range
Y: the search y range
Z: -infinity to +infinity.   actually, from
-numeric_limit<double>::max()   to
+numeric_limit<double>::max()

i think its numeric_limit<> ?  its in <numeric_traits> or something, i
always get that mixed up.


and your target point would be
X: middle of X range
Y: middle of Y range
Z: +numeric_limit<double>:max()

unless your locations are using some very large numbers, then the
distance calc should in theory give you the point with the largest
weight (Z).   the distance component of X and Y should be very small
in comparison to Z, so you'll get the point with the greatest Z
(weight), despite its location in X,Y

that should be faster than just searching in 2D space and checking each node.

see ya
Paul