Why does QgsSpatialIndex.nearestNeighbor(point, 1) sometimes return 2 lines?

Question

I'm trying to get the closest line to a point using PyQGIS in a plugin. The active code file is this: http://pastebin.com/TDzmsKVM

When I request the closest line (only 1)

nearestIds = self.spIndex.nearestNeighbor(self.feat2.geometry().centroid().asPoint(),1)

I sometimes get a list with two lines and the first one is not the closest but as far as I can see the second one is. Why is this?

Does QgsSpatialIndex use only boundingboxes for lines? How do I get the real closest line always, not only most of the time?

Answer 1

The nearest points can return more then one according to the underlying code. RTree.cc (a underlaying file)

539  // report all nearest neighbors with equal greatest distances.
540  // (neighbors can be more than k, if many happen to have the same greatest distance).

The greatest distance I guess should be the smallest. But other then that it sounds like a truncation in the tree precision.

Answer 2

QgsSpatialIndex only knows about the bounding boxes. You will need to get the actual geometries to find the real nearest neighbour. I have done it like this in the NNJoin plugin:

# Find a nearest index entry to myPoint (QgsPoint)
nearestindexid = self.spIndex.nearestNeighbor(myPoint, 1)[0]
# Get the feature in the layer (self.myvectorlayer) that is
# being indexed by self.spIndex
nnfeature = self.myvectorlayer.getFeatures(QgsFeatureRequest(nearestindexid)).next()
# Get the distance to this feature (it is not necessarily the nearest one)
mindistance = myPoint.distance(nnfeature.geometry())
px = myPoint.x()
py = myPoint.y()
# Get all the features that may be closer to the point than nnfeature
closefeatureids = self.spIndex.intersects(QgsRectangle(px - mindistance,
                   py - mindistance, px + mindistance, py + mindistance))
for closefeatureid in closefeatureids:
    closefeature = self.myvectorlayer.getFeatures(QgsFeatureRequest(closefeatureid)).next()
    thisdistance = myPoint.distance(closefeature.geometry())
    if thisdistance < mindistance:
        mindistance = thisdistance
        nnfeature = closefeature
        if mindistance == 0:
             break