| authors |
Alik, B. |
| year |
1999 |
| title |
A topology construction from line drawings using a uniform plane subdivision technique |
| source |
Computer-Aided Design, Vol. 31 (5) (1999) pp. 335-348 |
| summary |
The paper describes an algorithm for constructing the topology from a set of line segments or polylines. The problem appears for example at land-maps that have been drawnby general-purpose drawing packages or captured from blue-prints 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 running-time 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 |
|
| references |
Content-type: text/plain
|
| last changed |
2003/05/15 21:33 |
|
