文档章节

Visulalize Boost Voronoi in OpenSceneGraph

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

Visulalize Boost Voronoi in OpenSceneGraph

eryar@163.com

Abstract. One of the important features of the boost polygon library is the implementation of the generic sweepline algorithm to construct Voronoi diagrams of points and linear segments in 2D(developed as part of the Google Summer of Code 2010 program). Voronoi diagram data structure has applications in image segmentation, optical character recognition, nearest neighbor queries execution. It is closely related with the other computational geometry conectps: Delaunay triangulation, medial axis, straight skeleton, the largest empty circle. The paper focus on the usage of Boost.Polygon Voronoi Diagram and visualize it in OpenSceneGraph. 

Key words. Voronoi, Boost.Polygon, 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图的算法。本文根据Boost.Polygon中的Voronoi库,并用OpenSceneGraph显示出剖分结果。 

2. Boost.Polygon Voronoi Diagram

Boost.Polygon库提供了构造Voronoi图的接口,可根据点集、线段集来生成Voronoi图,如下图所示: 

wps_clip_image-28950

Figure 2.1 Voronoi Diagram generated by Boost.Polygon Voronoi Algorithms 

Boost.Polygon中的基于扫描线算法(sweep-line algorithm)Voronoi库可以实现如下功能: 

v 输入数据可以是点集和线段; 

v 算法的稳定性高及输出完整的拓朴信息; 

v 可以控制输出的几何信息的精度; 

计算几何方面以稳定性著称的CGAL库中的Voronoi算法只满足前两个功能。S-Hull库以上功能都没有很好的满足。下面是一些Boost.Polygon,CGAL,S-Hull库的对比数据: 

wps_clip_image-24820

wps_clip_image-17491

Figure 2.2 Construction time for 10 random points 

wps_clip_image-6204

Figure 2.3 Construction time for 100 random points 

wps_clip_image-7587

Figure 2.4 Construction time for 1000 random points 

wps_clip_image-22652

Figure 2.5 Construction time for 10000 random points 

wps_clip_image-7032

Figure 2.6 Memory usage for 100000 random points 

wps_clip_image-14814

Figure 2.7 Logarithmic Execution Time 

结论: 

v 在输入上没有限制这点上CGAL要优于Boost.Polygon; 

v Boost.Polygon Voronoi的稳定性要高于S-Hull; 

v Boost.Polygon Voronoi和S-Hull的时间复杂度为N*log(N),而CGAL的不是; 

v Boost.Polygon Voronoi的输出顶点的精度高于CGAL库; 

v Boost.Polygon Voronoi的速度快; 

v Boost.Polygon Voronoi根据10000个点或1000个线段来构造Voronoi的时间为0.02秒以内,所以可用来处理有实时性要求的场景; 

3. Implementation

Boost.Polygon的Voronoi算法使用简单,只需要输入点集或线段集合,就可以直接构造出Voronoi图了。最简单的程序示例代码如下: 

/*
*    Copyright (c) 2014 eryar All Rights Reserved.
*
*        File    : Main.cpp
*        Author  : eryar@163.com
*        Date    : 2014-05-06 18:28
*        Version : V1.0
*
*    Description : The Simplest example for boost voronoi library.
*      Key words : boost voronoi, C++
*
*/

#include "boost/polygon/voronoi.hpp"

using namespace boost::polygon;

typedef int coordinate_type;
typedef point_data<coordinate_type> Point;
typedef voronoi_diagram<double> VD;

int main(int argc, char* argv[])
{
    std::vector<Point> points;

    points.push_back(Point(0, 0));
    points.push_back(Point(1, 6));
    points.push_back(Point(-4, 5));
    points.push_back(Point(5, -1));
    points.push_back(Point(3, -11));
    points.push_back(Point(13, -1));

    VD vd;
    construct_voronoi(points.begin(), points.end(), &vd);

    return 0;
}

且Boost.Polygon的Voronoi算法遍历Voronoi边Edges,Voronoi单元cell,Voronoi顶点Vertex也很直接。如下代码所示为遍历所有边,来将剖分结果可视化:  

/*
*    Copyright (c) 2014 eryar All Rights Reserved.
*
*        File    : Main.cpp
*        Author  : eryar@163.com
*        Date    : 2014-05-06 18:28
*        Version : V1.0
*
*    Description : VoronoiViewer for boost voronoi library visulization.
*      Key words : boost voronoi, C++, OpenSceneGraph
*
*/

#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")


#include "boost/polygon/voronoi.hpp"

using namespace boost::polygon;

typedef double coordinate_type;
typedef point_data<coordinate_type> Point;
typedef voronoi_diagram<coordinate_type> VD;


