## Visulalization Voronoi in OpenSceneGraph 原

eryar

Visulalization 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

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 <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

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

PDF Version and Source code: Visualization Voronoi in OpenSceneGraph

© 著作权归作者所有

### eryar

wangray84
2012/11/19
899
0

OSG 社区爱好者： 你们好！ 北京南山高科技有限公司正在招聘视景仿真工程师，职责三维引擎设计、开发及应用开发。 南山高科总师办是个精英队伍，目前全部人员都是硕士以上学历、并有4位博士或...

feiger.yu
2010/07/06
6
0

OSG 社区爱好者： 你们好！ 北京南山高科技有限公司正在招聘视景仿真工程师，职责三维引擎设计、开发及应用开发。 南山高科总师办是个精英队伍，目前全部人员都是硕士以上学历、并有4位博士或...

feiger.yu
2010/07/06
686
0
OpenSceneGraph 应用的问题

OpenSceneGraph 我都已经编译通过，环境变量添加好了，可在命令行（CMD）进行测试osgversion,osglogo,osgviewer cow.osg，都通过了。但是 在 vs2010中新建一个项目，测试时 出现了这样的错误...

yuxinabc1
2015/07/07
355
1

2013/05/22
156
0

Docker搭建Mysql集群、主从同步复制

1、创建数据挂载点： mkdir /opt/mysql-master/mysql、/opt/mysql-master/conf.d、/opt/mysql-slave/conf.d、/opt/mysql-slave/conf.d 2、分别在master、slave节点文件目录conf.d下创建touch......

WALK_MAN
28分钟前
3
0

y123456yz
29分钟前
1
0

33分钟前
3
0
Spring-boot单元测试（私有方法测试）

Spring-boot的单元测试网上有了很多，当项目是可以使用spring-boot正常运行时，只要在测试类上添加如下配置就使用@Autowired的方式进行单元测试 @RunWith(SpringJUnit4ClassRunner.class)@...

50分钟前
1
0
spring cloud(第一部)框架概述

50分钟前
2
0