[Insight-developers] point locator for kd tree

[Nicholas Tustison]

Perfect.  That all makes sense.  I'll put the patch together using the 
second option sometime later tonight (hopefully) and you can take 
a look and make comments.  I plan on pulling your point locator 
class from the IJ article  unless there's another version I should use.


On May 31, 2011, at 6:06 PM, Luis Ibanez wrote:

> 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