[Insight-developers] point locator for kd tree

[Luis Ibanez]

Hi Nick,


On Mon, May 30, 2011 at 1:23 PM, Nicholas Tustison <ntustison at gmail.com> wrote:
> Hi Luis,
>
> I don't know if you saw my response to your code review but in case you
> hadn't, I wanted to raise some of the issues I mentioned there.  I really
> don't care what route we go, I just want to put something in place so I can
> potentially submit a couple of point set metrics before the release date.
>
> I had seen your PointLocator2 class with the same functionality that I
> wanted, namely to be able to locate the nearest neighbors of a user-specified
> point within a given point set.  However, there were a couple of issues
> which led me to implement the point set location functionality within the
> point set itself.  Geometric information, in the form of the bounding box,
> is already being computed in the point set as requested by the user so
> adding the kd-tree does not seem incongruous.


Here are some more considerations:

The itkPointSet is in the Core/Common Module
The itkKdTree is in the Numerics/Statistics Module


Currently ITK-Common only depends on

* ITK-VNLInstantiation
* ITK-KWSys


To implement the closest point location in the
itkPointSet directly we would have to move the
KdTree and the KdTreeGenerator to Core/Common.

(your patch currently works because  the Tests in Common
can have additional dependencies beyond the ones of
the ITK-Common module itself. That however will not work
in an application).


...relocating the classes is not impossible...
but it is something to keep in mind...


Implementing the closest point location in a
helper class enable us to put this class out
of Common and out of Statistics (if we want).



> Additionally, you already have the function FindClosestPoint() in the
> point set class, although it isn't implemented properly, and that's very similar
> to wanting the nearest N neighbors.  So if you look at my submission, I
> have
>
> FindClosestPoint()
> FindClosetsNPoints()
> FindPointsWithinRadius()
>
> all based on the kd-tree.
>


Agree.

However, they don't have to be methods of the PointSet itself.

For example, the itkImage doesn't have a function that gives
your the index of pixel with the maximum value or minimum
value.

We implement such services in calculators.

DataObjects should be only "containers of data"


> Also, I believe the code entanglements that you mention is what led me to
> implement the VectorContainerToListSampleAdaptor class which seems a
> much better use of the data then the PointSetToListSampleAdaptor class
> which ignores everything in the point set class except for what is housed in the
> PointSetContainer class which is a VectorContainer type.
>

I certainly agree.

for the purpose of the KdTree we only
need the point coordinates information.

Your adaptor is better suited for this goal.


> So, although what I propose is one possible solution, another solution would
> be to submit the PointSetLocator2 class (with a possible deletion of  the
> FindClosestPoint() function in the PointSet class?).   What are your thoughts
> in favoring one over the other?
>


I would vote for this second option.


Namely:

1) Add the PointSetLocator2 (renamed as PointSetLocator)
    Based on the KdTree.

2) Adopt the use of your new Adaptor, so that the PointSet
    Locator focuses on the point coordinates.

3) Put the computation of the PointSet Bounding box in the
    PointLocator or another helper class.

4) Remove the FindClosestPoint() from the PointSet,
    and make it available in the PointLocator.

    Since the method was never functional in the PointSet,
    this is not a backward compatibility concern.


I'm happy to put such patch together,
or to assist you in doing so.


    Luis