利用类Delaunay三角剖分实现Voronio图

Implementation of Voronoi Diagram by Ressmble Delaunay Triangulation

1引言 计算几何在计算机辅助设计、计算机图形学(特别是三维图形生成技术)及机器人等领域是非常重要的.特别在近年来,受到了学术界的极大关注.Voronoi图是计算几何的一个重要分支.在气象、生态、空中交通管制、城市规划等领域都得到广泛应用.

Voronoi diagram is one of the most important branches in computational geometry and finds applications in various fields. In the paper, the method, which is proposed, is new and efficient.It verifies pixels one by one, finds Voronoi vertices, connects Voronoi vertices, forms Voronoi diagrams. The method of thinking is clear-cut, algorith-mically simple, implements easily, and the data structure of Voronoi diagrams are easily described. Finally the source program is written in Visual C++.