= Temporal GIS Algebra for Raster and Vector Data =

== Introduction ==

=== Temporal Algebra ===

The idea is to implement a temporal algebra to process space time datasets, 
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 processes 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. 
Hence the modules r.mapcalc for raster processing and v.buffer, v.over , v.patch for vector map processing are used. 
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 algebra. The algebra must provide the functionality to define spatio-temporal 
operators that process time and space in a single expression.

It should be possible to select maps based on their temporal relations. It must be possible to temporally shift the time stamps, 
to create temporal buffer and to snap time instances to create a valid temporal topology. 
Hence many operations that are common in spatial processing should have an equivalent in the temporal processing.

==== Temporal selection ====

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

We define a selection operator ''':''' that by default selects parts of a space time dataset that are temporally equal to parts of a second, hence 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 defined the {topological relations, selection operator} 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 to connect them:

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

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

In addition we define a temporal functions:

==== 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 expression. This is very important, so we do not need to specify a time reference for temporal processing.
= Overview of all temporal algebra elements =

== 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           :'''[[BR]]
'''  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 {=:} B
   C = A {equals,:} 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 {=!:} B
   C = A {equals,!:} 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. Use
   the time interval/instances of A in C.
  
{{{
   C = A {during,:} B
   C = A {during,=:} 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. The maps
   in C will have different time intervals as A or B using the union operator.
   Hence they are unions between time intervals of A and B.
  
{{{
   C = A {during,|:} B
}}}

 * Select all maps from space time dataset A
   that are during B and during C and during D.
   Store the resulting list of maps using the timer intervals/instances
   of A in E.

{{{
   E = A {during,=:} B {during,=:} C {during,=:} D
}}}

Operator number of maps in interval  [[BR]]
'''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.


== Combination of temporal operators ==

{{{
 --------------
|   |  : |  !: |
|---|- --|-----|
| & | &: | &!: |
| | | |: | |!: |
| + | +: | +!: |
| = | =: | =!: |
 --------------
}}}


== Logical operators ==

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

}}}

== Temporal functions ==

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

{{{
if                      decision option
  if(x, a)              a if x not 0
  if(x, a, b)           a if x not 0, b otherwise

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

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{equals,=:}B{equals,=:}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
}}}

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
}}}

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:

{{{
 ---------------------------------------
|   |  : |  !: |  % |  / |  * |  - |  + |
|---|----|-----|----|----|----|----|----|
| & | &: | &!: | &% | &/ | &* | &- | &+ |
| | | |: | |!: | |% | |/ | |* | |- | |+ |
| + | +: | +!: | +% | +/ | +* | +- | ++ |
| = | =: | =!: | =% | =/ | =* | =- | =+ |
 ---------------------------------------
}}}

Combination of temporal and logical raster operators:

{{{
 ------------------------------------------------
|   |  : |  !: |  == |  != |  <= |  >= |  < |  > |
|---|----|-----|-----|-----|-----|-----|----|----|
| & | &: | &!: | &== | &!= | &<= | &>= | &< | &> |
| | | |: | |!: | |== | |!= | |<= | |>= | |< | |> |
| + | +: | +!: | +== | +!= | +<= | +>= | +< | +> |
| = | =: | =!: | === | =!= | =<= | =>= | =< | => |
 ------------------------------------------- ----
}}}

Note the combination of temporal and logical operators is only
possible in reference time mode.