4

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

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

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

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

4

2 回答 2

3

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

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

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

于 2010-12-28T00:05:07.407 回答
0

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

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

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

于 2011-01-21T15:41:39.513 回答