[Insight-developers] point locator for kd tree

[Nicholas Tustison]

Thanks Luis.  Fortunately, that's the version with which I started.  I added
a little error checking.  I added a couple functions to augment the
Search() functions already defined in the class.  I also fitted it to use
the PointsContainer as opposed to the PointSet.  The template 
parameters mirror the BoundingBox class which I thought was  a good 
model.  Currently, I'm finishing the last of the debugging.  The bounding
box was fairly entrenched within the Mesh object and its derivatives and
so that took some time to modify.


On Jun 1, 2011, at 3:30 PM, Luis Ibanez wrote:

> Hi Nick,
> 
> The most recent version of the code is in
> the NAMIC Sandbox:
> 
> http://svn.na-mic.org/NAMICSandBox/trunk/QuadEdgeMeshRigidRegistration/Source/
> 
> Wen Li (University of Iowa) made many improvements
> in the code, after the initial papers were submitted to
> the Insight Journal.
> 
> 
> 
>      Luis
> 
> 
> -----------
> On Tue, May 31, 2011 at 6:13 PM, Nicholas Tustison <ntustison at gmail.com> wrote:
>> 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
>> 
>>