[kde-edu]: GSoC proposal: Marble routing

[Alex Merry]

I'm interested in applying for one of the suggested GSoC projects involving 
Marble.  This is the routing suggestion: implementing a routing algorithm in 
Marble.

Included below is what I've come up with for my application.  It's a little 
over the character limit for the synopsis for the application form, but I 
would put this in a PDF file and link to it from my application.

Any comments/criticisms/advice would be greatly appreciated!

Alex



Marble Routing Support - Alex Merry

Marble provides various geographical functions as a KPart and
as a standalone application.  It can display the globe, with
various surface textures and, thanks to the work of last
year's SoC projects, it can do 2D projections.

Marble would be greatly enhanced, and the OpenStreetMap data
put to much better use, if it were possible to ask Marble for
a route from one point on the Earth to another.


Tasks:

This project would involve the following tasks:
1. Implement a routing algorithm that, given a starting point
   and an ending point, would calculate the best route
   between the points.
2. display this route on the globe surface.
3. provide a user interface for telling Marble the two points,
   such as a context menu action or a search for a placemark
   or street.
4. display a list of directions, in the style of Google Maps

1: Routing Algorithm

It should be possible to use either an internet link (using
the OpenStreetMap API) or an OSM file (such as planet.osm,
although generally a extract such as the uk.osm file would
be used).  Care would need to be taken with regards to
memory consumption in the OSM file case, as planet.osm is
in the region of 60Gb!

When using an internet link, data should be downloaded as and
when the routing algorithm requires it.  Naturally, the
load-on-demand interface should be abstracted from the actual
data retrieval, so the algorithm wouldn't care whether the
data was extracted from a file or from the internet.

The algorithm implementation should probably return a list
of nodes, two for each way - where the way is entered and
where it is left.

The algorithm will obviously have to take into account things
like one-way streets.  However, it should also take into
account road types: motorways are generally preferable to
trunk roads, which are generally preferable to secondary
roads, and so on.


2. Route Projection

When using the Mapnik OpenStreetMap projection, it should
be possible to simply render the route onto the map, using
the data returned from the routing algorithm, in much the
same way that Mapnik might render a way - by drawing lines
between each node and the following one on the route.


3. User Interface

The current interface for marking measure points (an option
in the context menu for the map) provides a way of marking
the start and finish of a route.

However, simply typing in a place name (such as a street name)
should be possible as well.  The OpenStreetMap Extended API
(osmxapi) would provide a good online query interface, but
offline searching (using an OSM file) should also be possible.

Searching for a placemark on the map should also be possible.


4. Directions

The information from OpenStreetMap includes street names.  It
should be relatively simple to provide a list of ways that
the route includes.

This can be augmented with a calculated distance to travel
on each way, and such information about how to move from one
way to another (such as "left turn", or "first exit on the
roundabout") as can be extracted from the OSM data.

This could be listed in a tab in the toolbox.



Further work:

There are some improvements that could be made that are
outside the scope of this GSoC project, but could be added
in later if the project is finished unexpectedly early, or
after the project has finished.

Route Restrictions

Provide a method of only allowing routes that involve certain
types of transport (for example, it is not possible to walk
or cycle along motorways).

This would involve modifying the alogorithm to give prohibit
certain routes (such as motorways for cyclists or pedestrians)
or change the weightings for certain routes (cyclists would
generally prefer minor roads to major ones, for example).



Time:

I would expect to spend most time (over half of the project
time) on the first part of the project: implementing the
algorithm and data extraction.  Rendering the route and
generating the directions should be the next most
time-consuming parts, with the user interface relatively
straightforward to add.



Biography:

I am in my fourth year of my undergraduate masters in
Mathematics and Computer Science.  I got involved with the
KDE project at the start of 2007, learning C++ and Qt to
do so.  I started doing various junior jobs in the core
KDE libraries, and then got involed in Plasma development
when it kicked off later that year.

My biggest programming projects to date have both involved
Qt: the nowplaying data engine and applet for Plasma and
my final year project for my degree course.

I can generally be found on #kde-devel and #plasma as
randomguy3.



-- 
KDE: http://www.kde.org
Ubuntu/Kubuntu: http://www.ubuntu.org http://www.kubuntu.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 194 bytes
Desc: This is a digitally signed message part.
Url : http://mail.kde.org/pipermail/kde-edu/attachments/20080321/c317c233/attachment.pgp