返回资讯中心
外部精选
软件工程
#开发者实时流

开发者开源地球椭球测地线路径快速拦截算法

来源标题:Fast Interception of a Path of Geodesic Segments on the Earth Spheroid

开发者为其开源项目 CoursePointer 提出一种 filter-and-refine 算法,用于快速找出点集对地球椭球上一系列测地线段的拦截位置。该方法结合 Karney 的测地线拦截算法,可得到精确拦截点,实现比 R-tree 更简单,在某些常见场景下可能更高效,代价是增长阶不同。作者表示未找到该方法的既有文献记录。

Hacker News 最新mshroyer2026/11/17 · 今天30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

这里我描述一种快速筛选-精化算法,用于查找一组点与一系列地球测地线段之间的拦截(interception),例如 GPX 文件中的路线与航点之间的拦截。这是我去年为开源项目 CoursePointer 开发的。[1] 将该筛选器与 Karney 的测地线拦截算法 [9] 结合,可以得到精确的拦截点,同时实现起来比 R-tree 更简单——在某些常见用例中可能还更高效,代价是增长阶(order of growth)上的权衡。

我未能找到这种确切方法的其他文献记录,包括请 AI 帮我检索现有技术也没有找到。如果你知道我遗漏的更早描述,请发邮件告诉我,我会更新这篇文章!

给定一条由 WGS84 椭球地球模型上的测地线段序列构成的路径,以及椭球上的一组点,我们如何快速找出这些点中是否有任何一个在一定阈值距离内“拦截”了这条路径?[2]

具体来说,我编写 CoursePointer 是为了将 GPX 路线/轨迹和航点转换为 Garmin FIT 课程文件和课程点。[3] 航点和课程点有不同的语义:航点只是椭球上某个位置的纬度/经度点,它可能位于同一 GPX 文件的路线或轨迹上,也可能不在。而课程点则专门与某个课程相关联——并位于该课程上某个特定距离处。该距离是它 FIT 表示的一部分。

因此,为了生成课程点,我的程序必须回答这个问题:“这条路线是否会经过距该航点例如 35 m 以内的位置?如果是,那发生在整条路线的哪个距离处?”

图 1:一条由多个线段组成的路线,以及一些航点。航点 A 靠近路线,因此应被解释为路线上的一个课程点;航点 B 远离路线,不应被视为课程点。

但我们该如何建模这些线段和航点?对于小范围区域,2D 投影很简单,但作为通用方案,它会引入需要修正的边界情况和畸变。球面地球模型更好,但与椭球之间仍可能相差约 0.5%。[8] 为了精度以及与其他 GIS/GPS 工具的一致性,我更愿意在 WGS84 椭球上进行这些计算。

从椭球上的一个点到一条测地线段的拦截没有闭式解,但存在迭代方法。[9] [10] Karney 的方法(他也在一个 SourceForge 评论中简洁地描述过)是以对拦截点的猜测为中心做球心投影(gnomonic projection),用笛卡尔几何计算新的猜测,并迭代直到猜测收敛。这能给出精确答案——但对 GPX 文件中每一对路线线段和航点都这样做并不是最快的做法。

因此我们需要某种筛选器,用来排除那些我们可以推断必定位于拦截阈值之外的路径线段与点的组合。R-tree 和 k-d-tree 能高效查询附近对象,但它们增加了复杂性,初始化也需要时间,此外矩形包围盒对于任意方向的路段来说并非最优。鉴于我项目更窄的需求,我想我可以做一个更简单的东西——而且对我关心的路线来说,也许还更快?

我主要关心的是从徒步或骑行规划器导出的那类路线,例如 Gaia GPS、Komoot 或 Ride with GPS。我们可以看一条示例路线,了解典型路线线段的尺度。

在 Mathematica 中打开这条示例公路骑行路线,可以看到 2209 条线段(包括一些零长度线段),中位长度为 40 m,平均值为 50 m,最大值为 303 m。更蜿蜒的徒步小径往往会有更短的线段。

图 2:一条真实公路骑行路线的线段长度分布。

这意味着,拥有一个能够对航点到较短线段的距离给出紧致下界的筛选器会很有用,尤其是对短线段。

CoursePointer 的筛选器通过用 WGS84 的弦来近似线段,从而建立这个紧致下界。这大幅减少了程序 O(M⋅N) 部分所需的工作量,其中 M 是线段数,N 是航点数。

我们首先将路线(由一系列路线/轨迹点给出)分割成相邻的点对。(有些路线规划器可能会在路线中包含一些零长度线段,为提高效率我们可以排除它们。)对于每一对点,我们:

我们还将所有航点转换为欧几里得空间。

图 3:线段端点和航点表示为欧几里得空间中的点。它们也可以视为从模型中心延伸出的向量。两个线段端点 𝐒𝟎 和 𝐒𝟏 隐式定义了它们之间的一条弦。

对于我们要比较的每个航点和路线线段,我们可以在欧几里得空间中求出航点到该线段近似弦的距离。我们首先取两个新向量:

图 4:两个新向量 𝐚 和 𝐛,分别由 𝐏 和 𝐒𝟏 减去 𝐒𝟎 得到。

我们想知道 𝐚 到 𝐛 上最近点的距离,如虚线所示:

图 5:𝐚 到 𝐛 的距离及其在 𝐛 上的投影。

人们可能会忍不住先测量 θ,然后计算 ‖𝐚‖sin⁡θ,但这只有在我们已经知道 0≤‖𝐚‖cos⁡θ≤‖𝐛‖ 时才成立。想象一下线段和点的组合中 θ>90∘ 的情况,这会使投影落在路线线段起点之后;另一方面,如果 𝐚 太长或 θ 太小,投影可能延伸到线段终点之外。相反,我们需要计算图中所示的向量 𝐜,它指向弦上的某处(包括其端点),但不会超出它们。

首先,考虑 𝐚 在通过 𝐛 的直线上的无界投影。我们称之为 𝐚𝐩𝐫𝐨𝐣:

利用点积恒等式 𝐚⋅𝐛=‖𝐚‖‖𝐛‖cos⁡θ 和 𝐛⋅𝐛=‖𝐛‖2,这可以改写为:

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →