A rapid algorithm for topology construction from a set of line segments
Sebastian Krivograd, Mladen Trlep, Borut Žalik · 2006
Abstract:- An efficient algorithm for topology construction from a set of line segments is considered in the paper. The algorithm works in two steps: input analyzing, and topology construction. In the first step, inconsistencies in input are solved. The second step consists of two parts: the envelope construction, and determination of neighbouring relations between the obtained neighbouring The time complexity of the first part highly depends on the input data distribution, and the second part, which presents our original work, runs in O(n), what is confirmed by experiments using artificial input and real data from geographic database.