Grass7/TemporalGISAlgebra

Temporal GIS Algebra for Raster and Vector Data

The idea is to implement a temporal GIS algebra to process space time datasets of type raster and vector, the new spatio-temporal datatypes in GRASS GIS 7. Space time datasets represent time series of raster, 3D raster and vector maps. The GRASS GIS temporal framework implements a snapshot approach, so that time and space are separated from each other. Hence, space time datasets are not truly 4 dimensional datatypes, time and space can only be processed separately from each other. The spatial capabilities of GRASS GIS are used to perform the spatial processing of the time stamped maps that are registered in the space time datasets. We use the modules r.mapcalc for raster processing and v.buffer, v.over , v.patch for vector map processing in the algebra. The temporal processing is provided by the GRASS GIS temporal framework that supports time intervals and time instances. Mixing time instance and time intervals as well as gaps, overlapping or inclusion of intervals and instances is possible. Hence this framework allows an arbitrary layout of the time dimension,

The only way to process several space time datasets with arbitrary temporal layout is to use their temporal relationships. Or more precisely, the temporal relationships of the time stamped maps that are registered in the space time datasets. The spatial operations between maps (sum, union, ...) can be performed after the temporal related maps are identified. This concept leads the design of the temporal GIS algebra. The algebra provides the functionality to define spatio-temporal operators that process time and space in a single expression.

Temporal Algebra

The temporal part of the temporal GIS algebra is designed to be used as is in the temporal vector algebra and the temporal raster algebra. Hence it works with space time datasets of any type (STRDS, STR3DS and STVDS). The algebra provides methods select maps from STDS based on their temporal relations. It is also possible to temporally shift maps, to create temporal buffer and to snap time instances to create a valid temporal topology. These operations can be assigned to space time datasets or to the results of operations between space time datasets.

Temporal selection

Here an example of the temporal algebra that simply selects parts of a space time dataset without processing raster or vector data:

We have defined the selection operator : that by default selects parts of a space time dataset that are temporally equal to parts of a second one. The following expression

C = A : B

means: Select all parts of space time dataset A that are equal to B and store it in space time dataset C. The parts are in this case time stamped maps. In addition we define the inverse selection operator !:, hence the following expression

C = A !: B

means: select all parts of space time time dataset A that are not equal to B and store it in space time dataset (STDS) C.

We have defined the operator {"topological relations", "temporal selection operator"} to perform selection with different temporal topology relations. Examples:

C = A {equals,:} B is exactly the same as C = A : B
C = A {equals,!:} B is exactly the same as C = A !: B

We can now define arbitrary topological relations using logical OR operator to connect them:

C = A {equals||during||overlaps,:} B

Select all parts of A that are equal B, during B or overlaps B.

Temporal buffer

Buffer time instances or time intervals:

buff_t(STDS, "time interval")

Example:

C = buff_t(A, "1 day")

Buffer all maps of STDS A with a temporal buffer of one day.

Temporal shift

Temporally shift all maps in a space time dataset by an interval:

tshift(STDS, "time interval")

Example:

tshift(A, "2 months")

Temporally shift all maps of space time dataset A by two months.

Temporally snap

Temporally snap time instances to its temporal nearest neighbor in the future and close gaps between time intervals.

tsnap(STDS)

The hash operator

It is of important interest how many maps are located in the time interval of a single map when processing two space time datasets. For this reason the hash operator # was introduced. In addition to the hash operator the temporal relation can be specified that should be analysed.

Example:

