菜单

生物学Visulalization Voronoi in OpenSceneGraph

2019年2月15日 - 生物学

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年和一九零七年在她们的舆论中商量了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();
}

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

生物学 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封装的库小巧,使用方便,速度还很快。也多少不足,如无法博取3个站点对应的大举形,即某些点属于哪个区域。不可以取得带权点集的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. 汪嘉业, 王文平, 屠长河, 杨承磊. 总结几何及应用. 科学出版社. 二〇一三 

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

PDF Version and Source code: Visualization Voronoi in
OpenSceneGraph

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图