osg::Node* BuildVoronoiDiagram(void)
{
    srand(static_cast<unsigned int> (time(NULL)));

    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();

    VD vd;
    std::vector<Point> thePoints;

    // Add points for the Voronoi Diagram.
    for (int i = 0; i < 100; ++i)
    {
        int x = rand() % 100;
        int y = rand() % 100;

        thePoints.push_back(Point(x, y));

        // Display the site of the Voronoi Diagram.
        theVertices->push_back(osg::Vec3(x - 1, 0.0, y));
        theVertices->push_back(osg::Vec3(x + 1, 0.0, y));

        theVertices->push_back(osg::Vec3(x, 0.0, y - 1));
        theVertices->push_back(osg::Vec3(x, 0.0, y + 1));
    }

    construct_voronoi(thePoints.begin(), thePoints.end(), &vd);

    // Visualize the edge of the Voronoi Diagram.
    // Traversing Voronoi edges using edge iterator.
    for (VD::const_edge_iterator it = vd.edges().begin(); it != vd.edges().end(); ++it)
    {
        if (it->is_primary())
        {
            if (it->is_finite())
            {
                theVertices->push_back(osg::Vec3(it->vertex0()->x(), 0.0, it->vertex0()->y()));
                theVertices->push_back(osg::Vec3(it->vertex1()->x(), 0.0, it->vertex1()->y()));
            }
            else
            {
                Point p1 = thePoints[it->cell()->source_index()];
                Point p2 = thePoints[it->twin()->cell()->source_index()];
                Point origin;
                Point direction;
                coordinate_type koef = 1.0;

                origin.x((p1.x() + p2.x()) * 0.5);
                origin.y((p1.y() + p2.y()) * 0.5);

                direction.x(p1.y() - p2.y());
                direction.y(p2.x() - p1.x());

                if (it->vertex0() == NULL)
                {
                    theVertices->push_back(osg::Vec3(
                        origin.x() - direction.x() * koef, 
                        0.0,
                        origin.y() - direction.y() * koef));
                }
                else
                {
                    theVertices->push_back(osg::Vec3(it->vertex0()->x(), 0.0, it->vertex0()->y()));
                }

                if (it->vertex1() == NULL)
                {
                    theVertices->push_back(osg::Vec3(
                        origin.x() + direction.x() * koef, 
                        0.0,
                        origin.y() + direction.y() * koef));
                }
                else
                {
                    theVertices->push_back(osg::Vec3(it->vertex1()->x(), 0.0, it->vertex1()->y()));
                }
            }
        }
    }
    
    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);

    return theGeode.release();
}


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

    theViewer.setSceneData(BuildVoronoiDiagram());
    theViewer.addEventHandler(new osgGA::StateSetManipulator(theViewer.getCamera()->getOrCreateStateSet()));
    theViewer.addEventHandler(new osgViewer::StatsHandler);
    theViewer.addEventHandler(new osgViewer::WindowSizeHandler);

    return theViewer.run();
}

绘制Voronoi的边时,当边是有限的finite时,直接可以画出直线;当边是infinite时,根据定义计算出了无界边的方向。显示结果如下图所示: 

wps_clip_image-8913

Figure 3.1 Construct Voronoi Diagram by 10 random points by Boost.Polygon 

wps_clip_image-27895

Figure 3.2 Construct Voronoi Diagram by 100 random points by Boost.Polygon 

4. Conclusion

Boost.Polygon中的Voronoi图算法稳定性及性能较高,且可以根据站点查找相关的拓朴信息,如根据站点查找Voronoi单元等;惟一不足的就是默认只处理整数点集。 

当输入有线段时,生成的Voronoi图中有曲线,曲线的绘制可参考相关例子实现。 

Boost.Polygon中的Voronoi算法都以模板实现,编译时只需要包含相关的头文件即可,不依赖其他库,使用还是很方便的。 

5. References

1. http://www.boost.org/

2. Boost.Polygon,http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/index.htm 

3. Voronoi Basic Tutorial,\boost_1_54_0\libs\polygon\doc\voronoi_basic_tutorial.htm 

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

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

 

PDF Version and Source Code: Visulalization Boost 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

没有更多内容

加载失败,请刷新页面

加载更多

idea下,Jetty采用main方法启动web项目

对于maven多模块的spring web项目,本地开发时,启动的方式一般有如下几种: 使用容器(tomcat/jetty/resin等),该方式需要ide支持,而社区版的idea并不支持; maven插件(jetty/tomcat),...

Funcy1122
11分钟前
0
0
删除功能(Ajax版)

单个删除 删除按钮: var delBtn = $("<a href='#' class='del'>删除</a>"); 注意: //此事件不可用$(".del").click(function(){var id =$(this).parents("tr").find("td:eq(1)").text()......

流小文
26分钟前
0
0
JVM:查看java内存情况命令

jmap (linux下特有,也是很常用的一个命令)   观察运行中的jvm物理内存的占用情况。   参数如下:   -heap :打印jvm heap的情况   -histo: 打印jvm heap的直方图。其输出信息包括类...

浮躁的码农
27分钟前
0
0
dockerfile 镜像构建(1)

通用dockerfile 利用已经编译好的.jar 来构建镜像。要构建的目录如下: [root@iZuf61quxhnlk9m2tkx16cZ demo_jar]# docker build -t demo:1 . 运行镜像: [root@iZuf61quxhnlk9m2tkx16cZ de...

Canaan_
今天
2
0
Redis radix tree源码解析

Redis实现了不定长压缩前缀的radix tree,用在集群模式下存储slot对应的的所有key信息。本文将详述在Redis中如何实现radix tree。 核心数据结构 raxNode是radix tree的核心数据结构,其结构体...

阿里云云栖社区
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部