[Insight-developers] point locator for kd tree

[Luis Ibanez]

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
>
>