Database Reference
In-Depth Information
Projection of the space−time prism
Road network
q
p
Figure 5.4 A projection of a prism and a road network.
A trajectory on a road network
RN
is then a trajectory whose spatial projection
is in
RN
. In the remainder we consider a uniform speed limit
v
i
on the network
to construct the space-time prism between two sample times
t
i
and
t
i
+
1
.
Space-Time Prisms in Road Networks
Using space-time prisms on a road network is usually more involved than sim-
ply taking the intersection of a space-time prism representing unconstrained
movement and the road network. Consider, for instance, the projection of the
unconstrained space-time prism along the time axis onto the
xy
-plane. This
projection is an ellipse such that its foci are the points of departure and arrival,
that is,
p
and
q
. At a time
t
between two instants
t
p
and
t
q
, the object's distance
to
p
is at most
v
max
(
t
−
t
p
) and its distance to
q
is at most
v
max
(
t
q
−
t
). Adding
those distances gives
v
max
(
t
−
t
p
)
+
v
max
(
t
q
−
t
)
=
v
max
(
t
q
−
t
p
), which is con-
stant. Therefore, all possible points a moving object with speed limit
v
max
could
have visited must lie within this ellipse with foci
p
and
q
, and the sum of their
distances to
p
and
q
is less than or equal to
v
max
(
t
q
−
t
p
). Any trajectory that
touches the border of the ellipse and has more than two straight line segments
is longer than
v
max
(
t
q
−
t
p
) (see Figure
5.4
). This particular trajectory lies in
the ellipse and hence in the intersection of the unconstrained space-time prism
and the road network,
but it does not lie in the road network space-time prism
entirely
, because there are points on it that can be reached in time but fromwhich
the destination cannot be reached in time, and vice versa. Just suppose a case
where there is no path on the road network from a vertex
p
that reaches another
one
q in a given time interval
. The intersection of the space-time prism with the
road network would not be empty. However, the road network space-time prism
clearly is, because there is no way to reach
q
from
p
using the network.
To define space-time prisms on a road network, we need an appropriate
distance function on the network. This distance measure is derived from the
shortest-path distance
used in graph theory.
