Visulalize Voronoi in OpenSceneGraph
eryar@163.com
Abstract. In mathematics a Voronoi diagram is a way of dividing space into a number of regions. A set of points, called seeds, sites, or generators is specified beforehand and for each seed there will be a correspoinding region consisting of all points closer to that seed than to any other. The regions are called Voronoi cells. It is dual to the Delaunay triangulation. It is named after Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation. Voronoi diagrams can be found in a large number of fields in science and technology, even in art, and they have found numerous practical and theoretical applications. The paper use OpenSceneGraph to visualize the Voronoi diagram.
Key words. Voronoi, C++, OpenSceneGraph, Visualization
1. Introduction
计算几何（Computational Geometry）作为一门学科，起源于20世纪70年代，经过近四十多年的发展，其研究内容不断扩大，涉及Voronoi图、三角剖分、凸包、直线与多边形求交、可见性、路径规划、多边形剖分等内容。据相关统计，在数以千计的相关文章中，约有15%是关于Voronoi图及其对偶（dual）图Delaunay三角剖分（Delaunay Triangulation）的研究。由于Voronoi图具有最近性、邻接性等众多性质和比较系统的理论体系，如今已经在计算机图形学、机械工程、地理信息系统、机器人、图像处理、大数据分析与处理、生物计算及无线传感网络等领域得到了广泛应用，同时也是解决碰撞检测、路径规划、可见性计算、骨架计算以及凸包计算等计算几何所涉及的其他问题的有效工具。
Voronoi图的起源最早可以追溯到17世纪。1644年，Descartes用类似Voronoi图的结构显示太阳系中物质的分布。数学家G.L. Dirichlet和M.G.Voronoi分别于1850年和1908年在他们的论文中讨论了Voronoi图的概念，所以Voronoi图又叫Dirichlet tessellation。在其他领域，这个概念也曾独立地出现，如生物学和生理学中称之为中轴变换（Medial Axis Transform）或骨架（Skeleton）。化学与物理学中称之为Wigner-Seitz Zones，气象学与地理学中称之为Thiessen多边形。Voronoi图最早由Thiessen应用于气象观测站中随机分布的研究。由于M.G. Voronoi从更通用的n维情况对其进行研究和定义，所以Voronoi图这个名称为大多数人所使用。
在路径规划、机械加工、模式识别、虚拟现实、生物计算等领域，将站点从离散点扩展到线段圆弧等生成Voronoi图的方式也是非常常见的。
目前可用于生成Voronoi图的库有一些，很多是开源库。像CGAL库、boost中也提供了生成Voronoi图的算法。本文根据Shane O Sullivans1封装的Voronoi库，并用OpenSceneGraph显示出剖分结果。
2. Implementation
用Shane O Sullivans封装的VoronoiDiagramGenerator可以生成点集的Voronoi图，得到剖分的线段。程序小巧，易于使用。结合OpenSceneGraph将剖分得到的线段显示出来。程序代码如下所示：
/*
* Copyright (c) 2014 eryar All Rights Reserved.
*
* File : Main.cpp
* Author : eryar@163.com
* Date : 2014-04-30 18:28
* Version : V1.0
*
* Description : VoronoiViewer for voronoi library visulization.
*
*/
#include "VoronoiDiagramGenerator.h"
// OpenSceneGraph library.
#include <osgDB/ReadFile>
#include <osgViewer/Viewer>
#include <osgGA/StateSetManipulator>
#include <osgViewer/ViewerEventHandlers>
#pragma comment(lib, "osgd.lib")
#pragma comment(lib, "osgDBd.lib")
#pragma comment(lib, "osgGAd.lib")
#pragma comment(lib, "osgViewerd.lib")
osg::Node* BuildVoronoi(void)
{
osg::ref_ptr<osg::Geode> theGeode = new osg::Geode();
osg::ref_ptr<osg::Geometry> theLines = new osg::Geometry();
osg::ref_ptr<osg::Vec3Array> theVertices = new osg::Vec3Array();
const long thePointCount = 10;
float *xValues = new float[thePointCount] ();
float *yValues = new float[thePointCount] ();
float theMin = 0.0;
float theMax = 100.0;
float x1 = 0.0;
float y1 = 0.0;
float x2 = 0.0;
float y2 = 0.0;
// Draw the boundary box.
theVertices->push_back(osg::Vec3(theMin, 0.0, theMin));
theVertices->push_back(osg::Vec3(theMin, 0.0, theMax));
theVertices->push_back(osg::Vec3(theMin, 0.0, theMin));
theVertices->push_back(osg::Vec3(theMax, 0.0, theMin));
theVertices->push_back(osg::Vec3(theMin, 0.0, theMax));
theVertices->push_back(osg::Vec3(theMax, 0.0, theMax));
theVertices->push_back(osg::Vec3(theMax, 0.0, theMin));
theVertices->push_back(osg::Vec3(theMax, 0.0, theMax));
// initialize random seed:
srand(time(NULL));
// Sites of the Voronoi.
for (int i = 0; i < thePointCount; ++i)
{
xValues[i] = rand() % 100;
yValues[i] = rand() % 100;
// Draw the site.
theVertices->push_back(osg::Vec3(xValues[i] - 1.0, 0.0, yValues[i]));
theVertices->push_back(osg::Vec3(xValues[i] + 1.0, 0.0, yValues[i]));
theVertices->push_back(osg::Vec3(xValues[i], 0.0, yValues[i] - 1.0));
theVertices->push_back(osg::Vec3(xValues[i], 0.0, yValues[i] + 1.0));
}
// Generate Voronoi Diagram.
VoronoiDiagramGenerator vdg;
vdg.generateVoronoi(xValues, yValues, thePointCount, theMin, theMax, theMin, theMax);
vdg.resetIterator();
while (vdg.getNext(x1, y1, x2, y2))
{
theVertices->push_back(osg::Vec3(x1, 0.0, y1));
theVertices->push_back(osg::Vec3(x2, 0.0, y2));
}
theLines->setVertexArray(theVertices);
// Set the colors.
osg::ref_ptr<osg::Vec4Array> theColors = new osg::Vec4Array();
theColors->push_back(osg::Vec4(1.0f, 1.0f, 0.0f, 1.0f));
theLines->setColorArray(theColors);
theLines->setColorBinding(osg::Geometry::BIND_OVERALL);
// Set the normal.
osg::ref_ptr<osg::Vec3Array> theNormals = new osg::Vec3Array();
theNormals->push_back(osg::Vec3(0.0f, -1.0f, 0.0f));
theLines->setNormalArray(theNormals);
theLines->setNormalBinding(osg::Geometry::BIND_OVERALL);
theLines->addPrimitiveSet(new osg::DrawArrays(osg::PrimitiveSet::LINES, 0, theVertices->size()));
theGeode->addDrawable(theLines);
// Free the meomry.
delete [] xValues;
delete [] yValues;
return theGeode.release();
}
int main(int argc, char* argv[])
{
osgViewer::Viewer myViewer;
myViewer.setSceneData(BuildVoronoi());
myViewer.addEventHandler(new osgGA::StateSetManipulator(myViewer.getCamera()->getOrCreateStateSet()));
myViewer.addEventHandler(new osgViewer::StatsHandler);
myViewer.addEventHandler(new osgViewer::WindowSizeHandler);
return myViewer.run();
}
上述程序生成结果如下所示：
Figure 2.1 Voronoi Diagram in OpenSceneGraph
修改站点的数量，生成的Voronoi图如下所示：
修改范围时也要修改生成范围中点的随机函数的取余操作，避免生成点超出范围。
Figure 2.2 Less Sites of the Voronoi Diagram
Figure 2.3 More Sites of the Voronoi Diagram
3. Conclusion
Shane O Sullivans封装的库小巧，使用方便，速度还很快。也有些不足，如不能取得一个站点对应的多边形，即某个点属于哪个区域。不能得到带权点集的Voronoi剖分。
源程序小巧，借助程序代码来对Voronoi的概念进行理解还是不错的。
4. References
1. Shane O Sullivans, http://www.skynet.ie/~sos/mapviewer/voronoi.php
2. http://ect.bell-labs.com/who/sjf/
3. 汪嘉业, 王文平, 屠长河, 杨承磊. 计算几何及应用. 科学出版社. 2011
4. 杨承磊, 吕琳, 杨义军, 孟祥旭. Voronoi图及其应用. 清华大学出版社. 2013