294
Alminas ˇ
Civilis, Christian S. Jensen, and Stardas Pakalnis
be assumed to be moving on main roads most of the time. This approach thus first
connects polylines while disregarding side streets, termed “tails,” and it only subsequently takes the tails into account.
To be more precise, a polyline pl in a set of polylines rn is a tail if at least one
delimiting point of pl is not connected to any delimiting point of any other polyline in
rn. Tails are also termed “first-level tails.” The ith level tails in rn are those polylines
that are tails in the set obtained by subtracting all tails at lower levels than i from rn.
A few observations are in order. If a road network has a purely hierarchical structure, each polyline is a tail at some level. Polylines that belong to a circular structure
in a road network, that is, a structure where each constituent polyline is connected at
both ends, are not tails. A highest tail level is assigned to all non-tail polylines. The
ranking is based on the tail level.
Direction-based Approach
The last approach takes into account the directions of the candidate polylines at the
connection points. The idea is that moving objects are expected to prefer to be moving as directly as possible toward their destinations, which means that they will tend
to move as straight as possible and by making as few turns as possible.
This approach thus gives preference to polylines that continue in the same
direction as much as possible when extending a polyline. Put differently, preference
is given to polylines with a direction at a connection point that has as small an angle
as possible with respect to the direction of the polyline to be extended, again at the
connection point.
Figure 13.3 explains this further. The property angle denotes the angle between
the polyline being extended and a candidate for use in the extension. The figure contains two such candidates and thus has two angles. Specifically, the line segment at
the connection point of the polyline to be extended is itself extended toward the candidate polyline. This extension corresponds to a straight extension of the polyline’s
line segment at the connection point. The property angle is then the angle between
the extended line segment and the line segment of the candidate polyline at the connection point. A small angle is thus preferable.
angle B
angle A
B
A
Fig. 13.3. The angle property between polylines
Alminas ˇ
Civilis, Christian S. Jensen, and Stardas Pakalnis
be assumed to be moving on main roads most of the time. This approach thus first
connects polylines while disregarding side streets, termed “tails,” and it only subsequently takes the tails into account.
To be more precise, a polyline pl in a set of polylines rn is a tail if at least one
delimiting point of pl is not connected to any delimiting point of any other polyline in
rn. Tails are also termed “first-level tails.” The ith level tails in rn are those polylines
that are tails in the set obtained by subtracting all tails at lower levels than i from rn.
A few observations are in order. If a road network has a purely hierarchical structure, each polyline is a tail at some level. Polylines that belong to a circular structure
in a road network, that is, a structure where each constituent polyline is connected at
both ends, are not tails. A highest tail level is assigned to all non-tail polylines. The
ranking is based on the tail level.
Direction-based Approach
The last approach takes into account the directions of the candidate polylines at the
connection points. The idea is that moving objects are expected to prefer to be moving as directly as possible toward their destinations, which means that they will tend
to move as straight as possible and by making as few turns as possible.
This approach thus gives preference to polylines that continue in the same
direction as much as possible when extending a polyline. Put differently, preference
is given to polylines with a direction at a connection point that has as small an angle
as possible with respect to the direction of the polyline to be extended, again at the
connection point.
Figure 13.3 explains this further. The property angle denotes the angle between
the polyline being extended and a candidate for use in the extension. The figure contains two such candidates and thus has two angles. Specifically, the line segment at
the connection point of the polyline to be extended is itself extended toward the candidate polyline. This extension corresponds to a straight extension of the polyline’s
line segment at the connection point. The property angle is then the angle between
the extended line segment and the line segment of the candidate polyline at the connection point. A small angle is thus preferable.
angle B
angle A
B
A
Fig. 13.3. The angle property between polylines