findNearestOption does not find point within a distance in particular situations

[jaceksokol]

Andriy, first of all, I really admire the work you've done on this library. The performance is amazing.

I found one issue which is related to the algorithm of searching nearest points.
I have a tree constructed with nodeCapacity = 4, distance calculator is SphericalEarth. The tree is represented as below:

RTreeNode(-26.05,21.64581,-17.80165,27.84296)
    RTreeNode(-26.05,21.64581,-17.80165,25.91667)
      RTreeNode(-21.69785,21.64581,-18.36536,23.41667)
        RTreeEntry(-21.69785,21.64581,-21.69785,21.64581,BWGNZ)
        RTreeEntry(-18.36536,21.84219,-18.36536,21.84219,BWSWX)
        RTreeEntry(-21.66667,22.05,-21.66667,22.05,BWSUN)
        RTreeEntry(-19.98333,23.41667,-19.98333,23.41667,BWMUB)
      RTreeNode(-26.05,21.77962,-23.9988,25.67728)
        RTreeEntry(-23.9988,21.77962,-23.9988,21.77962,BWHUK)
        RTreeEntry(-26.05,22.45,-26.05,22.45,BWTBY)
        RTreeEntry(-24.60167,24.72806,-24.60167,24.72806,BWJWA)
        RTreeEntry(-25.22435,25.67728,-25.22435,25.67728,BWLOQ)
      RTreeNode(-21.41494,23.75201,-17.80165,25.59263)
        RTreeEntry(-19.16422,23.75201,-19.16422,23.75201,BWKHW)
        RTreeEntry(-17.80165,25.16024,-17.80165,25.16024,BWBBK)
        RTreeEntry(-21.3115,25.37642,-21.3115,25.37642,BWORP)
        RTreeEntry(-21.41494,25.59263,-21.41494,25.59263,BWLET)
      RTreeNode(-24.87158,25.86556,-24.62694,25.91667)
        RTreeEntry(-24.62694,25.86556,-24.62694,25.86556,BWMGS)
        RTreeEntry(-24.87158,25.86989,-24.87158,25.86989,BWRSA)
        RTreeEntry(-24.65451,25.90859,-24.65451,25.90859,BWGBE)
        RTreeEntry(-24.66667,25.91667,-24.66667,25.91667,BWGAB)
    RTreeNode(-23.10275,26.71077,-21.17,27.84296)
      RTreeNode(-23.10275,26.71077,-21.97895,27.84296)
        RTreeEntry(-22.38754,26.71077,-22.38754,26.71077,BWSER)
        RTreeEntry(-23.10275,26.83411,-23.10275,26.83411,BWMAH)
        RTreeEntry(-22.54605,27.12507,-22.54605,27.12507,BWPAL)
        RTreeEntry(-21.97895,27.84296,-21.97895,27.84296,BWPKW)
      RTreeNode(-21.17,27.50778,-21.17,27.50778)
        RTreeEntry(-21.17,27.50778,-21.17,27.50778,BWFRW)

When searching for the nearest point to -24.65527, 25.91904 with the maxDist parameter set to 50 km, I am expecting the tree to return Some(RTreeEntry(-24.65451,25.90859,-24.65451,25.90859,BWGBE)). However, the method returns None. If I maxDist is set to infinity all works fine.

I did some investigation and the situation can be represented graphically like below:

A is the point that I'm looking for the nearest objects, and B is the expected closest object.

[plokhotnyuk]

@jaceksokol Hi, Jacek! Thanks for trying the library!
It was a nasty porting error that sat for a long time due to a lack of proper tests with rectangle entries defined for spherical geometry.

[jaceksokol]

Thank you, Andriy, for such a quick reaction 🙇

[plokhotnyuk]

@jaceksokol You are welcome!
Please peak up a release with the fix - it is already available on the Maven Central: https://github.com/plokhotnyuk/rtree2d/releases/tag/v0.11.8