[Roadnav-devel] Thoughts about adding external dependencies
Status: Inactive
Brought to you by:
rllynch
|
From: Dustin S. <du...@vi...> - 2008-10-05 18:37:44
|
Hey, So after a bit of a hiatus, I'm working a bit more on improving libroadnav (though, my time is still currently somewhat limited). Right now, I'm starting work on recreating the backend for Roadnav to scale a bit better, and be OpenStreetMap focused. Along the way, I've come across some dependencies that I'm currently thinking about adding to Roadnav, and I welcome any thoughts about this. I have listed the libraries in order of importance. bzip2 (important): OSM distributes the planet.osm (for those not familiar, its a collection of all OSM data) file in a 4GB bz2 file. While I plan to support primarily the live API, it seems like it would be good to support reading directly from the planet file if the user really wants to spend a few days compiling maps from it. wxWidgets currently does not support bzip files. expat (important): expat is used by wxWidgets internally to parse XML, and more importantly it can parse XML files in a streaming fashion, which will be particularly important for the planet.osm file... given its 90GB uncompressed. The current OSM data importer uses a custom set of operations to parse the XML file, but it seems to be that it could be a good idea (and possibly less error-prone) to use expat to do this instead. STXXL (thinking about this): STXXL is an STL-like library designed/optimized for very large data sets using external memory. There are a number of features from this library that could potentially be really useful (the vector and map containers in particular), depending on the performance of this library for smaller data sets (hundreds of thousands to millions, which is the range Roadnav uses). It has also occurred to me that adapting the map implementation (its a btree, which is similar to an rtree) to use an R tree index (such as the one I've implemented) could be a *huge* win, and save lots of time. I've actually contacted the author about this idea to see if he would be willing to accept some patches to that effect. Boost (semi-thinking about this, still a long way off): Currently roadnav has an implementation of routing algorithms (Dijkstra's algorithm, in particular). However, one thing that is particularly attractive to me is moving this to use the Boost Graph Library, which not only has implementations for Dijkstra's, but other routing-related algorithms too (which may help improve performance). Interestingly enough, there are also some graph-related items in STXXL also, so this may not be necessary. Of course, this is not really a priority yet, but I figured that I would throw it out there... I realize that for Linux versions of roadnav, the dependencies aren't quite as big of an issue, whereas for windows it can get trickier and so we would probably have to import these external dependencies into the project in their own set of directories or something. If anyone is interested, I'm doing work on the backend in libroadnav/branches/TestConcepts/Backend As I said, let me know your thoughts about any of this. For the most part, I haven't actually made up my mind about it yet, just trying to consider good ways to do this stuff. Thanks! Dustin -- Innovation is just a problem away |