• <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>

            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)作為一門(mén)學(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用類(lèi)似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é)中稱之為T(mén)hiessen多邊形。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
            韋恩圖,在我們地理信息專(zhuān)業(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

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            国内精品久久久久影院亚洲| 99久久无色码中文字幕| 中文国产成人精品久久不卡| 久久亚洲日韩看片无码| 奇米影视7777久久精品| 国产免费久久久久久无码| 久久伊人中文无码| 久久精品中文騷妇女内射| 色综合久久88色综合天天 | 久久精品无码专区免费青青 | 国产午夜精品久久久久九九| 久久综合久久综合亚洲| 99久久99久久久精品齐齐| 色诱久久av| 狠狠色丁香久久综合五月| 中文字幕乱码久久午夜| 国产精品午夜久久| 99久久免费国产精精品| 久久人人添人人爽添人人片牛牛 | 精品国产乱码久久久久软件| 一级做a爱片久久毛片| 91精品国产高清久久久久久国产嫩草| 午夜精品久久久久9999高清| 欧美日韩中文字幕久久伊人| 99国产欧美久久久精品蜜芽| 久久久久久久久久久精品尤物| 国产精自产拍久久久久久蜜| MM131亚洲国产美女久久| 色综合久久久久无码专区| 免费无码国产欧美久久18| 精品久久久久久99人妻| 久久精品国产精品青草app| 久久九九精品99国产精品| 色偷偷久久一区二区三区| 久久强奷乱码老熟女网站| 四虎影视久久久免费| 亚洲国产精品综合久久一线| 欧美精品一区二区精品久久| 精品九九久久国内精品| 日韩欧美亚洲综合久久影院d3| .精品久久久麻豆国产精品|