Modeling and Querying History of Movement Discrete Model
Modeling and Querying History of Movement Discrete Model
4.3 A Discrete Model
Base Types
int Dint = int {}
real ...
string
bool
Time Type
instant Dinstant = real {}
Spatial Types
point trivial
points trivial
line a finite set of line segments (which may intersect in
end-points) abstract discrete The task: Define finite representations for all the types of the abstract model (and map these into data structures later).
A Discrete Model
not edge-disjoint edge-
disjoint a finite set of polygons, each with polygonal holes abstract discrete Seg = ... (def. of line segments)
Cycle = {S Seg | ... } (def. of simple polygon)
Face = {(c, H) | c Cycle, H Cycle, such that ...}
Dregion = {F Face | f1, f2 F f1 f2
edge-disjoint(f1, f2)} Spatial Types (cont.)
region
A Discrete Model
straightforward
interesting
trivial Type Constructors
a an ordered domain
range(a) A value is a finite set of disjoint, non-adjacent intervals over a. Each interval can be closed, open, or half-open
a a standard or a spatial type
moving(a) A value is a partial function f: Ainstant Aa
intime(a) A value is a pair from Ainstant ´ Aa
A Discrete Model
Representation of types moving(a): Represent the temporal development of the value of type a by decomposing the time dimension into a set of disjoint time intervals (“slices”) such that within each slice the development can be described by some “simple” function. Called the sliced representation.
A Discrete Model
BASE SPATIAL TEMPORAL moving
of abstract model replaced by
BASE SPATIAL UNIT const
UNIT ureal, upoint, upoints, uline, uregion
UNIT MAPPING mapping
in the discrete model.
abstract type discrete type
moving(int) mapping(const(int))
moving(string) mapping(const(string))
moving(bool) mapping(const(bool)) moving(real) mapping(ureal) moving(point) mapping(upoint) moving(points) mapping(upoints) moving(line) mapping(uline) moving(region) mapping(uregion) In terms of data types, the sliced representation is realized by a generic type constructor mapping applicable to unit types, where a unit value is a pair, consisting of a time interval and a description of a “simple” function.
A Discrete Model - Sketch of Definitions
Sliced representation (generic definition)
Let (V, <) a set with a total order.
Interval(V) =
{(s, e, lc, rc) | s, e V, lc, rc bool, s e, (s = e) (lc = rc = true)}
Temporal unit:
Unit(S) = Interval(Instant) S (S a set)
Mapping
A Discrete Model - Sketch of Definitions
Dureal = Interval(Instant)
Semantics (value at instant t):
Distance between two moving points:
Perimeter of a moving region:
Area of a moving region:
Not closed under derivative!
Real Units
A Discrete Model - Sketch of Definitions
Semantics (value at instant t):
Dupoint = Interval(Instant) MPoint Point Units
A Discrete Model - Sketch of Definitions
Semantics (value at instant t):
Points Units
A Discrete Model - Sketch of Definitions
First define a moving segment:
Region Units
A Discrete Model - Sketch of Definitions
value of the region type, i.e., mapping(uregion) consistent with region Region Units
Comments