CGAL replacement for iOS

Question

I have a set of nodes that define the streets. Each node has latitude and longitude. I also have a user location with latitude and longitude. My intention is to build a Voronoi diagram for the segments defined by each pair of nodes, and then find which node location is closest to.

It looks like this task can be accomplished using the CGAL library. Although I'm going to compile it for the iOS environment, you guys may be able to provide links to libs that are already compiled against iOS, or were intended to be used in the Objective-C environment from the very beginning ...

Because I'm afraid that even if CGAL compiles for me, I might run into problems using it. Thanks!

R. S. Also, probably you have a better solution. Feel free to write it here.

Answer 1

I have never used CGAL, so I can not comment on whether my solution is better.

But I used the spatialite library to do something like this. Spatialite runs on top of sqlite. When you use it, it’s better not to use the sqlite library that comes with the iPhone, but simply recompile everything from scratch with the included space. Once you have the data in the database, you can simply use functions such as ST_Distance to find the closing segments.

Spatialite uses R * -Trees for spatial indexing. The search is very fast.

Answer 2

CGAL - mess (committee design and C ++, always dangerous), IMHO. It’s hard to penetrate.

But do you need to calculate the Voronoi diagram on the device? If your data set is street data, it may not change so much, and you can pre-create it outside the device.

Finally, the Voronoi diagram is a powerful construction, but here it may be redundant. If you want to avoid a large library, a simple heuristic is enough: place dots along your street segments. Given the user's location, find the nearest street (using, say, a kd tree - it's easy to implement, quickly, many implementations are available). Use the ones to check the selection of candidates for segments to find the closest.