authors 
Alik, B. 
year 
1999 
title 
A topology construction from line drawings using a uniform plane subdivision technique 
source 
ComputerAided Design, Vol. 31 (5) (1999) pp. 335348 
summary 
The paper describes an algorithm for constructing the topology from a set of line segments or polylines. The problem appears for example at landmaps that have been drawnby generalpurpose drawing packages or captured from blueprints by digitalisation. The solution comprises two steps; in the first step inconsistencies in the input data aredetected and removed, and in the second step the topology is constructed. The algorithm for topology construction consists of two phases: determination of a concave hull,and generation of polygons. It is shown that the runningtime of the presented algorithm is better than O(n2), where n is the number of input points. Because of a largenumber of geometric elements being expected, the geometric search needed at the first step of the algorithm is speeded up by an acceleration techniquea uniform planesubdivision. 
keywords 
Computational Geometry, Topology Construction, Uniform Space Subdivision 
series 
journal paper 
email 
zalik@unimb.si 
references 
Contenttype: text/plain

last changed 
2003/05/15 19:33 
