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

[Michael Barton]

My second choices after #1 would be (in ranked order) 3,2,4

Michael


On 3/1/07 3:54 PM, "Wolf Bergenheim" <wolf+grass at bergenheim.net> wrote:

> 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

__________________________________________
Michael Barton, Professor of Anthropology
School of Human Evolution & Social Change
Center for Social Dynamics & Complexity
Arizona State University

phone: 480-965-6213
fax: 480-965-7671
www: http://www.public.asu.edu/~cmbarton