GRASS GSoC 2013 Temporal GIS Algebra for raster and vector data in GRASS
(See also other GRASS GSoC 2013 projects)
Student Name: | Thomas Leppelt, Thünen Institute Braunschweig Germany |
Organization: | OSGeo - Open Source Geospatial Foundation |
Mentor Name: | Mentor: Soeren Gebbert Backup mentor: Helena Mitasova & Michael Barton |
Title: | Temporal GIS Algebra for raster and vector data in GRASS |
Abstract
Using the TGRASS GIS API to create spatio-temporal vector and raster algebra to process massive vector and raster datasets based on their spatio-temporal relationships.
Background
The temporal modules in GRASS are capable of managing, analysing, processing and visualizing large spatio-temporal datasets. Additionally various temporal framework properties were implemented to describe the temporal and spatial relationships for datasets. Our aim is to develop modules, that can be used to process massive vector and raster datasets based on their spatio-temporal relationships. Therefore a spatio-temporal vector and raster algebra is needed and has to be implemented into GRASS7.
The idea
I would like to develop a temporal GIS algebra for raster and vector data in GRASS7. The idea is also posted on the GRASS SoC ideas page for 2013 (http://grasswiki.osgeo.org/wiki/GRASS_SoC_Ideas_2013).
The temporal modules in GRASS are capable of managing, analysing, processing and visualizing large spatio-temporal datasets. Additionally various temporal framework properties were implemented to describe the temporal and spatial relationships for datasets. Our aim is to develop modules, that can be used to process massive vector and raster datasets based on their spatio-temporal relationships. Therefore a spatio-temporal vector and raster algebra is needed and has to be implemented into GRASS7.
The project will have three new GRASS7 modules and additions to the GRASS GIS temporal library as outcome:
v.mapcalc
According to r.mapcalc for raster datasets, v.mapcalc will provide the functionalities of GRASS modules like v.overlay (and, or, xor, not), v.buffer (buff_point, buff_line, buff_area) and v.patch (patch) as algebraic expression for vector map operations. The implementation will be realised with PLY (http://www.dabeaz.com/ply/) and PyGRASS and will work as a standalone module. In the next step we will develop the temporal algebra that provides temporal variables (day of year, weekday, datum, time, ...) and spatio-temporal topology relations (predecessor, successor, follows, equals, in, meet, …) to perform analyses based on dataset spatio-temporal topologies. The TGRASS GIS API delivers the required functionalities to set up the spatio-temporal relationships for raster and vector datasets. This is the base to create GRASS modules for spatio-temporal vector and raster map calculations:
t.vect.mapcalc
The spatio-temporal vector map calculation module will be derived by combining the new implemented module v.mapcalc with the spatio-temporal algebra into a new module named t.vect.mapcalc. This module will provide all vector calculation options from v.mapcalc with additional spatio-temporal algebra. The implementation of a class structure will ensure that the new class is based on the classes for vector and spatio-temporal algebra and inherits all their functionalities.
t.rast.mapcalc
The spatio-temporal raster map calculation module will be derived by combining the existing module r.mapcalc with the new implemented spatio-temporal algebra. In result the arithmetic operation from r.mapcalc will be extended by spatio-temporal algebra. This module will be based on the same class for spatio-temporal algebra as t.vect.mapcalc to avoid redundancy.
v.mapcalc
Description
v.mapcalc performs overlay and buffer functions on vector map layers. New vector map layers can be created which are expressions of existing vector map layers, boolean vector operations and buffer functions.
Program use
The module expects its input as expression in the following form:
result = expression
This structure is similar to r.mapcalc, see r.mapcalc. Where result is the name of a vector map layer that will contain the result of the calculation and expression is any valid combination of boolean and buffer operations for existing vector map layers. The input is given by using the first module option expression= . This option passes a quoted expression on the command line, for example:
v.mapcalc expression="A = B"
Where A is the new vector map layer that will be equal to the existing vector map layer B in this case.
v.mapcalc "A = B"
Will give the same result.
Operators and functions
The module supports the following boolean vector operations:
Boolean Name | Operator | Meaning | Precedence | Correspondent function |
---|---|---|---|---|
AND | & | Intersection | 1 | (v.overlay operator=and) |
OR | | | Union | 1 | (v.overlay operator=or) |
DISJOINT OR | + | Disjoint union | 1 | (v.patch) |
XOR | ^ | Symmetric difference | 1 | (v.overlay operator=xor) |
NOT | ~ | Complement | 1 | (v.overlay operator=not) |
And vector functions:
Function name | Description |
---|---|
buff_p(A, size) | Buffer the points of vector map layer A with size |
buff_l(A, size) | Buffer the lines of vector map layer A with size |
buff_a(A, size) | Buffer the areas of vector map layer A with size |
Notes
As shown in the operator table above, the boolean vector operators do not have different precedence. In default setting the expression will be left associatively evaluated. To define specific precedence use parentheses around these expressions, for example:
v.mapcalc expression="D = A & B | C"
Here the first intermediate result is the intersection of vector map layers A & B. This intermediate vector map layer is taken to create the union with vector map C to get the final result D. It represents the default behaviour of left associativity.
v.mapcalc expression="D = A & (B | C)"
Here the first intermediate result is taken from the parenthesized union of vector map layers B | C. Afterwards the intersection of the intermediate vector map layer and A will be evaluated to get the final result vector map layer D.
It should be noticed, that the order in which the operations are performed does matter. Different order of operations can lead to a different result.
Examples
This example needed specific region setting. It should work in UTM and LL test locations. First set the regions extent and create two vector maps with one random points, respectively:
g.region s=0 n=80 w=0 e=120 b=0 t=50 res=10 res3=10 -p3
v.random --o -z output=point_1 n=1 seed=1
v.info point_1
v.random --o -z output=point_2 n=1 seed=2
v.info point_2
Then the vector algebra is used to create buffers around those points, cut out a subset and apply different boolean operation on the subsets in one statement:
v.mapcalc --o expr="buff_and = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) & (buff_p(point_2, 35) ~ buff_p(point_2, 25))"
v.mapcalc --o expr="buff_or = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) | (buff_p(point_2, 35) ~ buff_p(point_2, 25))"
v.mapcalc --o expr="buff_xor = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) ^ (buff_p(point_2, 35) ~ buff_p(point_2, 25))"
v.mapcalc --o expr="buff_not = (buff_p(point_1, 30.0) ~ buff_p(point_1, 20.0)) ~ (buff_p(point_2, 35) ~ buff_p(point_2, 25))"
Temporal Algebra concept
An overview of the Temporal GIS Algebra concept for Raster and Vector Data is open for discussion and can be found here.
Project plan
Period | Task | Status / Notes |
---|---|---|
May 31 | Getting familiar with PLY and PyGRASS, read documentations | √ |
June 7 | Implement v.mapcalc | √ |
June 14 | Working with TGIS API framework | √ |
June 21 | Create temporal algebra draft, writing example programs | √ |
June 28 | Creating spatio-temporal algebra by using TGIS API | √ |
July 5 | Implementation of temporal algebra in PLY | √ |
July 12 | Continue testing and implementation of temporal algebra | √ |
July 19 | Writing documentation for temporal algebra | √ |
July 26 | Implementation of t.vect.mapcalc with documentation and tests | in progress |
August 2 | Mid-term evaluations deadline | |
August 9 | Write documentation and tests for t.vect.mapcalc | |
August 16 | Implementation of t.rast.mapcalc | |
August 23 | Continue implementation of t.rast.mapcalc | |
August 30 | Continue implementation of t.rast.mapcalc | |
September 6 | Write documentation and tests for t.rast.mapcalc | |
September 16 | Suggested 'pencils down' date | |
September 20 | Write tutorials for t.vect/t.rast.mapcalc | |
September 27 | Final evaluation |
Weekly Reports
Week 1 - 2012-05-31
What did I do this week?
- Studying Python-Lex-Yacc parsing tool.
- Getting familiar with PyGRASS.
- Working with the Backus Naur form of context free grammar.
- Create example programs for the vector algebra in PLY.
What will I be working on next week?
Implement the vector algebra GRASS module v.mapcalc with PLY and PyGRASS.
Did I meet with any stumbling blocks?
First I was a little bit confused about how PLY works. It took a while until I understood the principals and the functioning.
Week 2 - 2012-06-7
What did I do this week?
- Develop a first implementation of vector algebra in PLY.
- Create a new website on google code.
- Upload v.mapcalc module into the new repository.
What will I be working on next week?
Getting familiar with the GRASS GIS Temporal Framework API.
Did I meet with any stumbling blocks?
Some problems with the vector algebra lexer class for boolean operations.
Week 3 - 2012-06-14
What did I do this week?
- Fixed bugs and worked on comments for the v.mapcalc module.
- Reading the documentation for the GRASS GIS Temporal Framework API.
- Building up a concept for the temporal algebra together with my mentor.
What will I be working on next week?
Write example programs for the temporal algebra
Did I meet with any stumbling blocks?
The concept get considerably large and it was hard to design it clearly arranged and intuitive.
Week 4 - 2012-06-21
What did I do this week?
- Extended the v.mapcalc module with a command list class (Important for later use in preprocessing steps of the temporal algebra).
- Create a developer wiki page for the temporal algebra concept.
- Working on the concept.
- Writing first example programs, experience with the TGIS framework.
What will I be working on next week?
Start implementing the temporal algebra.
Did I meet with any stumbling blocks?
No major problem this week.
Week 5 - 2012-06-28
What did I do this week?
- Using PLY for lexical analysis of temporal expressions.
- Utilize TGIS methods to evaluate temporal selection expressions.
- Start to implement an intern map list structure to store generated map lists, derived from temporal expressions, independently from input type (Vector, Raster).
- Writing the structure for the temporal algebra and started to fill in the required methods.
What will I be working on next week?
Continue the implementation of the temporal algebra.
Did I meet with any stumbling blocks?
I try to keep track of the temporal algebra. Sometimes it gets very complex.
Week 6 - 2012-07-05
What did I do this week?
- Implement functions to compare space time datasets by their topology and to perform temporal selection on raster and vector datasets.
- Create Module t.select for temporal selection.
- Changed some functionalities in the temporal algebra concept.
What will I be working on next week?
Continue the implementation of the temporal algebra functions like temporal buffering, snapping and shifting.
Did I meet with any stumbling blocks?
No big Problems this week
Week 7 - 2012-07-12
What did I do this week?
- Implement functions for temporal buffering, snapping and shifting.
- Add global temporal variables into the algebra (td(), start_time, end_time, ...)
- Started to integrate conditional statements into the algebra.
What will I be working on next week?
This week I participate in the GRASS community sprint in Prague. Discussing and working intensively on the temporal algebra for the next six days.
Did I meet with any stumbling blocks?
Only minor problems.
Week 8 - 2012-07-19
What did I do this week?
- Participation in the GRASS community sprint in Prague.
- Discussing and working intensively on the temporal algebra.
- Add global temporal variables into the algebra (td(), start_time, end_time, ...)
- Implemented functions for if-statements in the temporal algebra.
- Implemented topological relationships for if-statements.
- Finished to implement the hash-operator (#) for map counting in conditional statements.
- New module t.select alpha version in repository ready for testing.
What will I be working on next week?
Testing and documentation of the GRASS module t.select. Start to integrate the vector operations into the temporal vector algebra.
Did I meet with any stumbling blocks?
Due to direct contact to GRASS developers at the meeting in Prague all problems could be solved.
Repository
The code for this project can be found in a svn repository at code.google: grass-gis-temporal-algebra