我有一个表示道路网络的图形数据结构(节点是道路中的点/交叉点,边缘是道路). Node对象具有与之关联的纬度和经度.

我正在使用Accord的KDTree类来查找给定GPS坐标的附近节点.由于Accord似乎没有将Haversine距离作为内置距离函数(我错了吗？),我定义了自己的自定义距离函数,并将其作为额外参数传递给KDTree.FromData()方法,如下：

        var nodes = graph.Nodes;
        //Initialize KD-tree with distance function defined as the cartesian approximate distance (in meters) 
        Func<double[], double[], double> distanceFunc = (x, y) => DistanceFunctions.ApproximateDistance(x,y);
        kdTreeOfNodes = KDTree.FromData<Node>(nodes.Select(x => new double[] { x.Value.Latitude, x.Value.Longitude }).ToArray(), nodes.ToArray(), distanceFunc);

请注意,’ApproximateDistance’在单独的类中定义为静态方法,并且是更正确的Haversine距离的笛卡尔近似值.

我试图超越最后一行时遇到异常.在这一行中,我传入数据以放入KDTree(即lat / lon数组的数组)以及相关节点,再加上我的自定义距离函数.看起来这个FromData构造函数实际上(出于某种原因？)调用我的ApproximateDistance函数,数组[1]和[1]作为两个输入参数,显然引发了一个异常,因为这个方法需要两个二维数组.

我不知道为什么这个构造函数调用我的ApproximateDistance函数(特别是这些奇怪的参数),似乎无法找到使用调试器…

解决方法:

K-d-tree在搜索期间不使用点对点距离,直到它们到达实际数据点.

相反,它是与分裂平面的一维偏差.这里可以是纬度或经度.

这就是为什么k-d-tree比Minkowski规范支持更少的原因.