algorithm - 在 mapKit 中获取凹壳

Question

使用 Swift 和苹果 mapKit 我想从 gps 坐标计算凹壳。我有一个定义折线的 CLLocation （纬度，经度）数组。对于路线地理围栏，我为折线中的每个 2d 点计算了距离为 n 米的所有可能的纬度和经度。此时我想计算这组点的凹壳。我找不到任何关于如何从 gps 坐标计算凹壳的信息。谁能给我推荐一个教程？

Answer 1

这篇论文应该对你有用。我使用本文中的算法来实现我的hull.js库。

您也可以通过Delaunay 三角剖分对您的形状进行三角剖分，然后像这里一样删除边界边缘。

Answer 2

在我读到你的问题之前，我从来没有听说过凹壳这个词，所以我用谷歌搜索了它。我发现了几种凹壳算法的参考资料。

似乎没有单一的解决方案。您必须决定是想要更光滑的船体还是内部面积最小的船体，或者介于两者之间。

如果您正在使用的所有点都在 100 公里左右的范围内，您可以简化问题并将您的纬度/经度转换为笛卡尔坐标。你所要做的就是计算出当前纬度经度之间的距离。

一旦你将你的点转换为笛卡尔坐标，它就变成了一个简单的凹壳问题。

如果您正在处理大片区域并且想要考虑地球的曲率，那么您遇到的问题要复杂得多。