球坐标系角距离(angular distance)下的KD树最近点查询算法

代码地址:https://github.com/mhy12345/angular-kdtree

给定一个坐标集合S,对于若干询问坐标p,分别求出该坐标在坐标集合中最邻近(K临近)的坐标。

KNN算法

问题概述

在K临近算法是一个经典的问题,通常在平面欧几里得坐标系下,我们使用KDTree这个算法来解决,时间复杂度为单次查询O(\sqrt{N})。现在,我们需要将这个KD树算法扩展到球坐标系下,来解决球坐标系中的最近点查询。具体来讲,定义问题为——

通过经度纬度定义球坐标系坐标点,并给定角距离公式 angular_separation 如下,这里的距离即天文学中的天体视角

我们对于每个询问坐标q,查询到与q距离最近的一个集合S中的坐标。

实现思路

与普通KD树相似,使用横纵轴轮流分割的方式建树。即,第一层将所有点按照维度大小对半分,第二层在第一层的基础上按照经度对半分。这样,KD树每一个节点都维护一个球坐标bounding-box内的坐标集合。对于每一次询问,只需要递归对每个子树遍历查询,并通过计算坐标与bounding-box的最短角距离来进行遍历剪枝。

使用样例

C++语言

Python语言

如果你觉得有用,记得点star哦~

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据