C = if(equal, A{contains,#}B > 2, A{contains,:}B)

This expression selects all maps from A that temporally contains at least 2 maps from B and stores them in space time dataset C. The leading equal statement in the if condition specifies the temporal relation between the if and then part of the if expression. This is very important, so we do not need to specify a global time reference (a space time dataset) for temporal processing.

Temporal Operators

The temporal algebra defines temporal operators that can be combined later with spatial operators to perform spatio-temporal operations. The temporal operators process the time instances and intervals of temporal related maps.

AND             &       Intersection 
OR              |       Union
DISJOINT OR     +       Disjoint union
LEFT REFERENCE  =       Use the time stamp of the left space time dataset

For example we can compute the intersection, union or disjoint union from time stamps of maps that temporally overlap, or we can just keep the time stamp of the left STDS.

All supported operators and functions are documented below.

Temporal Vector Algebra

The temporal vector algebra includes all functions from the temporal algebra and adds spatial Boolean and buffer operations that can be performed on temporal related vector maps that are registered in space time vector datasets.

Spatio-Temporal Operators

These are the spatial operators that are supported:

AND             &       Intersection            (v.overlay operator=and)
OR              |       Union                   (v.overlay operator=or)
DISJOINT OR     +       Disjoint union          (v.patch)
XOR             ^       Symmetric difference    (v.overlay operator=xor)
NOT             ~       Complement              (v.overlay operator=not)

We combine the temporal topology relations, the temporal operators and the spatial operators to create spatio-temporal operators:

{"list of temporal relations", "temporal operator" "spatial operator"} 

The spatial operator can be used stand-alone. In this case the temporal topology relation "equal" and the temporal operator "left reference =" is assumed and used as default. This allows the convenient use of the spatial operators in case of space time vector datasets with equal time stamps.

Example: Compute the spatial intersection between maps of STVDS A and B that are temporally equal, resulting spatial intersection maps are stored in C with time stamps from A:

C = A & B

Compute the spatio-temporal intersection between maps of STVDS A and B that temporally overlap, resulting spatial intersection maps are stored in C with new time stamps resulting from temporal intersection:

C = A {overlap,&&} B

Perform a spatial union and a temporal disjoint union between all maps of STVDS A and B that are temporally equal or overlap and are later than 1990, resulting spatial union maps are stored in C with new time stamps resulting from temporal disjoint union:

C = if(start_year() > 1990, A {equal,overlap,+|} B)

The temporal vector algebra provides point, line and area buffer functions in addition to the operators.

All supported operators and functions are documented below.

Temporal Raster Algebra

The temporal raster algebra uses all operators and functions of the temporal algebra and adds a subset of the arithmetic operators and functions from r.mapcalc. New spatio-temporal operators are defined that include temporal topology relations, temporal operators and arithmetic operators.

Examples: Create the sum of all maps from STRDS A and B that have equal time stamps and store the new maps in STRDS C:

C = A + B

Same expression with explicit definition of the temporal topology relation and temporal operators:

C = A {equal,=+} B

Select all cells from STRDS B with equal temporal relations to STRDS A, if the cells of A are in the range of [100.0, 1600] of time intervals that have more then 30 days (Jan, Mar, Mai, Jul, Aug, Oct, Dec):

C = if(A > 100 && A < 1600 && td(A) > 30, B)

Same expression with explicit definition of the temporal topology relation and temporal operators:

C = if(equal, A > 100 && A < 1600 {equal,&&} td(A) > 30, B)

Compute the recharge in meter per second for all cells of precipitation STRDS "Prec" if the mean temperature specified in STRDS "Temp" is higher than 10 degrees. Computation is performed if STRDS "Prec" and "Temp" have equal time stamps. The number of days or fraction of days per interval is computed using the td() function that has as argument the STRDS "Prec":

C = if(Temp > 10.0, Prec / 3600.0 /24.0 / td(Prec))

Same expression with explicit definition of the temporal topology relation and temporal operators:

C = if(equal, Temp > 10.0, Prec / 3600.0 / 24.0 {equal,=/} td(Prec))

Compute the mean value of all maps from STRDS A that are located during time intervals of STRDS B if more than one map of A is contained in an interval of B, use A otherwise, the resulting time intervals are either from B or A:

C = if(B {contain,#} A > 1, (B {contain, =+} A - B) / (B {contain,#} A), A)

Same expression with explicit definition of the temporal topology relation and temporal operators:

C = if(equal, B {contain,#} A > 1, (B {contain, =+} A {equal, =-} B) {equal,=/} (B {contain,#} A), A)

All supported operators and functions are documented below.

Overview of all supported spatio-temporal operators and functions

Temporal topology relations

equals            A ------
                  B ------

during            A  ---- 
                  B ------

contains          A ------
                  B  ---- 

starts            A ----
                  B ------

started           A ------
                  B ----

finishs           A   ---- 
                  B ------

finished          A ------
                  B   ----

precedes          A ----
                  B     ----

follows           A     ----
                  B ----

overlapped        A   ------
                  B ------

overlaps          A ------
                  B   ------

over              booth overlaps and overlapped

The relations must be read A is related to B, like - A equals B - A is during B - A contains B

Topological relations must be specified in {} parentheses

A {equals} B

Topological relations are always combined with other temporal operators in the {} parentheses

Temporal operators

Temporal operators that work on time intervals and instances of maps in space time datasets:

Intersection &

Examples with time intervals a and b:

 c <- a & b
  a ------                              
  b  ----                               
  c  ----

  a ----
  b   ----
  c   --

  a ---
  b    ---
  c

Union |

Examples with time intervals a and b:

c <- a | b
  a ------                              
  b  ----                               
  c ------

  a ----
  b   ----
  c ------

  a ---
  b    ---
  c ------

  a ---
  b     ---
  c

Disjoint Union +

Examples with time intervals a and b:

 c <- a + b
  a ------                              
  b  ----                               
  c ------

  a ----
  b   ----
  c ------

  a ---
  b    ---
  c ------

  a ---
  b     ---
  c -------

Left Reference =

Examples with time intervals a and b:

 c <- a = b
  a ------                              
  b  ----                               
  c ------ 

  a ----
  b   ----
  c ----  

  a ---
  b    ---
  c ---   

  a ---
  b     ---
  c ---

The = operator ignores indexing operators for space time datasets: A[i]

Temporal selection operators to select parts of space time datasets:

Selection :
Inverse selection !:

Temporal operators have no precedence.

Examples:

  • Select all maps from space time dataset A that have equal time intervals with space time dataset B and store them in space time datasets C.

   C = A : B
   C = A {:} B
   C = A {equals,:} B
  • Select all maps from space time dataset A that have unequal time intervals with space time dataset B and store them in space time datasets C.

   C = A !: B
   C = A {!:} B
   C = A {equals,!:} B
  • Select all maps from space time dataset A that are during time intervals of space time dataset B and store them in space time datasets C.

   C = A {during,:} B
  • Select all maps from space time dataset A that are during B and during C and during D.
   E = A {during,:} B {during,:} C {during,:} D

Operator number of maps in interval
Number of maps #

Compute the number of maps from space time dataset B that are during the time intervals of maps from space time dataset A.

A{contains,#}B

This will return a list of integers (scalars) corresponding to the maps of A that contain maps from B.

Logical operators

Logical operators:

Symbol  description             precedence

  ==    equal                   3
  !=    not equal               3
  >     greater than            3
  >=    greater than or equal   3
  <     less than               3
  <=    less than or equal      3
  &&    and                     4
  ||    or                      4

Combination of temporal and logical operators:

 -------------------------------------------------
|   |  && |  || |  == |  != |  <= |  >= |  < |  > |
|---|-----|-----|-----|-----|-----|-----|----|----|
| & | &&& | &|| | &== | &!= | &<= | &>= | &< | &> |
| | | |&& | ||| | |== | |!= | |<= | |>= | |< | |> |
| + | +&& | +|| | +== | +!= | +<= | +>= | +< | +> |
| = | =&& | =|| | === | =!= | =<= | =>= | =< | => |
 -------------------------------------------- ----

Temporal functions

Note a and b can either be space time datasets or expressions.

if                      decision option
  if(if, then, else)
  if(x, a)              a if x not 0; temporal topological relation between if and then is equal
  if(x, a, b)           a if x not 0, b otherwise; temporal topological relation between if, then and else is equal
  if(topo, x, a)        a if x not 0; temporal topological relation between if and then is explicit specified by topo
  if(topo, x, a, b)     a if x not 0, b otherwise; temporal topological relation between if, then and else is explicit specified by topo

buff_t(a, size)         Buffer stds a with granule ("1 month" or 5)
tshift(a, size)         Shift stds a with granule ("1 month" or 5)
tsnap(a)                Snap time instances and intervals of stds a

td(a)                   Returns a list of time intervals of stds a

start_time()            Start time as HH::MM:SS
start_date()            Start date as yyyy-mm-DD
start_datetime()        Start datetime as yyyy-mm-DD HH:MM:SS
end_time()              End time as HH:MM:SS
end_date()              End date as yyyy-mm-DD
end_datetime()          End datetime as  yyyy-mm-DD HH:MM

start_doy()             Day of year (doy) from the start time [1 - 366]
start_dow()             Day of week (dow) from the start time [1 - 7], the start of the week is Monday == 1
start_year()            The year of the start time [0 - 9999]
start_month()           The month of the start time [1 - 12]
start_week()            Week of year of the start time [1 - 54]
start_day()             Day of month from the start time [1 - 31]
start_hour()            The hour of the start time [0 - 23]
start_minute()          The minute of the start time [0 - 59]
start_second()          The second of the start time [0 - 59]
end_doy()               Day of year (doy) from the end time [1 - 366]
end_dow()               Day of week (dow) from the end time [1 - 7], the start of the week is Monday == 1
end_year()              The year of the end time [0 - 9999]
end_month()             The month of the end time [1 - 12]
end_week()              Week of year of the end time [1 - 54]
end_day()               Day of month from the start time [1 - 31]
end_hour()              The hour of the end time [0 - 23]
end_minute()            The minute of the end time [0 - 59]
end_second()            The second of the end time [0 - 59]            

Examples:

Select all maps from space time dataset A that have equal time stamps with space time dataset B and C and are ealier that Jan. 1. 2005 and store them in space time dataset D.

D = if(start_date() < "2005-01-01", A : B : C)

Temporal Vector Algebra

Boolean vector operations:

AND             &       Intersection            (v.overlay operator=and)
OR              |       Union                   (v.overlay operator=or)
DISJOINT OR     +       Disjoint union          (v.patch)
XOR             ^       Symmetric difference    (v.overlay operator=xor)
NOT             ~       Complement              (v.overlay operator=not)

Vector functions:

buff_p(a, size)         Buffer the points of all maps from space time vector dataset a with size 
buff_l(a, size)         Buffer the lines of all maps from space time vector dataset a with size 
buff_a(a, size)         Buffer the areas of all maps from space time vector dataset a with size 

Examples:

  • Create an intersection between all maps of space time dataset A and B that have equal time stamps.
   C = A & B
   C = A {&} B
   C = A {=&} B
   C = A {equals,=&} B

  • Question: Meeting of two animals that occur when the distance between two sea elephants is less than 10 meters? Space time vector dataset A and B contains the measured positions and time instances/intervals of two sea elephants. The granularity of the space time vector datasets is 1h. We create a new space time vector dataset C that contains the spatio-temporal intersections of the positions of the sea elephants.
   C = buff_p(buff_t(A, "2 hours"), 5) {over||equals,&&} buff_p(buff_t(B, "2 hours"), 5)

Combinations of temporal and vector operators

 ----------------------------
|   |  & |  | |  ^ |  ~ |  + |
|---|----|----|----|----|----|
| & | && | &| | &^ | &~ | &+ |
| | | |& | || | |^ | |~ | |+ |
| + | +& | +| | +^ | +~ | ++ |
| = | =& | =| | =^ | =~ | =+ |
 ----------------------------

Temporal Raster Algebra

Arithmetic Operators:

Symbol  description     precedence

  %     modulus         1
  /     division        1
  *     multiplication  1
  +     addition        2
  -     subtraction     2

Raster functions:

abs(x)                  return absolute value of x
foat(x)                 convert x to foating point
if decision options:
  if(x)                 1 if x not zero, 0 otherwise
  if(x,a)               a if x not zero, 0 otherwise
  if(x,a,b)             a if x not zero, b otherwise
int(x)                  convert x to integer [ truncates ]
log(x)                  natural log of x
log(x,b)                log of x base b
max(x,y[,z...])         largest value of those listed
median(x,y[,z...])      median value of those listed
min(x,y[,z...])         smallest value of those listed
round(x)                round x to nearest integer
sqrt(x)                 square root of x
tan(x)                  tangent of x (x is in degrees)
not(x)			1 if x is zero, 0 otherwise
pow(x,y)		x to the power y
rand(a,b)		random value x : a <= x < b
round(x)		round x to nearest integer
sin(x)			sine of x (x is in degrees)
sqrt(x)			square root of x
tan(x)			tangent of x (x is in degrees)
xor(x,y)		exclusive-or (XOR) of x and y
isnull(x)              check if x = NULL

Internal variables:

row()                   current row of moving window
col()                   current col of moving window
x()                     current x-coordinate of moving window
y()                     current y-coordinate of moving window
ewres()                 current east-west resolution
nsres()                 current north-south resolution
null()                  NULL value

Combination of temporal and arithmetical raster operators:

 ----------------------------
|   |  % |  / |  * |  - |  + |
|---|----|----|----|----|----|
| & | &% | &/ | &* | &- | &+ |
| | | |% | |/ | |* | |- | |+ |
| + | +% | +/ | +* | +- | ++ |
| = | =% | =/ | =* | =- | =+ |
 ----------------------------