4

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.

Aleks N.
  • 6,051
  • 3
  • 42
  • 42

2 Answers2

3

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.

Tom Verbeure
  • 232
  • 2
  • 8
  • Thank you Tom. I'm now studying this library. Will mark your reply as 'Answer' if that really fits. I'm hoping it will, since I'm exactly keeping node data in a SQLite db. – Aleks N. Dec 28 '10 at 00:19
  • Looks like you gave me the proper vector. Here is a similar question and a piece of advice: http://stackoverflow.com/questions/4373730/is-there-an-offline-geocoding-framework-library-or-database-for-ios Saw that earlier but for some reason filtered that out being absorbed by Voronoi algo. :) – Aleks N. Dec 28 '10 at 00:24
0

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.

payne
  • 13,833
  • 5
  • 42
  • 49
  • Actually what I did is compiled Spatialite lib for iOS, then converted my MySQL db to the one with Geometry column and spatial index and let the lib do the rest. – Aleks N. Jan 22 '11 at 10:12