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

[Michael Barton]

I agree with Trevor about the #1 priority (i.e., labeling). I need to mull
over the other options.

Michael


On 3/1/07 4:35 PM, "Trevor Wiens" <twiens at interbaun.com> wrote:

> On Fri, 02 Mar 2007 00:54:03 +0200
> Wolf Bergenheim 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:
> 
> Get marks and code for GRASS. What a wonderful idea.
> 
> The options all sound interesting. My personal vote would be for label
> placement as I see cartography as a major weakness in GRASS and this
> would lay part of the foundation for better cartography in GRASS. My
> experience in most systems is that when it comes time for output
> hours can be wasted in label placement so an algorithm to get one
> 90% good on that would be a huge time saver for cartographic use. It
> would be very useful, if it can be written such that it could be
> used by either v.label, ps.map or perhaps a new interface in the
> future. In that regard label size in relation to a paper or view size
> will need to be taken into account.
> 
> My other choices in order of preference are 4, 3, and 2. In regard to
> line smoothing I know little about it so I can't state a preference on
> algorithm and thus it is my last choice. I've not needed this
> functionality before so I've never researched it.
> 
> Thanks
> 
> T
>> 
>> 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:>
>> 
>> _______________________________________________
>> grass-dev mailing list
>> grass-dev at grass.itc.it
>> http://grass.itc.it/mailman/listinfo/grass-dev
> 

__________________________________________
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