LI Jiatian, YANG Qili, LUO Fuli, LUO Huilan, LIN Yan. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11): 1545-1550. DOI: 10.13203/j.whugis20140018
Citation: LI Jiatian, YANG Qili, LUO Fuli, LUO Huilan, LIN Yan. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11): 1545-1550. DOI: 10.13203/j.whugis20140018

A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons

  • Computing efficiency and the type of generator are a limitation and barely sustain the construction of Voronoi diagrams based on polyline/polygons. Thus, a new decomposition and combination algorithm for polyline/polygons is proposed in this paper, the main procedure transforms polyline/polygons into discrete feature points. According to cross connection characteristics, vicinity feature points pairs are constructed, whose cross parts of Voronoi diagrams can be substitute for the equal distance boundaries of polyline/polygons. Based on the area differences in iterative discrete computational sub-Voronoi regions, before and after, the generator is alternative in the iterative procedure that making sub-Voronoi region being gradually adjusted to the required precision. From empirical results and analysis, it can be concluded is that the time complexity of the proposed algorithm is O(n2) at high precision. Lastly, generated effect of polyline/polygon Voronoi diagram in the case of ample data using this algorithm is revealed.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return