eryar

PipeCAD - Plant Piping Design Software.
RvmTranslator - Translate AVEVA RVM to OBJ, glTF, etc.
posts - 603, comments - 590, trackbacks - 0, articles - 0

Visulalize Voronoi in OpenSceneGraph

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

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图这个名称为大多数人所使用。

2. Implementation

/*
*    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
<osgViewer/Viewer>
#include
<osgGA/StateSetManipulator>
#include
<osgViewer/ViewerEventHandlers>

#pragma comment(lib,
"osgd.lib")
#pragma comment(lib,
"osgDBd.lib")
#pragma comment(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.00.0, yValues[i]));
theVertices
->push_back(osg::Vec3(xValues[i] + 1.00.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.0f1.0f0.0f1.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.0f0.0f));

theLines
->setNormalArray(theNormals);
theLines
->setNormalBinding(osg::Geometry::BIND_OVERALL);

theLines

theGeode

// Free the meomry.
delete [] xValues;
delete [] yValues;

return theGeode.release();
}

int main(int argc, char* argv[])
{
osgViewer::Viewer myViewer;

myViewer.setSceneData(BuildVoronoi());

new osgGA::StateSetManipulator(myViewer.getCamera()->getOrCreateStateSet()));
new osgViewer::StatsHandler);
new osgViewer::WindowSizeHandler);

return myViewer.run();
}

Figure 2.1 Voronoi Diagram in OpenSceneGraph

Figure 2.2 Less Sites of the Voronoi Diagram

Figure 2.3 More Sites of the Voronoi Diagram

3. Conclusion

Shane O Sullivans封装的库小巧，使用方便，速度还很快。也有些不足，如不能取得一个站点对应的多边形，即某个点属于哪个区域。不能得到带权点集的Voronoi剖分。

4. References

1. Shane O Sullivans, http://www.skynet.ie/~sos/mapviewer/voronoi.php

3. 汪嘉业, 王文平, 屠长河, 杨承磊. 计算几何及应用. 科学出版社. 2011

4. 杨承磊, 吕琳, 杨义军, 孟祥旭. Voronoi图及其应用. 清华大学出版社. 2013