Modeling and Querying History of Movement Algorithms for operations
(Part 2)
Modeling and Querying History of Movement Algorithms for operations
(Part 2)
Refinement Partition
algorithm compute_refinement_partition
Input: a moving value, MV _1= <(i_1 , iuf_1), (i_2, iuf_2), …, (i_m, iuf_m)>,
where i_i is ith unit definition interval and iuf_i is ith unit function
a moving value, MV_2 = <(j_1, juf_1), (j2, juf_2), …, (j_n, juf_n)>,
where j_i is ith unit definition interval and juf_i is ith unit function
Output: a refinement partition of MV_1, RMV_1 = <(k_1 , riuf_1), (k_2, riuf_2), …, (k_p, riuf_p)
a refinement partition of MV_2, RMV_2 = <(k_1, rjuf_1), (k_2, rjuf_2), …, (k_p, rjuf_p)>
Idea:
By parallel scan, break the unit definition intervals of both moving values
so that a unit from MV_1 and a unit from MV_2 are either:
defined on equal definition time intervals or
defined on disjoint definition time intervals
Unit functions are not modified.
2. Two units defined on equal definition time intervals form a pair.
Any algorithm on two moving values is now reduced to an algorithm on two sequences of pairs.
MV_1 MV_2 Parallel scan RMV_1 RMV_2
Inside operation: Idea
Signature inside: mpoint x mregion mbool algorithm inside
Input: a moving point value, MP = , where mpu_i is ith unit
a moving region value, MR = , where mru_i is ith unit
Output: a moving boolean value, MB = , where mbu_i is ith unit
Idea of the algorithm:
Compute refinement partitions, RMP and RMR, of MP and MR by a parallel scan.
For each pair of units from RMP and RMR, (mpu_i, mru_i) , with unit definition time interval i :
a) Each intersection between mpu and mru is represented as a pair (t, action),
where t is the time of the intersection and action {enter, leave}.
Compute all k intersections.
The actions are alternating by time.
Compute a (sub)sequence of k+1 units from MB, based on the list of actions.
Inside operation: Pseudocode
Signature inside: mpoint x mregion mbool algorithm inside
Input: a moving point value, MP = , where mpu_i is ith unit
a moving region value, MR = , where mru_i is ith unit
Output: a moving boolean value, MB = , where mbu_i is ith unit
MB: = ;
(RMP, RMR) := compute_refinement_partition(MP, MR);
for each (mpu_i , mru_i) (RMP, RMR) do
:= upoint_uregion_inside(mpu_i, mru_i);
MB := MB ;
algorithm upoint_uregion_inside
Input: a moving point unit, mpu_i = (i, mpuf_i),
where i = [s, e] is the unit definition time interval and mpuf_i is the unit function
a moving region unit, mru_i = (i, mruf_i),
where i = [s, e] is the unit definition time interval and mruf_i is the unit function
Output: a sequence of moving boolean units,
[Body of the algoithm upoint_uregion_inside on the next slide]
Inside operation: Pseudocode
Signature inside: mpoint x mregion mbool algorithm upoint_uregion_inside
Input: a moving point unit, mpu_i = (i, mpuf_i),
where i = [s, e] is the unit definition time interval and mpuf_i is the unit function
a moving region unit, mru_i = (i, mruf_i),
where i = [s, e] is the unit definition time interval and
mruf_i is the unit function with the number of moving segments s_i
Output: a sequence of moving boolean units,
if not are3D_MBBs_intersecting(mpu_i, mru_i) then return <([s, e], false)>;
<(t_1, a_1), …, (t_(k_i), a_(k_i))> := sort_by_time (find_intersections (mpuf_i, mruf_i));
if k = 0 then
if mpu_i(s) isInside mru_i(s) then return <([s, e], true)>;
else return <([s, e], false)>;
else
if a_1 = leave then return <([s, t_1], true), ((t_1, t_2), false), ([t_2, t_3], true), …>
else return <([s, t_1], false), ((t_1, t_2), true), ([t_2, t_3], false), …>
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm upoint_uregion_inside
Input: a moving point unit, mpu_i = (i, mpuf_i),
where i = [s, e] is the unit definition time interval and mpuf_i is the unit function
a moving region unit, mru_i = (i, mruf_i),
where i = [s, e] is the unit definition time interval and
mruf_i is the unit function with the number of moving segments s_i
Output: a sequence of moving boolean units,
if not are3D_MBBs_intersecting(mpu_i, mru_i) then return <([s, e], false)>;
<(t_1, a_1), …, (t_(k_i), a_(k_i))> := sort_by_time (find_intersections (mpuf_i, mruf_i));
if k = 0 then
if mpu_i(s) isInside mru_i(s) then return <([s, e], true)>;
else return <([s, e], false)>;
else
if a_1 = leave then return <([s, t_1], true), ((t_1, t_2), false), ([t_2, t_3], true), …>
else return <([s, t_1], false), ((t_1, t_2), true), ([t_2, t_3], false), …>
O (s_i)
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm upoint_uregion_inside
Input: a moving point unit, mpu_i = (i, mpuf_i),
where i = [s, e] is the unit definition time interval and mpuf_i is the unit function
a moving region unit, mru_i = (i, mruf_i),
where i = [s, e] is the unit definition time interval and
mruf_i is the unit function with the number of moving segments s_i
Output: a sequence of moving boolean units,
if not are3D_MBBs_intersecting(mpu_i, mru_i) then return <([s, e], false)>;
<(t_1, a_1), …, (t_(k_i), a_(k_i))> := sort_by_time (find_intersections (mpuf_i, mruf_i));
if k = 0 then
if mpu_i(s) isInside mru_i(s) then return <([s, e], true)>;
else return <([s, e], false)>;
else
if a_1 = leave then return <([s, t_1], true), ((t_1, t_2), false), ([t_2, t_3], true), …>
else return <([s, t_1], false), ((t_1, t_2), true), ([t_2, t_3], false), …>
O (k_i log k_i) O (s_i)
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm upoint_uregion_inside
Input: a moving point unit, mpu_i = (i, mpuf_i),
where i = [s, e] is the unit definition time interval and mpuf_i is the unit function
a moving region unit, mru_i = (i, mruf_i),
where i = [s, e] is the unit definition time interval and
mruf_i is the unit function with the number of moving segments s_i
Output: a sequence of moving boolean units,
if not are3D_MBBs_intersecting(mpu_i, mru_i) then return <([s, e], false)>;
<(t_1, a_1), …, (t_(k_i), a_(k_i))> := sort_by_time (find_intersections (mpuf_i, mruf_i));
if k = 0 then
if mpu_i(s) isInside mru_i(s) then return <([s, e], true)>;
else return <([s, e], false)>;
else
if a_1 = leave then return <([s, t_1], true), ((t_1, t_2), false), ([t_2, t_3], true), …>
else return <([s, t_1], false), ((t_1, t_2), true), ([t_2, t_3], false), …>
O (s_i) O (k_i log k_i) O (s_i)
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm upoint_uregion_inside
Input: a moving point unit, mpu_i = (i, mpuf_i),
where i = [s, e] is the unit definition time interval and mpuf_i is the unit function
a moving region unit, mru_i = (i, mruf_i),
where i = [s, e] is the unit definition time interval and
mruf_i is the unit function with the number of moving segments s_i
Output: a sequence of moving boolean units,
if not are3D_MBBs_intersecting(mpu_i, mru_i) then return <([s, e], false)>;
<(t_1, a_1), …, (t_(k_i), a_(k_i))> := sort_by_time (find_intersections (mpuf_i, mruf_i));
if k = 0 then
if mpu_i(s) isInside mru_i(s) then return <([s, e], true)>;
else return <([s, e], false)>;
else
if a_1 = leave then return <([s, t_1], true), ((t_1, t_2), false), ([t_2, t_3], true), …>
else return <([s, t_1], false), ((t_1, t_2), true), ([t_2, t_3], false), …>
O (s_i) O (k_i ) O (k_i log k_i) O (s_i)
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm upoint_uregion_inside
Input: a moving point unit, mpu_i = (i, mpuf_i),
where i = [s, e] is the unit definition time interval and mpuf_i is the unit function
a moving region unit, mru_i = (i, mruf_i),
where i = [s, e] is the unit definition time interval and
mruf_i is the unit function with the number of moving segments s_i
Output: a sequence of moving boolean units,
if not are3D_MBBs_intersecting(mpu_i, mru_i) then return <([s, e], false)>;
<(t_1, a_1), …, (t_(k_i), a_(k_i))> := sort_by_time (find_intersections (mpuf_i, mruf_i));
if k = 0 then
if mpu_i(s) isInside mru_i(s) then return <(i, true)>;
else return <(i, false)>;
else
if a_1 = leave then return <([s, t_1], true), ((t_1, t_2), false), ([t_2, t_3], true), …>
else return <([s, t_1], false), ((t_1, t_2), true), ([t_2, t_3], false), …>
O (s_i) O (k_i log k_i+ s_i) O (k_i ) O (k_i log k_i) O (s_i)
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm inside
Input: a moving point value, MP = , where mpu_i is ith unit
a moving region value, MR = , where mru_i is ith unit
Output: a moving boolean value, MB = , where mbu_i is ith unit
MB: = ;
(RMP, RMR) := compute_refinement_partition(MP, MR);
for each (mpu_i , mru_i) (RMP, RMR) do
:= upoint_uregion_inside(mpu_i, mru_i);
MB := MB ;
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm inside
Input: a moving point value, MP = , where mpu_i is ith unit
a moving region value, MR = , where mru_i is ith unit
Output: a moving boolean value, MB = , where mbu_i is ith unit
MB: = ;
(RMP, RMR) := compute_refinement_partition(MP, MR);
for each (mpu_i , mru_i) (RMP, RMR) do
:= upoint_uregion_inside(mpu_i, mru_i);
MB := MB ;
O (m + n)
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm inside
Input: a moving point value, MP = , where mpu_i is ith unit
a moving region value, MR = , where mru_i is ith unit
Output: a moving boolean value, MB = , where mbu_i is ith unit
MB: = ;
(RMP, RMR) := compute_refinement_partition(MP, MR);
for each (mpu_i , mru_i) (RMP, RMR) do
:= upoint_uregion_inside(mpu_i, mru_i);
MB := MB ;
O (k_i log k_i + s_i) O (m + n)
Inside operation: Complexity
Signature inside: mpoint x mregion mbool algorithm inside
Input: a moving point value, MP = , where mpu_i is ith unit
a moving region value, MR = , where mru_i is ith unit
Output: a moving boolean value, MB = , where mbu_i is ith unit
MB: = ;
(RMP, RMR) := compute_refinement_partition(MP, MR);
for each (mpu_i , mru_i) (RMP, RMR) do
:= upoint_uregion_inside(mpu_i, mru_i);
MB := MB ;
O (k_i log k_i + s_i) O (m + n) O (m + n) + O (K log k_max + S), where:
K = k_1 + k_2 + … + k_p (i.e., total number of intersections) ,
k_max is maximum number of intersections per unit,
S = s_1 + s_2 + … + s_p (i.e., total number of moving segments in RMR)
Similar operations
Signature inside: mpoint x mregion mbool
Input: moving values
Output: construct a moving boolean value
at: mpoint x region mpoint
mregion x point mpoint
Convert input parameters: static region (point) into moving region (point)
Ouput: do not construct a moving boolean, use an argument moving point
intersection: mpoint x mregion mpoint
Output: do not construct a moving boolean, use an argument moving point
intersection of 3D lines and polyhedra algorithm inside
Input: a moving point value, MP = , where mpu_i is ith unit
a moving region value, MR = , where mru_i is ith unit
Output: a moving boolean value, MB = , where mbu_i is ith unit
Idea of the algorithm:
Compute refinement partitions, RMP and RMR, of MP and MR by a parallel scan.
For each pair of units from RMP and RMR, (mpu_i, mru_i) , with unit definition time interval i :
a) Each intersection between mpu and mru is represented as a pair (t, action),
where t is the time of the intersection and action {enter, leave}.
Compute all k intersections.
The actions are alternating by time.
Compute a (sub)sequence of k+1 units from MB, based on the list of actions.
At operation: Idea
Signature at: mpoint x points mpoint algorithm at
Input: a moving point value, MP = , where mpu_i is ith unit
a points value, MPP = , where pp_i is ith point
Output: a moving point value, RMP = , where rmpu_i is ith unit
Idea of the algorithm:
For each unit of MP , mpu_i :
Perform a binary search on MPP with the minimum x-coordinate of the unit projection minimum bounding box of mpu_i, pmbb_i .
This will find the first point of MPP that may be inside pmbb_i , pp_f.
b) Starting from pp_f, for each point of MPP, pp_j, check if pp_j is inside pmbb_i .
If so, check if pp_j intersects with mpu_i.
If so, then create a result unit, rmpu_j, which is mpu_i restricted to the intersection time.
2. Sort the resulting units.
At operation: Idea
Signature at: mpoint x points mpoint pp_f algorithm at
Input: a moving point value, MP = , where mpu_i is ith unit
a points value, MPP = , where pp_i is ith point
Output: a moving point value, RMP = , where rmpu_i is ith unit
Idea of the algorithm:
For each unit of MP , mpu_i :
Perform a binary search on MPP with the minimum x-coordinate of the unit projection minimum bounding box of mpu_i, pmbb_i .
This will find the first point of MPP that may be inside pmbb_i , pp_f.
b) Starting from pp_f, for each point of MPP, pp_j, check if pp_j is inside pmbb_i .
If so, check if pp_j intersects with mpu_i.
If so, then create a result unit, rmpu_j, which is mpu_i restricted to the intersection time.
2. Sort the resulting units.
At operation: Idea
algorithm at
Input: a moving point value, MP = , where mpu_i is ith unit
a points value, MPP = , where pp_i is ith point
Output: a moving point value, RMP = , where rmpu_i is ith unit
Idea of the algorithm:
For each unit of MP , mpu_i :
Perform a binary search on MPP with the minimum x-coordinate of the unit projection minimum bounding box of mpu_i, pmbb_i .
This will find the first point of MPP that may be inside pmbb_i , pp_f.
b) Starting from pp_f, for each point of MPP, pp_j, check if pp_j is inside pmbb_i .
If so, check if pp_j intersects with mpu_i.
If so, then create a result unit, rmpu_j, which is mpu_i restricted to the intersection time.
2. Sort the resulting units.
Signature at: mpoint x points mpoint pp_f
At operation: Pseudocode
Signature at: mpoint x points mpoint algorithm at
Input: a moving point value, MP = , where mpu_i is ith unit
a points value, MPP = , where pp_i is ith point
Output: a moving point value, RMP = , where rmpu_i is ith unit
RMP: = ;
for each (i, mpuf_i, pmbb_i) MP, where pmbb_i = (x_min, x_max, y_min, y_max) do
pp_f := binary_search (MPP, ” pp_f x_min”);
for each pp_j such that pp_j MPP and pp_j pp_f and pp_j x_max do
if y_min pp_j y_max then
t: = intersection_time (mpu_i, pp_j);
if t then RMP: = RMP <([t,t], mpuf_i>;
sort_by_time(RMP);
return RMP;
pp_f
At operation: Complexity
algorithm at
Input: a moving point value, MP = , where mpu_i is ith unit
a points value, MPP = , where pp_i is ith point
Output: a moving point value, RMP = , where rmpu_i is ith unit
RMP: = ;
for each (i, mpuf_i, pmbb_i) MP, where pmbb_i = (x_min, x_max, y_min, y_max) do
pp_f := binary_search (MPP, ” pp_f x_min”);
for each pp_j such that pp_j MPP and pp_j pp_f and pp_j x_max do
if y_min pp_j y_max then
t: = intersection_time (mpu_i, pp_j);
if t then RMP: = RMP <([t,t], mpuf_i>;
sort_by_time(RMP);
return RMP;
Signature at: mpoint x points mpoint O (log n) pp_f
Comments