Split axis determination

[paulhilbert]

While studying the nanoflann.hpp I stumbled over a piece of code I don't understand. More specifically the middleSplit_ function and in there following lines (1114-1126):

cutfeat = 0;
for (int i=0; i<(DIM>0 ? DIM : dim); ++i) {
    ElementType span = bbox[i].high-bbox[i].low;
    if (span>(1-EPS)*max_span) {
        ElementType min_elem, max_elem;
        computeMinMax(ind, count, cutfeat, min_elem, max_elem);
        ElementType spread = max_elem-min_elem;;
        if (spread>max_spread) {
            cutfeat = i;
	    max_spread = spread;
        }
    }
}

Why does the call to computeMinMax get cutfeat as the split axis? Note that for the first i for which span > (1-eps) * max_span, cutfeat will be set to i. After that however computeMinMax will always return the bounds for cutfeat and therefore the same spread effectively never triggering the innermost if again.

So if I am right cutfeat will always be the first i for which the outermost if is true, not the i maximizing spread. Notice also that in practice this would only lead to inefficient, not wrong results since cutfeat is still maximizing the bounding box spread as a heuristic. The obvious fix being to use i rather than cutfeat in the computeMinMax call.

Maybe I also overlooked something rendering this issue irrelevant. Whatever the case I will be glad for any feedback.

[jlblancoc]

This is why open source is cool... thank you! You are totally right, of course.

I just fixed it, but the strange point is that since your message I've been performing different performance tests (with 2D point clouds in robotics applications, and with 3D random point clouds) and I could not observe any relevant improvement (!).

But the correct algorithm is with your correction, so it's merged.

Cheers.