# Difference between revisions of "GRASS SoC Ideas 2007"

m (→See also) |
|||

(20 intermediate revisions by 6 users not shown) | |||

Line 1: | Line 1: | ||

GRASS related ideas for the [http://wiki.osgeo.org/index.php/Google_Summer_of_Code Google Summer of Code] 2007: | GRASS related ideas for the [http://wiki.osgeo.org/index.php/Google_Summer_of_Code Google Summer of Code] 2007: | ||

− | * Improved Line of Sight Analysis in GRASS | + | ==Timeline / Requirements for GRASS project== |

+ | |||

+ | * [http://code.google.com/support/bin/topic.py?topic=10442 Google SoC FAQ] | ||

+ | |||

+ | * Monday March 12th 2007, Deadline for '''OSGeo''' submission as an organization | ||

+ | * We must list of potential mentors for GRASS work | ||

+ | * March 24: Student application deadline. | ||

+ | * April 9: Accepted student applications announced. | ||

+ | * May 28: Students begin work. | ||

+ | * August 31: final evaluation deadline. | ||

+ | |||

+ | ==Improved Line of Sight Analysis in GRASS== | ||

Line of sight determination is a very important analysis to have available in a GIS. The GRASS module that currently performs this function, r.los, has a number of limitations, including being very slow to run and unable to handle large high-resolution datasets. The task: write a new r.los module based on the paper 'A Fast Algorithm for Approximate Viewshed Computation' published in 'Photogrammetric Engineering & Remote Sensing' July 2003: | Line of sight determination is a very important analysis to have available in a GIS. The GRASS module that currently performs this function, r.los, has a number of limitations, including being very slow to run and unable to handle large high-resolution datasets. The task: write a new r.los module based on the paper 'A Fast Algorithm for Approximate Viewshed Computation' published in 'Photogrammetric Engineering & Remote Sensing' July 2003: | ||

http://www.asprs.org/publications/pers/2003journal/july/2003_jul_767-774.pdf | http://www.asprs.org/publications/pers/2003journal/july/2003_jul_767-774.pdf | ||

Incorporate features of r.cva (http://www.ucl.ac.uk/~tcrnmar/GIS/r.cva.html), which cannot currently be incorporated in GRASS for licensing reasons, and extend with other functionality as appropriate. | Incorporate features of r.cva (http://www.ucl.ac.uk/~tcrnmar/GIS/r.cva.html), which cannot currently be incorporated in GRASS for licensing reasons, and extend with other functionality as appropriate. | ||

+ | |||

The work will involve familiarisation with the GRASS raster library for reading and writing maps, the GRASS vector library for reading analysis location sites. It is expected that the GRASS directed graph library will also be useful for implementing many features of the algorithm (specifically, determining the crossing points and distances between the cells). | The work will involve familiarisation with the GRASS raster library for reading and writing maps, the GRASS vector library for reading analysis location sites. It is expected that the GRASS directed graph library will also be useful for implementing many features of the algorithm (specifically, determining the crossing points and distances between the cells). | ||

− | Potential Mentor: Paul Kelly | + | Some hints on what's involved in GRASS programming are available here: http://freegis.org/cgi-bin/viewcvs.cgi/*checkout*/grass6/SUBMITTING |

+ | |||

+ | ; Potential Mentor: Paul Kelly | ||

+ | |||

+ | ==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. | ||

− | * | + | This work will involve the use of the vector library to read the vector maps to be generalized and writing the new as a new vector map. |

− | + | ||

+ | ; Potential Mentor: Wolf Bergenheim | ||

+ | |||

+ | ; Google [http://code.google.com/soc/2007/osgeo/appinfo.html?csaid=3D7195C3927C616D Abstract] | ||

+ | |||

+ | ==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. | ||

+ | |||

+ | This will involve reading and writing raster maps. | ||

+ | |||

+ | ; Potential Mentor: Wolf Bergenheim | ||

+ | |||

+ | ==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: | ||

+ | * by building a "road network" with the help of building trapezoids from each corner point of the obstacles. | ||

+ | OR PREFERABLY | ||

+ | * by building a visibility graph and converting it into a weighted network and running Dijkstra's shortest path on it. | ||

+ | |||

+ | This project will be vector and will also involve the directed graph library when calculating the shortest path. | ||

+ | |||

+ | ; Potential Mentor: Wolf Bergenheim | ||

+ | |||

+ | ; Google [http://code.google.com/soc/2007/osgeo/appinfo.html?csaid=FEF51B36978B92BF Abstract] | ||

+ | |||

+ | ==Further work on r.li== | ||

+ | The r.li module recently entered official GRASS code base. It is meant as a faster and more manageable replacement for r.le for the analysis of landscape ecology and composition. To replace it fully, we need: | ||

+ | * implementation of other indices | ||

+ | * remove the dependency on TclTk, so as to prepare it for the coming python GUI | ||

+ | * further testing and bugfixing | ||

+ | |||

+ | ; Potential Mentor: Paolo Cavallini | ||

+ | |||

+ | == Other ideas == | ||

+ | * better implement PostGIS support (I do not think this is very useful --[[User:Cavallini|Cavallini]] 07:48, 13 March 2007 (CET)) | ||

* integrate GDAL as part of GRASS raster library: [http://freegis.org/cgi-bin/viewcvs.cgi/grass/gips/gip-0002.txt?rev=HEAD&content-type=text/vnd.viewcvs-markup GRASS raster "live links" proposal] | * integrate GDAL as part of GRASS raster library: [http://freegis.org/cgi-bin/viewcvs.cgi/grass/gips/gip-0002.txt?rev=HEAD&content-type=text/vnd.viewcvs-markup GRASS raster "live links" proposal] | ||

− | + | : is this somewhat similar to a "r.external" equivalent of v.external? --[[User:Cavallini|Cavallini]] 07:48, 13 March 2007 (CET) | |

− | : | + | :: yes -- Markus [[User:Neteler|Neteler]] 15:03, 13 March 2007 (CET) |

+ | * implement parts of [[Time series in GRASS]] | ||

== Potential Mentors == | == Potential Mentors == | ||

* Paul Kelly (for line of sight project) | * Paul Kelly (for line of sight project) | ||

+ | * Wolf Bergenheim (for the line generalization / least cost projects) | ||

+ | * Paolo Cavallini (for r.li project) | ||

− | + | == See also == | |

* [http://wiki.osgeo.org/index.php/Google_Summer_of_Code OSGeo involvement Google Summer of Code] | * [http://wiki.osgeo.org/index.php/Google_Summer_of_Code OSGeo involvement Google Summer of Code] | ||

− | + | {{GSoC}} | |

− |

## Latest revision as of 04:47, 13 March 2011

GRASS related ideas for the Google Summer of Code 2007:

## Contents

- 1 Timeline / Requirements for GRASS project
- 2 Improved Line of Sight Analysis in GRASS
- 3 A new module which would do line generalization with one of these algorithms
- 4 A new simulation/optimization algorithm for least cost path
- 5 Shortest path in free (vector) space (avoiding obstacles)
- 6 Further work on r.li
- 7 Other ideas
- 8 Potential Mentors
- 9 See also

## Timeline / Requirements for GRASS project

- Monday March 12th 2007, Deadline for
**OSGeo**submission as an organization - We must list of potential mentors for GRASS work
- March 24: Student application deadline.
- April 9: Accepted student applications announced.
- May 28: Students begin work.
- August 31: final evaluation deadline.

## Improved Line of Sight Analysis in GRASS

Line of sight determination is a very important analysis to have available in a GIS. The GRASS module that currently performs this function, r.los, has a number of limitations, including being very slow to run and unable to handle large high-resolution datasets. The task: write a new r.los module based on the paper 'A Fast Algorithm for Approximate Viewshed Computation' published in 'Photogrammetric Engineering & Remote Sensing' July 2003: http://www.asprs.org/publications/pers/2003journal/july/2003_jul_767-774.pdf Incorporate features of r.cva (http://www.ucl.ac.uk/~tcrnmar/GIS/r.cva.html), which cannot currently be incorporated in GRASS for licensing reasons, and extend with other functionality as appropriate.

The work will involve familiarisation with the GRASS raster library for reading and writing maps, the GRASS vector library for reading analysis location sites. It is expected that the GRASS directed graph library will also be useful for implementing many features of the algorithm (specifically, determining the crossing points and distances between the cells).

Some hints on what's involved in GRASS programming are available here: http://freegis.org/cgi-bin/viewcvs.cgi/*checkout*/grass6/SUBMITTING

- Potential Mentor
- Paul Kelly

## 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.

This work will involve the use of the vector library to read the vector maps to be generalized and writing the new as a new vector map.

- Potential Mentor
- Wolf Bergenheim

- Google Abstract

## 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.

This will involve reading and writing raster maps.

- Potential Mentor
- Wolf Bergenheim

## 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:

- by building a "road network" with the help of building trapezoids from each corner point of the obstacles.

OR PREFERABLY

- by building a visibility graph and converting it into a weighted network and running Dijkstra's shortest path on it.

This project will be vector and will also involve the directed graph library when calculating the shortest path.

- Potential Mentor
- Wolf Bergenheim

- Google Abstract

## Further work on r.li

The r.li module recently entered official GRASS code base. It is meant as a faster and more manageable replacement for r.le for the analysis of landscape ecology and composition. To replace it fully, we need:

- implementation of other indices
- remove the dependency on TclTk, so as to prepare it for the coming python GUI
- further testing and bugfixing

- Potential Mentor
- Paolo Cavallini

## Other ideas

- better implement PostGIS support (I do not think this is very useful --Cavallini 07:48, 13 March 2007 (CET))
- integrate GDAL as part of GRASS raster library: GRASS raster "live links" proposal

- is this somewhat similar to a "r.external" equivalent of v.external? --Cavallini 07:48, 13 March 2007 (CET)
- yes -- Markus Neteler 15:03, 13 March 2007 (CET)

- implement parts of Time series in GRASS

## Potential Mentors

- Paul Kelly (for line of sight project)
- Wolf Bergenheim (for the line generalization / least cost projects)
- Paolo Cavallini (for r.li project)