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

[Trevor Wiens]

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


-- 
Trevor Wiens 
twiens at interbaun.com

The significant problems that we face cannot be solved at the same 
level of thinking we were at when we created them. 
(Albert Einstein)