关键词: Voronoi 图, 联机增量算法, 减量算法, 不规则三角网, 数字地面模型

Abstract: Voronoi is also called Thiessen polygon, which is a continuous polygon made of
perpendicular bisectors by joining the two adjacent points. It is widely used in pattern
recognition, computer graphics, computer aided design, geography information system and
many other fields. A new approach of constructing TIN that represented terrain well was given
based on Voronoi diagrams and Delaunay triangulation networks. It is easily to make full use of
the management and loading of TIN in the establishment of DEM. The method of online
incremental and reducing algorithm to realize the generation of Voronoi after adding and
deleting points can change points actively, and it holds the superiorities of fast speed and high
efficiency.

Key words: Voronoi, Online adding algorithm, Deleting algorithm, TIN, DTM