[GRASS-dev] New feature (algorithm and / or module) to implent to GRASS (long)

[Wolf Bergenheim]

Greetings GRASS developers,

I'm attending a course in Spatial Data Algorithms
(http://www.tkk.fi/Units/Cartography/courses/maa-123340/), and we are
supposed to implement one algorithm or data structure we have talked
about. I'd like to combine this work with something useful, that is I'd
like to give whatever I implement to GRASS. Partially for altruistic
reasons, partially because I think that coding within the GRASS
environment will make debugging and testing a whole lot easier and more
comfortable. Now I'd like to know which algorithm would you like me to
implement. Here are some candidates:

1. Label position
=================
One of the algorithms we learned about was "A generic Cartographic
Labeling Algorithm" by Edmondson, Christensen, Marks and Shrieber
published in Cartographica, Vol 33 No. 4, 1996 pp. 13-23.

This algorithm of theirs is able to position labels so that they don't
overlap and the labels are also placed in as good a place as possible.
It can handle line-, point- and area labels.

This module would not be a replacement to v.label rather an extension,
but it would have to start out as a separate module (to make it possible
to grade my work). My plan for this would be to output a label file just
like v.label does. After I'm done for school I'd merge this code to be
triggered by a flag in v.label.

2. Line generalization or smoothing
===================================
A new module which would do line generalization with one of these algorithms

*) Douglas-Peuker algorithm
*) Reumann-Witkam algorithm
*) Lang simplification algorithm
*) Cromley's Hierarchical algorithm
*) Boyle's forward-looking smoothing algorithm

The most famous of these is the Douglas-Peuker algorithm.

If you would like me to do this one please also indicate which algorithm
you would be most interesting /  useful for you.

3. A new simulation/optimization algorithm for least cost path
==============================================================
A new module which would calculate the shortest path from a starting
point to a destination. It would use Dijkstra's algorithm do find the
shortest path in a weighted network. In other words it would treat a
cost surface (generated by r.cost) as a network and then calculate the
shortest path. This differs from r.drain in that r.drain is a local
function, greedy algorithm, whereas this a focal algorithm, that is it
takes not only it's immediate location into account, and finds a global
shortest path.

4. Shortest path in free (vector) space (avoiding obstacles)
============================================================
This module would take as input a vector map with polygons. These
polygons would be treated as obstacles. It would also take a starting
and end point as input. It would output a vector map containing the
shortest path in free space (this assumes an equal cost surface).
There are 2 different ways to do this calculation:

a) by building a "road network" with the help of building trapezoids
from each corner point of the obstacles.
OR
b) by building a visibility graph and converting it into a weighted
network and running Dijkstra's shortest path on it.

------------------------

If you want more elaboration or have questions on any of the above,
please don't hesitate to ask (on or off list). I'd also like to hear any
other comments you might have.

The time-line for this project is that I will start coding at the latest
on week 13 (most probably week 12), and the project will have a demo
session on the 26th of April, and must be completed by the 10th of May.

Best regards,
--Wolf Bergenheim

-- 

<:3 )---- Wolf Bergenheim ----( 8:>