CGAL在iOS上的替代方案

Question

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

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

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

另外，也许您有更好的解决方案。请随意在这里说明。

- Aleks N.

Answer 1

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

但我使用了spatialite库来完成类似的事情。Spatialite运行在sqlite之上。当您使用它时，最好不要使用iPhone附带的sqlite库，而是重新编译包括spatialite的所有内容。一旦将数据存储在数据库中，您可以使用简单的函数，例如ST_Distance来查找最近的线段。

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

- Tom Verbeure

---

谢谢Tom。我现在正在学习这个库。如果它确实适合，我会将您的回复标记为“答案”。我希望它能够胜任，因为我正好将节点数据保存在SQLite数据库中。 - Aleks N.

看起来你给了我正确的向量。这里有一个类似的问题和一条建议：https://dev59.com/tW855IYBdhLWcg3wYjOF 之前看到过，但由于沉迷于 Voronoi 算法而被过滤掉了。 :) - Aleks N.

Answer 2

在我看来，CGAL（委员会设计和C++，总是危险）很混乱。它很难理解。

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

最后，Voronoi图是一个强大的结构，但在这里可能过于复杂了。如果你想避免包含一个大型库，一个简单的启发式方法可能就足够了：沿着你的街道段放置点。给定用户的位置，使用kd树（易于实现，快速，有很多实现可用）找到最近的街道点。使用它们来测试一组候选段以找到最接近的。

- payne

---

实际上我所做的是为iOS编译了Spatialite库，然后将我的MySQL数据库转换成具有几何列和空间索引的数据库，并让该库完成其余操作。 - Aleks N.