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