Archive for the ‘roadnav’ Category

Updates and such

Tuesday, January 6th, 2009

Well, I have a *ton* of things going on right now… I am very busy mentoring for a FIRST team that my company sponsors (the Kwarqs), and some important deadlines coming up at work.. and trying to get my massive updates to Roadnav integrated in.

Speaking of which, I’ve bundled all of my R* and B+ tree code into a library called libsdbx… I need to write more in depth about it, but its a nice header-only C++ library that allows usage of generic R* and B+ trees with either a memory backend or a file-based backend. Its really nice to use, but I think I’m going to hold off on releasing it in a formal package until a final release of libroadnav is created (which will definitely iron out any lingering performance issues or bugs).

Libsdbx can be found in Roadnav SVN at https://roadnav.svn.sourceforge.net/svnroot/roadnav/libsdbx/trunk/.

As I create neat FIRST-related stuff, I’ll be sure to post some of that up here also. I’m really excited about this open source thrust that FIRST seems to be going down lately, its definitely encouraging and makes me want to contribute.

Posted in FIRST, roadnav | No Comments »

R* Tree Implementation for C++

Saturday, October 4th, 2008

So a few weeks ago I finished preliminary work on an R* Tree implementation in C++. My goal for this implementation is as follows:

  • Simple API – Most existing implementations I’ve seen are far from simple
  • Generic enough to use with most types, with low overhead
  • N dimensions for bounding boxes
  • Easy to integrate and use for Roadnav
  • Take advantage of modern C++ features to get decent performance

This is a header-only implementation of an R tree with an R* index, and makes heavy use of templates, STL, and STL-style functors; but it should work in any relatively modern C++ compiler. To do searching for nodes, this implementation uses the Visitor pattern via functors — there are examples and documentation in RStarVisitor.h.

If you use this, *please* let me know, I’m very interested to see what bugs may come up, and possible performance problems. Unfortunately, I haven’t gotten around to writing any comprehensive tests for it (but given the tests I’ve run so far, I’m reasonably sure the implementation is mostly correct), but I expect that once I get it integrated into Roadnav that this will follow shortly after. Also, integration of the R* tree into Roadnav will make a lot of potential errors pop out. Look for this in the near future.

Additionally, I am thinking about some of the following ideas too:

  • Adding the ability to work with extra-large datasets by saving/loading to/from disk (after all, that is the point of R trees…)
  • Adding a bulk insert function — there is pseudocode already for this, but I haven’t actually written an implementation for this yet. Also, a more efficient bulk delete function
  • Trying to implement it as a Boost intrusive container. I’ve been playing with some Boost stuff lately at work, and theres a lot of neat things there.

I’ll also use this opportunity to put in a plug for Roadnav — if you’re looking to work on an open source project, theres a bunch of (mostly) interesting stuff that I’m working on/planning for Roadnav. What I’m working on right now is totally removing US-specific stuff from Roadnav, and moving to an OpenStreetMap-only implementation. Theres a number of features that are getting thrown away, but I think that the dynamic community that OSM opens up to Roadnav will be well worth it.

Note: I’ve updated this quite a bit (though, remove functionality has been removed and it no longer uses the visitor pattern for data access), and its currently a part of libsdbx. Libsdbx can be found in Roadnav SVN at https://roadnav.svn.sourceforge.net/svnroot/roadnav/libsdbx/trunk/. I’ll write about this soon.. but its pretty neat. It supports R* and modified B+ trees, in memory or on disk. Check it out.

Note II: I’ve pushed the source code to github at https://github.com/virtuald/r-star-tree

Download the sourcecode here

Posted in roadnav | 22 Comments »

XKCD GPS “Cyborg navigation” ported to Roadnav

Sunday, July 13th, 2008

So as you probably know, I am a fan of the webcomic XKCD. Back in May, Randall posted a comic and a blag article about his idea of a dead reckoning type navigation system, which every couple of seconds it speaks the distance and the direction to your destination. I’ve been hanging out with the excellent people at #geohashing, and one of them suggested that I look at the “cyborg script” for use on my carputer. Well I thought, why not port it to C++ and stick it in Roadnav?

So I went ahead and did the implementation in my semi-experimental wx3 branch of Roadnav, and it worked out pretty well! Its not present in any downloads on the Roadnav site yet . You can find it labeled as the “wxWidgets 3 Development Line (alpha)” at the Roadnav download page. Some nice things about using it inside roadnav:

  • You can enter the destination in a street address or raw coordinates
  • It marks the destination on the map that it shows
  • Cross platform support (Windows, Linux, OSX)

Now, there are a number of usability issues present with this implementation of the Cyborg navigation. For one, you can’t mute it (inside the program at least). For two, you can’t actually turn it off yet.

If you want to play with it, you can download the source code via SVN for Roadnav and libroadnav in the wx3 branch. Alternatively, you can download a snapshot from the Roadnav downloads page. If you’re just looking for a C++ version of the cyborg script, you can see it at this link.

Mind you, that whole branch is mostly alpha at the moment, but revision 1715 should work without any significant problems. Hopefully a stable release will be out by the end of summer (no guarantees here though). If you find bugs or have issues with that particular branch, drop me a line!

Despite being (in my opinion) the best open source GPS navigation app out there, I will admit that there are a number of large performance and usability issues with Roadnav. However, I’m hoping that we (though, at the moment its only me doing active development) can optimize it and rework its code base to perform just as well as any commercial GPS apps out there (if you’re wanting to do some development, join the roadnav-devel mailing list or contact me, I have a number of ideas that aren’t in the TODO list yet).

Original XKCD blag post: http://blag.xkcd.com/2008/05/20/gps-cyborg-implant/

Posted in Carputer, roadnav, xkcd | No Comments »