here is a brainstorm i did a while ago on the find_pth_nearest ...<br><br>this may not work at all, but it may give some food for thought until i get the visitor patterns going...<br><br><br><div class="gmail_quote">if you were to do it with the find_nearest_if() in libkdtree, I think all you need to do is force kdtree to look for the second nearest point... that is, ignore all the points that are less than the nearest (so far) and accept all the other points.<br>
<br>So I think if you did (for the find 2nd nearest case)... <br><br><br>struct compare_2nd<br>{<br>struct State<br>
{<br>State( Point const& t ) : <br>
target(t), initialised(false)<br>
{}<br>
Point target, p_best, p_second_best;<br>bool initialised;<br>double best, second_best;<br>};<br><br>State * state;<br>compare_2nd(State * s) : state(s) {}<br><br>bool operator()( Point const& n ) const<br>{<br>double dist = distance_between(n,state->target);<br>
<br>/* first look at a point... */<br>if ( ! state->initialised)<br>{<br> state->best = state->second_best = dist;<br> state->p_best = state->p_second_best = n;<br> state->initialised = true;<br> return true;<br>
}<br><br>if (dist < state->best) /* better than our best? */<br>{<br> /* shuffle best to second best */<br> state->second_best = state->best;<br> state->p_second_best = state->p_best;<br> /* we have a new king */<br>
state->best = dist;<br> state->p_best = n;<br> /* pretend we weren't interested so it won't reduce the search space to this point<br> this is the key to making kdtree keep looking for 2nd best */<br>
return false; <br>}<br><br>if (dist < state->second_best) /* better than our second-best? */<br>{<br> state->second_best = dist;<br> state->p_second_best = n;<br>
}<br><br>/* allow 2nd best points and worse to be used for refining the region in libkdtree */<br>
return true;<br>}<br><br>};<br><br><br>i THINK that would work. there are unit tests in kdtree, adapt those to check that this will double-check the correct 2nd best point and test that way.<br><br><br>to run, you would do...<br>
<br>typedef kdtree<etc> Tree;<br>Tree tree(points.begin(),points.end()); // fill the tree<br><br>compare_2nd::State state(target_point); // create the state<br><br>/* run the find with the functor and its state. */<br>
tree.find_nearest_if( target_point, max_range, compare_2nd(&state));<br><br>your_result = state.p_second_best;<br><br><br></div><br>