青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

eryar

PipeCAD - Plant Piping Design Software.
RvmTranslator - Translate AVEVA RVM to OBJ, glTF, etc.
posts - 603, comments - 590, trackbacks - 0, articles - 0

Visulalization 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

計(jì)算幾何(Computational Geometry)作為一門學(xué)科,起源于20世紀(jì)70年代,經(jīng)過(guò)近四十多年的發(fā)展,其研究?jī)?nèi)容不斷擴(kuò)大,涉及Voronoi圖、三角剖分、凸包、直線與多邊形求交、可見(jiàn)性、路徑規(guī)劃、多邊形剖分等內(nèi)容。據(jù)相關(guān)統(tǒng)計(jì),在數(shù)以千計(jì)的相關(guān)文章中,約有15%是關(guān)于Voronoi圖及其對(duì)偶(dual)圖Delaunay三角剖分(Delaunay Triangulation)的研究。由于Voronoi圖具有最近性、鄰接性等眾多性質(zhì)和比較系統(tǒng)的理論體系,如今已經(jīng)在計(jì)算機(jī)圖形學(xué)、機(jī)械工程、地理信息系統(tǒng)、機(jī)器人、圖像處理、大數(shù)據(jù)分析與處理、生物計(jì)算及無(wú)線傳感網(wǎng)絡(luò)等領(lǐng)域得到了廣泛應(yīng)用,同時(shí)也是解決碰撞檢測(cè)、路徑規(guī)劃、可見(jiàn)性計(jì)算、骨架計(jì)算以及凸包計(jì)算等計(jì)算幾何所涉及的其他問(wèn)題的有效工具。

Voronoi圖的起源最早可以追溯到17世紀(jì)。1644年,Descartes用類似Voronoi圖的結(jié)構(gòu)顯示太陽(yáng)系中物質(zhì)的分布。數(shù)學(xué)家G.L. Dirichlet和M.G.Voronoi分別于1850年和1908年在他們的論文中討論了Voronoi圖的概念,所以Voronoi圖又叫Dirichlet tessellation。在其他領(lǐng)域,這個(gè)概念也曾獨(dú)立地出現(xiàn),如生物學(xué)和生理學(xué)中稱之為中軸變換(Medial Axis Transform)或骨架(Skeleton)。化學(xué)與物理學(xué)中稱之為Wigner-Seitz Zones,氣象學(xué)與地理學(xué)中稱之為Thiessen多邊形。Voronoi圖最早由Thiessen應(yīng)用于氣象觀測(cè)站中隨機(jī)分布的研究。由于M.G. Voronoi從更通用的n維情況對(duì)其進(jìn)行研究和定義,所以Voronoi圖這個(gè)名稱為大多數(shù)人所使用。

在路徑規(guī)劃、機(jī)械加工、模式識(shí)別、虛擬現(xiàn)實(shí)、生物計(jì)算等領(lǐng)域,將站點(diǎn)從離散點(diǎn)擴(kuò)展到線段圓弧等生成Voronoi圖的方式也是非常常見(jiàn)的。

目前可用于生成Voronoi圖的庫(kù)有一些,很多是開(kāi)源庫(kù)。像CGAL庫(kù)、boost中也提供了生成Voronoi圖的算法。本文根據(jù)Boost.Polygon中的Voronoi庫(kù),并用OpenSceneGraph顯示出剖分結(jié)果。

2. Boost.Polygon Voronoi Diagram

Boost.Polygon庫(kù)提供了構(gòu)造Voronoi圖的接口,可根據(jù)點(diǎn)集、線段集來(lái)生成Voronoi圖,如下圖所示:

wps_clip_image-28950

Figure 2.1 Voronoi Diagram generated by Boost.Polygon Voronoi Algorithms

Boost.Polygon中的基于掃描線算法(sweep-line algorithm)Voronoi庫(kù)可以實(shí)現(xiàn)如下功能:

v 輸入數(shù)據(jù)可以是點(diǎn)集和線段;

v 算法的穩(wěn)定性高及輸出完整的拓樸信息;

v 可以控制輸出的幾何信息的精度;

計(jì)算幾何方面以穩(wěn)定性著稱的CGAL庫(kù)中的Voronoi算法只滿足前兩個(gè)功能。S-Hull庫(kù)以上功能都沒(méi)有很好的滿足。下面是一些Boost.Polygon,CGAL,S-Hull庫(kù)的對(duì)比數(shù)據(jù):

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

結(jié)論:

v 在輸入上沒(méi)有限制這點(diǎn)上CGAL要優(yōu)于Boost.Polygon;

v Boost.Polygon Voronoi的穩(wěn)定性要高于S-Hull;

v Boost.Polygon Voronoi和S-Hull的時(shí)間復(fù)雜度為N*log(N),而CGAL的不是;

