Visulalization Voronoi in OpenSceneGraph

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图、三角剖分、凸包、直线与多边形求交、可知性、路线设计、多边形剖分等剧情。据相关总括,在数以千计的连带文章中,约有一伍%是有关Voronoi图及其对偶(dual)图Delaunay三角剖分(Delaunay
Triangulation)的钻研。由于Voronoi图具备近日性、邻接性等诸多质量和相比较系统的理论种类,近日儿中午已在计算机图形学、机械工程、地理新闻体系、机器人、图像处理、大额解析与拍卖、生物总计及有线传感网络等世界取得了普遍应用,同时也是化解碰撞检查测试、路线设计、可知性总结、骨架总结以及凸包计算等总结几何所涉嫌的其余主题材料的灵光工具。 

Voronoi图的来源最早能够追溯到壹七世纪。1644年,Descartes用接近Voronoi图的结构展现太阳系中物质的遍布。科学家G.L.
Dirichlet和M.G.Voronoi分别于1850年和一九零6年在他们的散文中讨论了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 Sullivans一封装的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();
}

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

化学答案 1

Figure 2.1 Voronoi Diagram in OpenSceneGraph 

修改站点的多少,生成的Voronoi图如下所示: 

修改范围时也要修改生成范围中式点心的轻松函数的取余操作,制止生成点超越范围。 

化学答案 2

Figure 2.2 Less Sites of the Voronoi Diagram 

化学答案 3

Figure 2.3 More Sites of the Voronoi Diagram 

3. Conclusion

Shane O
Sullivans封装的库小巧,使用方便,速度还相当的慢。也稍微不足,如不能够拿到2个站点对应的多边形,即某些点属于哪个区域。不能够博得带权点集的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. 汪嘉业, 王文平, 屠长河, 杨承磊. 总结几何及应用. 科学出版社. 201壹 

  4. 杨承磊, 吕琳, 杨义军, 孟祥旭. Voronoi图及其应用. 哈工大东军政大学学出版社. 20一三

PDF Version and Source code: Visualization Voronoi in
OpenSceneGraph

admin

网站地图xml地图