c# - 具有自定义距离功能的 Accord KDTree

Question

我有一个表示道路网络的图形数据结构(节点是道路中的点/交叉点，边缘是道路)。 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 的数据(即纬度/经度数组的数组)以及关联的节点，以及我的自定义距离函数。似乎这个 FromData 构造函数实际上(出于某种原因？)调用了我的 ApproximateDistance 函数，将数组 [1] 和 [1] 作为两个输入参数，显然会引发异常，因为此方法需要两个二维数组。

我不知道为什么这个构造函数正在调用我的 ApproximateDistance 函数(尤其是使用这些奇怪的参数)，并且似乎无法使用调试器找到答案...

Answer 1

K-d-trees 在搜索期间不使用点到点距离，直到它们到达实际数据点。

相反，它是与 split 平面的一维偏差。此处将是纬度或经度。

这就是为什么 k-d-tree 只支持 Minkowski 范数的原因。