hul 2 00s.
h
ygon
Node
2
3
0
OGY
n tables
ve been
rdinates
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B-YF. Istanbul 2004
of the nodes and identified points, the coordinate sets of edges.
Table 3 describes the structure of the input data.
Coordinates | Coordinate Set of Coordinates of
of Nodes Edges
Node ID Edge ID
Identified Points
Identified Point ID
x coordinate | The coordinate sets x coordinate
y coordinate of points in one y coordinate
z coordinate edge z coordinate
Table 3 Structures of Input Data
To build Edge-Node relation table, the essential idea is coordinate
matching. If the coordinates of nodes match the coordinates of the
from nodes or the end nodes in the set tolerance, note down the
node ID in Edge-Node relation table. And the Node-Edge relation
table is based on the former one. According to the from-node and
end-node Id of every edge, we can easily get the edges at every
node.
The crux of the algorithm is to build what we define as special
area topology, that is, to search the road segments around the area
feature that are closest to it. From Fig. 4, we know that if we draw
a radial downwards from the identified point (A), the edge (BC)
that intersects with the radial first is one edge we want. So we
may think that if the radial is dense enough, we can find all
required road segments around the area feature (Fig.4). However,
the fact is that we cannot draw all radials. In our algorithm, we
transform the problem to the following steps. Above all, specify
the begin edge of the search process by drawing a vertical radial
as we describe above. Then, set the begin edge as the edge of
current disposal (current edge for short) and identify the begin
node and end node of current edge according the rules defined in
our algorithm. Set the end node as the current node of the
searching process. And then search another edge that is connected
to the current edge at the current node and closest to the area
feature based on Qi operator. And then set the searched edge as
the current edge, the end node of the edge as the current node. The
searching process circulates until the end node of the current edge
is equal to the begin node of the begin edge. During the searching
process, we employ Qi operator because it is more efficient than
angle operator used before. We also need to correctly dispose the
dangle edges that are valid to road network. More details can be
gotten in the following section.
N
hel
p
ed
Fig. 4 An intuitionistic method to search the
road segments around the area feature
4.2 More Details
Specify the begin edge and identify the begin node and end
node of one edge: Draw a vertical radial downwards from the
identified point. The Edge which intersects with the radial first is
the begin edge in our algorithm. This process can be optimized by
excluding the edges that cannot intersect with the radial rather
than computing the intersect points between the radial and all the
edges. The begin node of one edge is the frontal node of one edge
in the counter-clockwise. In Fig. 4, BC is the begin edge that
intersects with the vertical radial first and B is the frontal nodes of
edge BC in the counter-clockwise. So B is the begin node of ed
BC and C is the end node of edge BC.
5
ge
Qi Operator: To search the next edge based on the current edge
and the current nodes, we need an operator to compute the most
appropriate edge, that is, the closest one to the polygon in the
direction. Angle operator is employed in the original methods. In
these methods the angle operator, tan” (x), needs to be computed.
The computation of tan” (x) is time consuming. The present paper
adopts Qi operator (Qi Hua, Liu WenXi, 1996) that saves the time
and heightens the efficiency. The basic ideas of Qi operator are to
represent the corresponding polyline on the boundary rectangle of
the unit circle as the azimuth of the radial. The center of the unit
circle is the end node of the current edge. In the Fig. 5, the
coordinate of point O is (Xo, Yo). The point B, the coordinate of
which is (X;, Y;) is the intersect point of the radial from O and the
boundary rectangle. SetAx;7 X;- Xo, Ay;= Y;- Yo. In the different
eight directions, the Qi operator of the azimuth can be represented
as the following formula.
13