iphone - iOS的CGAL替代品

Question

我有一组定义街道的节点。每个节点都有纬度和经度。我也有纬度和经度的用户位置。我的目的是为每对节点定义的段构建 Voronoi 图，然后找到最接近哪个节点的用户位置。

看起来这个任务可以用 CGAL 库来完成。虽然我正在为 iOS 环境编译它，但也许你们将能够提供已经针对 iOS 编译的库的链接，或者从一开始就打算在 Objective C 环境中使用......

因为我担心即使CGAL为我编译，我在使用时可能会遇到麻烦。谢谢！

PS也可能你有一个更好的解决方案。随意拼写我们在这里。

Answer 1

我从未使用过 CGAL，所以我无法评论我的解决方案是否更好。

但是我使用了spatialite库来做类似的事情。Spatialite 在 sqlite 之上运行。使用的时候，最好不要使用 iPhone 自带的 sqlite 库，而是简单的从头开始重新编译所有的东西，包括 spatialite。在数据库中获得数据后，您可以使用简单的函数（例如 ST_Distance）来查找关闭段。

Spatialite 使用 R*-Trees 进行空间索引。查找速度非常快。

Answer 2

CGAL 是一团糟（委员会设计和 C++，总是很危险），恕我直言。很难穿透。

但是，您需要在设备上计算 Voronoi 图吗？如果您的数据集是街道数据，它可能不会发生太大变化，您可以在设备外预先构建它。

最后，Voronoi 图是一个强大的构造，但在这里可能有点矫枉过正。如果你想避免包含一个大图书馆，一个简单的启发式可能就足够了：沿着你的街道放置点。给定用户的位置，找到最近的街道点（例如，使用 kd-tree——实现简单、快速、有很多可用的实现）。使用这些来测试一组候选段以找到最接近的段。