NSDT工具推荐： Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 可编程3D场景编辑器 - REVIT导出3D模型插件 - 3D模型语义搜索引擎 - AI模型在线查看 - Three.js虚拟轴心开发包 - 3D模型在线减面 - STL模型在线切割 - 3D道路快速建模
测地线计算是许多地理空间应用的重要组成部分。 示例包括查找两个位置之间的距离、道路长度、路段方向、多边形面积或距离道路最近的点。
在 Mapbox，我们依靠这些计算来处理来自 SDK 的遥测数据，以便我们可以推断出未绘制地图的街道、道路速度、转弯车道、转弯限制以及卫星图像更新优先级的区域。
我们通常使用 Turf 进行这些计算——它是一个简单、快速、模块化的 JavaScript 库，用于地理空间分析。 然而，遥测数据量与日俱增，处理数据的计算挑战也越来越大。 我们在此过程中所能发挥的每一点性能都会得到回报。
为了优化处理，我构建了 cheap Ruler，这是一个 JavaScript 库，用于在城市规模上进行超快速测地线计算。 它不是 Turf 的替代品——它只实现了一部分方法，有一定的局限性，并且仅适用于性能敏感的应用程序。 但在合适的情况下，它可以比使用传统方法快 100 倍。 让我们探讨一下它是如何工作的。
1、测量距离
为了获得平面上两点的距离，我们使用毕达哥拉斯定理：
这不适用于地球上的位置，因为纬度和经度值不会直接映射到距离单位。 如果你站在其中一根极点附近，360 度的经度可能等于几英里，而在赤道上，同样的 360 度将等于 24,900 英里。
其次，地球不是一个平坦的地方——它是球形的！ 幸运的是，数学家找到了一种测量球体距离的方法 - 首先使用球面余弦定律，然后使用 Turf 和大多数地理应用程序中使用的半正弦公式对此进行改进。
不幸的是，地球甚至不是一个球体——它是一个扁椭球体。 因此，半正矢公式可能导致高达 0.5% 的误差。 为了解决这个问题，Thaddeus Vincenty 开发了一个非常复杂的公式，精确度高达 0.5 毫米，使其成为所有严肃科学目的的终极测地线公式。
这两个公式都依赖于许多三角计算，这些计算的计算成本很高。 我们怎样才能避免它们？
2、欧几里得测地线近似
我们需要的大多数对性能敏感的测量都是在城市街区范围内进行的——在遥测中，我们通常测量长达几十英里的距离，而不是数千英里。 对于这样的小距离，我们可以假装地球是平的，并避免大多数复杂的计算，而不会造成明显的精度损失。
为了近似两个纬度之间的距离（距离的“垂直”部分），我们可以将其按比例缩放到子午线的长度（约 12,430 英里），因为它对于任何经度都大致相同：
对于经度差异，纬线的长度（360 度圆）取决于其纬度，从赤道长度（24,901 英里）开始，并以纬度的余弦进行缩放：
然后我们可以将这两个公式与毕达哥拉斯定理结合起来，对两个位置之间的距离进行欧几里得近似，并使用中间的纬度进行经度校正：
生成的公式仅包含一次三角函数调用，这使其比三角函数较多的半正弦公式快得多。
但还有一个考虑因素。 假设我们正在特定的城市区域（例如在缩放 14 的图块内）进行计算。 坐标纬度的余弦在小区域内不会有太大变化，因此我们可以使用相同的经度校正乘数来进行所有这些计算，而不会造成明显的精度损失。 因此，我们对一个面积计算一次余弦，然后完全避免三角计算，从而带来巨大的加速。
对于具有 OpenStreetMap 道路的典型缩放 14 图块的简单基准，使用此近似值计算道路长度比使用 Turf 线距离计算道路长度快 30 倍。
3、提高逼近精度
根据定义，这种近似方法不如传统方法精确。 但到底有多不精确呢？
我编写了一个小脚本来测量这一点，下面的表格显示了上述欧几里得近似值与各种距离（以英里为单位）和纬度的精确文森蒂公式之间的误差范围：
正如你所看到的，近似数千公里的距离并不是一个好主意。 但如果你测量几百以内的东西，误差就非常小——低于 0.5%。
现在让我们看看半正弦公式的误差（不依赖于距离）：
如果你仅测量几百英里以内的距离，则平坦地球近似的误差仅比半正弦公式稍大，该公式适用于大多数应用。
但更重要的是，有一种方法可以使其更加精确，同时保持相同的性能，即使用 FCC 为投影到平面的椭球地球规定的公式：
它与之前描述的方法非常相似，只是我们使用纬度和经度的系数。 而且，我们可以使用切比雪夫的方法来计算角度倍数的余弦，将余弦计算的次数从五次减少到一次。 我们来看看错误：
对于几百英里以下的值，此方法比半正弦公式更快、更精确。
4、认识一下Cheap Ruler
我采用了上面的近似方法，并将其扩展到 Turf 中可用的大多数测量方法。 结果是一个名为 Cheap-ruler 的 JavaScript 模块。
以下是它的功能以及相对于 Turf 的加速（在 Node v6 上运行这些基准测试）的简短列表：
distance：距离，快约 31 倍bearing：快约 3.6 倍destination：目的地，约快 7.2 倍lineDistance：线距离，快约 31 倍area：面积，快约 3.4 倍along：快约 31 倍pointOnLine：快约 78 倍lineSlice：大约快 60 倍
此外，我还实现了几个实用函数，这些函数不直接镜像 Turf 模块，而是非常快速地近似通常通过 Turf 调用组合完成的常见任务：
lineSliceAlong：沿线的给定距离之间对线进行切片； 比turf.lineSlice(turf.along(...快 285 倍bufferPoint：给定缓冲距离，在点周围创建边界框； 比使用两个对角线turf.destination调用创建边界框快约 260 倍bufferBBox：快约 260 倍（同样）insideBBox：比turf.inside(turf.point(p), turf.bboxPolygon(bbox))快约 19 倍
用法是这样的 - 首先创建一个具有一定纬度（在您进行计算的区域周围）和单位（例如英里）的标尺对象：
var ruler = cheapRuler(35.05, 'miles');如果你事先不知道纬度，则可以为每个要素创建单独的标尺（例如，使用道路第一个点的纬度）。
为了方便起见，你还可以根据图块坐标（y 和 z）创建标尺：
var ruler = cheapRuler.fromTile(1567, 12, 'kilometers');然后，你可以像使用 Turf 一样使用标尺对象，只不过直接传递坐标而不是将它们包装为 GeoJSON 特征：
var distance = ruler.distance([30.51, 50.32], [30.52, 50.312]);避免函数包装和输入验证使我们能够额外压缩更多性能。 该库适用于性能至关重要的高级用途，而且我们不针对普通用户，所以这很好。
cheap-ruler 的一个额外小好处是它的代码少于 200 行——非常适合在你希望保持尽可能轻量的网页上使用，并且易于移植到其他编程语言。
原文链接：Fast geodesic approximations with Cheap Ruler
BimAnt翻译整理，转载请标明出处