v Boost.Polygon Voronoi的輸出頂點(diǎn)的精度高于CGAL庫(kù);

v Boost.Polygon Voronoi的速度快;

v Boost.Polygon Voronoi根據(jù)10000個(gè)點(diǎn)或1000個(gè)線段來(lái)構(gòu)造Voronoi的時(shí)間為0.02秒以內(nèi),所以可用來(lái)處理有實(shí)時(shí)性要求的場(chǎng)景;

3. Implementation

Boost.Polygon的Voronoi算法使用簡(jiǎn)單,只需要輸入點(diǎn)集或線段集合,就可以直接構(gòu)造出Voronoi圖了。最簡(jiǎn)單的程序示例代碼如下:

 

/*
*    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(
00));
    points.push_back(Point(
16));
    points.push_back(Point(
-45));
    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頂點(diǎn)Vertex也很直接。如下代碼所示為遍歷所有邊,來(lái)將剖分結(jié)果可視化:

 

/*
*    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 - 10.0, y));
        theVertices
->push_back(osg::Vec3(x + 10.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.0f1.0f0.0f1.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.0f0.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的邊時(shí),當(dāng)邊是有限的finite時(shí),直接可以畫(huà)出直線;當(dāng)邊是infinite時(shí),根據(jù)定義計(jì)算出了無(wú)界邊的方向。顯示結(jié)果如下圖所示:

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圖算法穩(wěn)定性及性能較高,且可以根據(jù)站點(diǎn)查找相關(guān)的拓樸信息,如根據(jù)站點(diǎn)查找Voronoi單元等;惟一不足的就是默認(rèn)只處理整數(shù)點(diǎn)集。

當(dāng)輸入有線段時(shí),生成的Voronoi圖中有曲線,曲線的繪制可參考相關(guān)例子實(shí)現(xiàn)。

Boost.Polygon中的Voronoi算法都以模板實(shí)現(xiàn),編譯時(shí)只需要包含相關(guān)的頭文件即可,不依賴其他庫(kù),使用還是很方便的。

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. 汪嘉業(yè), 王文平, 屠長(zhǎng)河, 楊承磊. 計(jì)算幾何及應(yīng)用. 科學(xué)出版社. 2011

5. 楊承磊, 呂琳, 楊義軍, 孟祥旭. Voronoi圖及其應(yīng)用. 清華大學(xué)出版社. 2013

 

Feedback

# re: Visulalization Boost Voronoi in OpenSceneGraph  回復(fù)  更多評(píng)論   

2014-05-08 10:37 by OpenCASCAE->3D
韋恩圖,在我們地理信息專業(yè)也有涉及,真棒,又受教了,哈哈。

# re: Visulalization Boost Voronoi in OpenSceneGraph  回復(fù)  更多評(píng)論   

2014-05-08 13:11 by eryar
是的,Voronoi圖的作用很大,我也是要學(xué)習(xí)中,看看能不能應(yīng)用一下
@OpenCASCAE-&gt;3D
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久久久高清| 欧美一区成人| 欧美日韩直播| 亚洲一区三区电影在线观看| 亚洲精品资源| 国产精品播放| 亚洲欧美在线视频观看| 亚洲免费在线观看| 国产色产综合产在线视频| 久久精品国产亚洲aⅴ| 久久久久成人精品| 亚洲精品美女在线| 在线一区二区三区四区| 国产午夜精品久久| 久久中文精品| 欧美激情按摩| 欧美一进一出视频| 免费观看成人鲁鲁鲁鲁鲁视频| 亚洲精品黄网在线观看| 中国成人亚色综合网站| 国产小视频国产精品| 欧美激情第六页| 国产精品久久久久久久久久妞妞| 久久精品国产91精品亚洲| 男人的天堂亚洲在线| 亚洲一区二区三区乱码aⅴ蜜桃女 亚洲一区二区三区乱码aⅴ | 亚洲裸体视频| 国产一区二区精品| 亚洲精品老司机| 国产精品人人做人人爽| 欧美成人国产va精品日本一级| 欧美激情1区2区3区| 欧美一区二区三区在线观看视频| 久久综合成人精品亚洲另类欧美| 亚洲免费一在线| 美女黄色成人网| 久久精品国产91精品亚洲| 欧美精品一卡| 免费久久99精品国产自| 国产精品久久久久久久免费软件 | 亚洲免费中文字幕| 亚洲免费不卡| 久久蜜桃av一区精品变态类天堂| 亚洲自拍偷拍网址| 欧美mv日韩mv国产网站app| 久久成人久久爱| 欧美性片在线观看| 91久久精品网| 91久久精品日日躁夜夜躁欧美| 午夜精品免费| 午夜精品电影| 欧美亚日韩国产aⅴ精品中极品| 欧美顶级大胆免费视频| 国语自产精品视频在线看一大j8 | 亚洲精品久久7777| 亚洲欧洲另类| 麻豆9191精品国产| 免费亚洲网站| 激情五月***国产精品| 亚洲欧美综合精品久久成人| 亚洲一区3d动漫同人无遮挡| 欧美激情综合亚洲一二区| 欧美jizzhd精品欧美巨大免费| 国产女主播一区二区| 中日韩视频在线观看| 在线视频你懂得一区| 欧美激情视频给我| 亚洲日本欧美| 99精品欧美一区| 欧美日韩三级视频| 一区二区三区.www| 亚洲欧美伊人| 国产欧美精品| 欧美一区三区二区在线观看| 久久久九九九九| 韩曰欧美视频免费观看| 久久久精品国产99久久精品芒果| 久久精品综合一区| 在线激情影院一区| 欧美激情一区在线| 一道本一区二区| 欧美一区二区三区在线观看 | 欧美精品一区二区三区蜜桃| 最新国产の精品合集bt伙计| 制服诱惑一区二区| 国产精品一区二区黑丝| 欧美伊人久久大香线蕉综合69| 久久久久久国产精品一区| 在线免费观看日本欧美| 欧美xxx成人| 中日韩视频在线观看| 久久精品女人的天堂av| 亚洲国产精品va| 欧美人与性动交α欧美精品济南到| 亚洲美女网站| 久久久999成人| 亚洲精品日韩在线观看| 国产精品免费一区二区三区观看| 欧美在线在线| 亚洲精品久久久一区二区三区| 欧美一区二区三区播放老司机| 一区在线视频| 欧美日韩一区二区三区四区五区| 亚洲欧美在线磁力| 亚洲黄页视频免费观看| 先锋影音国产精品| 亚洲精品日韩精品| 国产亚洲欧美一区二区| 欧美另类一区二区三区| 欧美亚洲日本国产| 亚洲国产日韩综合一区| 久久九九免费视频| 亚洲少妇自拍| 亚洲高清视频一区| 国产欧美日韩一区二区三区在线观看 | 国产精品久久久久久久久久免费看| 久久精品视频导航| 夜夜嗨av色一区二区不卡| 蜜乳av另类精品一区二区| 亚洲欧美亚洲| 亚洲视频你懂的| 亚洲片区在线| 影音先锋欧美精品| 国产精品中文在线| 欧美日韩第一区日日骚| 久久亚洲私人国产精品va| 亚洲一二区在线| 一本久久综合亚洲鲁鲁| 亚洲国产另类精品专区| 欧美国产精品| 女仆av观看一区| 久久亚洲二区| 欧美在线视频免费| 欧美一区二区三区在线| 亚洲在线1234| 一区二区三区国产| 一区二区三区 在线观看视频| 亚洲国内精品| 亚洲第一精品夜夜躁人人爽| 国模私拍一区二区三区| 国产欧美二区| 好吊视频一区二区三区四区| 国产美女扒开尿口久久久| 国产精品久久久久国产精品日日| 欧美日韩一级大片网址| 欧美日韩二区三区| 欧美日韩一区综合| 国产精品成人观看视频免费| 欧美视频一区在线| 国产精品网红福利| 国产精品综合网站| 国产在线欧美| 在线精品亚洲| 日韩亚洲欧美精品| 亚洲网站在线| 欧美在线视频一区二区| 久久久国产精品亚洲一区| 久久久久免费视频| 久久中文字幕一区| 最新日韩在线视频| 一区二区三区欧美视频| 亚洲欧美日韩系列| 久久久久久久综合色一本| 免费观看在线综合| 欧美日韩国产丝袜另类| 国产精品影音先锋| 亚洲第一网站| 亚洲在线视频一区| 久久久久成人精品| 亚洲国产精品专区久久 | 久久福利一区| 免费不卡中文字幕视频| 亚洲乱亚洲高清| 午夜在线电影亚洲一区| 免费亚洲电影| 国产精品久久久久aaaa樱花| 国一区二区在线观看| 日韩视频中午一区| 欧美制服第一页| 亚洲电影欧美电影有声小说| 夜夜嗨av一区二区三区中文字幕 | 亚洲福利国产精品| 亚洲欧美日韩天堂| 欧美电影在线| 国产亚洲精品bt天堂精选| 亚洲国产精品一区制服丝袜| 亚洲一区二区三区在线视频| 久久久久久久999| 日韩一级黄色大片| 久久亚洲精品中文字幕冲田杏梨 | 欧美大学生性色视频| 国产视频观看一区| 一区二区三区蜜桃网| 麻豆精品网站| 亚洲在线观看视频| 欧美激情精品| 在线视频观看日韩| 香蕉成人久久| 日韩视频免费在线| 欧美二区在线观看|