se 
ite 
he 
he 
rts 
ip 
re 
ot 
ill 
Sagi Filin 
  
  
  
  
distortions are removed if the projections are 
performed between similar segments in the 
polylines instead of the whole polylines. As 
breakpoints are the features that partition the 
polylines into segments it is necessary to first 
identify them on both polylines (as depicted in 
Figure 3.b), match them, and then apply the 
projections on the segments between them, 
Figure 3.c illustrates the modified projection 
algorithm. 
(b) 
   
  
  
  
  
  
Figure 3. Projection of polylines with/without “breakpoints” 
As can be seen, the modified procedure 
performs better in capturing the idea of polyline projection, as it at first associates counterpart breakpoints and only then 
associates the intermediate segments and the vertices along them. With the identification of counterpart elements between 
both sets and with establishing a transformation between them, the problem of merging common features is solved. Now it 
is only left to transform the related features to the unified database, thus solving the problem of maintaining topological 
relations and if one data sets is more accurate than another, then transforming the related objects to their new location can 
be expected to increase their accuracy. 
2.3 Planar subdivision of the data 
As local transformations that also coalesce counterpart features are in concern (according to the criteria introduced above), a 
natural approach would be to subdivide the data set according to the counterpart features. Having a network structure of the 
linear features makes this choice even more natural by providing a natural subdivision of the data into adjacent regions 
according to the minimal set of polygons formed by all the edges. Indeed, it is not 
mandatory for linear features to form a network structure, in such a case, the plane 
can be subdivided into regions using common algorithms, (for example, De Berg 
| et al. 1997). Subdividing the space into regions extends the topological structure of 
| the data from a network topology into cell topology by introducing “faces”- 2D 
objects defined by the edges (1D objects) enclosing them. The cell structure can 
based on identifying faces by their enclosing edges. This requires forming a 
convention regarding the position of a face in respect to the defining edge, for 
example, the right-hand side of an edge defines the inner part of a face. Since each 
edge participates in defining two faces - one on the left and one on the right, they 
are duplicated (virtually) so that each undirected edge turns into two directed 
edges, and each participates in defining only one face. The face construction 
algorithm then scans the edge list, and finds, for the current unchecked directed edge in the list, the next directed edge that 
forms the maximum clockwise angle in respect to the current directed edge. This process is repeated until the original 
directed edge is reached again. The criterion for terminating the algorithm is when no edges are left in the edge list. The 
process is comprehensive, but generates some undesirable phenomena such as connecting separate regions or including 
segments that contribute nothing to the overall face definition. These phenomena are mostly concerned with free edges (for 
example access roads leaving a main roads) or linking edges (such as roads connecting a major road network to a closed 
network of roads in a residential area). Figure 4 demonstrates such cases, and following the algorithm we can see that the 
inner structure will be part of the left face even though it is inside the right face. To eliminate such situations the algorihm 
is refined to identify and eliminate free edges and linking edges. The first situation is easier to perform as free edges are 
characterized by having at least one free end node. These edges are separated from the edge list for the cell topology. This 
process should be iterative as the removal of one edge might turn another one free. Links are more difficult to detect as their 
end points are connected to at least two edges. To track them we use the fact that in the definition of cell boundaries they 
will appear twice in the definition of the same face. 
  
  
| Figure 4. Free and linking edges | 
while defining closed regions 
Elimination of link edges can create inner faces inside a face (holes). Holes appear twice in the face list, one defining the 
outer boundary and the other the inner boundary. Viewing Figure 5 and keeping in mind the idea of local transformations 
shows that holes play an important role in the rubber-sheeting transformation. Naturally we would like the rubber-sheeting 
transformation of objects inside region P, to be performed according to its boundary but not in respect to the external 
boundary of polygon P;. By the same token we would like the objects in P; to be transformed according to the external face 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 285