文档章节

Visulalization Voronoi in OpenSceneGraph

eryar
 eryar
发布于 2014/11/23 12:34
字数 1391
阅读 41
收藏 0

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

计算几何(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();
}

 上述程序生成结果如下所示: 

wps_clip_image-21060

Figure 2.1 Voronoi Diagram in OpenSceneGraph 

修改站点的数量,生成的Voronoi图如下所示: 

修改范围时也要修改生成范围中点的随机函数的取余操作,避免生成点超出范围。 

wps_clip_image-21063

Figure 2.2 Less Sites of the Voronoi Diagram 

wps_clip_image-15223

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

PDF Version and Source code: Visualization Voronoi in OpenSceneGraph

© 著作权归作者所有

eryar
粉丝 21
博文 127
码字总数 227012
作品 0
武汉
私信 提问
有必要澄清一下关于 OpenThreads 的事项

有必要澄清一下,OpenThreads早在几年前就已经并入到OpenSceneGraph中,成为专用于该渲染引擎的线程库,oschina这里提供的地址已经不会再更新了。更新版本的OpenThreads(包括原子支持等)只...

wangray84
2012/11/19
899
0
北京南山高科技有限公司招聘OSG工程师

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

feiger.yu
2010/07/06
6
0
北京南山高科技有限公司招聘OSG工程师,招聘3人

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

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

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

yuxinabc1
2015/07/07
355
1
交流下C++和Lua合作的事儿~

我有个项目C+++Lua+QtScript的,感觉很高端吧,,实际上Lua就被当做XML在用而已。想放脚本上去,不知道放到什么地方。 而且有个问题,我用的OpenSceneGraph,使用智能指针,析构函数是protect...

子矜
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
手把手教你做中间件开发(分布式缓存篇)-借助redis已有的网络相关.c和.h文件,半小时快速实现一个epoll异步网络框架,程序demo

本文档配合主要对如下demo进行配合说明: 借助redis已有的网络相关.c和.h文件,半小时快速实现一个epoll异步网络框架,程序demo 0. 手把手教你做中间件、高性能服务器、分布式存储技术交流群 ...

y123456yz
29分钟前
1
0
阿里技术男的成长史:越想证明自己死得越快……

在上海工作8年后,身为部门经理的钱磊,管理着一家ERP公司的百十来号员工,“再往上爬就是老板和他儿子了……从这个领域的技术角度来讲算是做到了顶。”05年,钱磊就开始关注一家名字奇怪,做...

阿里云云栖社区
33分钟前
3
0
Spring-boot单元测试(私有方法测试)

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

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

关于微服务 近几年,'微服务'这个词越来越多的被身边的人所提及,到底什么是微服务,为什么微服务总是伴随着spring cloud被人们所提及,这里笔者结合多年的技术经历跟大家分享下自己的理解:...

白中墨
50分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部