Majority voting in find_nearest()

[Sylvain Bougerel]

On Thu, Oct 16, 2008 at 7:38 PM, Paul Harris <paulharris at computer.org> wrote:
> Hi Will, Sylvain,
>
> I am not so sure that we can generate an iterator just like that, because
> two nodes that are close to a point may be on two sides of the tree - if the
> target is right on a dividing line (hope thats not too vague to get the
> picture).
>

Hi Paul,

In my opinion, there is no problem to write such an iterator. Think
about it this way:

Each time you do iterator::operator++, it starts a new nearest
neighbor search, except that instead of just being bounded by a max
distance from the root, the search is now also bounded by a min
distance from the current point. It should be really fast, since we
will prune the tree both for min and max.

Consequently: iterator::operator-- would be written the same way. We
can even imagine writing an "inward" operator, that would start from
the point furthest away and iterate to the nearest point.


> I think I emailed the list a while back in response to a query about getting
> the last 4 closest points via find_nearest_if or visit_nearest.  I think the
> only way may be to approach it from that direction...
>
> the basic idea is that the visitor is called as the algorithm steps through
> the tree.  It adjusts the bounds as it goes via the return value (true or
> false - in response to the question "did the visitor just visit a point that
> is closer to the target").
>

Well, I'm not so found of the visitor pattern, cause I have the
feeling the control over the iteration process is more limited than
with an iterator. Well, I might be wrong, but I'd rather work on an
iterator :-)

Sylvain


> 2008/10/16 Sylvain Bougerel <sylvain.bougerel.devel at gmail.com>
>>
>> Hi Willi,
>>
>> I bumped into the same requirement in the past. My personal desire it
>> to implement an iterator on the nearest neighbor that goes outward.
>> With this, you could call i++ until you find the point that correspond
>> to your requirements. I've just started working on this recently, and
>> you might have to wait a bit for a similar feature to come in.
>>
>>
>> At the moment, regrettably, I cannot think of any solution that does
>> not involve modifying the library itself.
>>
>> On Wed, Oct 15, 2008 at 7:06 PM, Willi Richert <w.richert at gmx.net> wrote:
>> > Hi,
>> >
>> > in some situations the same point is inserted with different labels. In
>> > this
>> > case find_nearest returns an arbitrary point of these euqally nearest
>> > points
>> > to the query point.
>> >
>> > However, it would be nice if one could get either all the points that
>> > are
>> > nearest and identical or to have a method that returns the label of the
>> > majority of the (identical) nearest points.
>> >
>> > Would that be feasible with the current libkdtree++ implementation?
>> >
>> > Regards,
>> >
>> > wr
>> >
>> > _______________________________________________
>> > libkdtree-devel mailing list
>> > libkdtree-devel at lists.alioth.debian.org
>> > http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>> >
>> >
>>
>> _______________________________________________
>> libkdtree-devel mailing list
>> libkdtree-devel at lists.alioth.debian.org
>> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>