How to searching for in kdtree when dynamic elements are considered

Sylvain Bougerel sylvain.bougerel.devel at gmail.com
Tue Nov 17 03:05:27 UTC 2009


On Tue, Nov 17, 2009 at 1:10 AM, jsl n <jsantam.hm at hotmail.com> wrote:
> Hi,
>
> This is the procedure, but, what happen if the fixed image (the one that the
> kdtree stores) is also transformed each iteration? should I build a new
> kdtree
> each iteration? I need to know if there is an efficient solution for this
> dynamic
> situations where all the image points (of the fixed image) are transformed
> in
> the same way.
>
> Thanks in advance.
>

Hi Jsl (?),

(The following comments are agnostic with regard to the type of
objects stored in the tree)

Some transformations result in a violation of the invariant, others do not.

Uniform translations or scallings of all point in the tree along a
linear vector or with constant factor (be it in affine or euclidean
space) will not break the invariant. So you can lock the kd-tree (if
necessary), perform the translation or scalling of all points in the
tree, unlock the kd-tree (if necessary), and continue your program.

Uniform rotations, on the contrary, do not have this property (neither
in affine nor in euclidean space), they *always* break the invariant
(unless they are null rotation, of course) in the kd-tree. Therefore,
upon a rotation, you have no choice but to rebuild your kd-tree
entirely.

Others transformation, such as perspectives transform or matrix
transform may or may not break the invariant in the tree. Unless you
are able to determine that a particular transformation is, in fact, a
composition of more elementary translations or scallings, you will
have to rebuild the tree every time you have such transform on your
image.

Cheers,
Sylvain



More information about the libkdtree-devel mailing list