iOS 的 CGAL 替代品
我有一组定义街道的节点。每个节点都有纬度和经度。我还有带有纬度和经度的用户位置。我的目的是为每对节点定义的段构建 Voronoi 图，然后找到用户位置最接近哪个节点。
看起来这个任务可以用 CGAL 库来完成。当我正在为 iOS 环境编译它时，也许你们能够提供已经针对 iOS 编译的库的链接，或者从一开始就打算在 Objective C 环境中使用的库......
因为我担心即使CGAL为我编译，我在使用它时也可能会遇到麻烦。谢谢！
PS 您也可能有更好的解决方案。请随意在这里拼写它。
I have a set of nodes that define streets. Each node has latitude and longitude. Also I have user location with latitude and longitude. My intention is to build Voronoi diagram for segments defined by each pair of nodes, and then find which node user location is closest to.
Looks like this task can be accomplished with CGAL library. While I'm in the process of compiling it for iOS environment, probably you guys will be able to give links to libs that are already compiled against iOS, or were intended to be used in Objective C environment from the very beginning...
Because I'm afraid that even if CGAL compiles for me, I might get into trouble when using it. Thanks!
P. S. Also probably you have a better solution in mind. Feel free to spell it our here.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我从未使用过CGAL，所以我无法评论我的解决方案是否更好。
但我使用 spatialite 库来做类似的事情。 Spatialite 运行在 sqlite 之上。当你使用它时，最好不要使用iPhone附带的sqlite库，而只是从头开始重新编译所有内容，并包含spatialite。一旦数据库中有数据，您就可以使用 ST_Distance 等简单函数来查找闭合线段。
Spatialite 使用 R*-Tree 进行空间索引。查找速度非常快。
I have never used CGAL, so I can't comment on whether or not my solution is better.
But I have used the spatialite library to do something similar. Spatialite runs on top of sqlite. When you use it, it's better to not use the sqlite library that comes with the iPhone, but simply recompile everything from scratch with spatialite included. Once you have the data in the database, you can use simply functions such as ST_Distance to find the closes segments.
Spatialite uses R*-Trees for spatial indexing. Lookups are very fast.
CGAL 是一团糟（委员会设计和 C++，总是危险的），恕我直言。很难渗透。
但是，您需要在设备上计算 Voronoi 图吗？如果您的数据集是街道数据，它可能不会改变那么多，您可以在设备外预先构建它。
最后，沃罗诺伊图是一个强大的构造，但在这里可能有点过头了。如果您想避免使用大型图书馆，一个简单的启发式方法可能就足够了：沿着街道路段放置点。给定用户的位置，找到最近的街道点（例如，使用 kd 树——实现简单、速度快、有大量可用的实现）。使用它们来测试候选段集以找到最接近的段。
CGAL is a mess (committee design and C++, always dangerous), IMHO. It's tough to penetrate.
But, do you need to calculate the Voronoi diagram on-device? If your data set is street data, it may not change that much, and you could pre-build it off-device.
Finally, the Voronoi diagram is a powerful construct, but may be overkill here. If you want to avoid including a big library, a simple heuristic may suffice: place points along your street segments. Given a user's location, find the nearest street points (using, say, a kd-tree -- simple to implement, fast, lots of implementations available). Use those to test a candidate set of segments to find the closest.