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

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>
            国产精品毛片在线| 欧美一区中文字幕| 久久裸体艺术| 亚洲网站视频| 最新成人在线| 先锋亚洲精品| 亚洲毛片在线看| 亚洲图片激情小说| 尤物yw午夜国产精品视频| 欧美激情第9页| 国产精品网红福利| 亚洲日本欧美日韩高观看| 国产嫩草影院久久久久 | 亚洲第一黄色| 欧美日韩国语| 亚洲电影成人| 亚洲国产日韩综合一区| 亚洲永久免费视频| 亚洲免费影视第一页| 免费在线一区二区| 亚洲第一页在线| 在线观看亚洲a| 久久精品一区二区| 久久久亚洲国产美女国产盗摄| 国产精品高清在线观看| 欧美福利在线| 日韩天天综合| 欧美成人激情视频免费观看| 久久人91精品久久久久久不卡| 国产精品乱看| 欧美一区二区在线免费观看 | 这里只有精品视频| 亚洲网站视频| 国产精品国产三级国产| 午夜亚洲视频| 亚洲第一区色| 午夜精品影院| 伊人久久av导航| 欧美精品麻豆| 香蕉免费一区二区三区在线观看 | 欧美中文字幕在线| 欧美国产1区2区| 亚洲伊人伊色伊影伊综合网| 国产精品视区| 美国三级日本三级久久99| 亚洲精品国久久99热| 久久久精品tv| 亚洲专区在线视频| 日韩图片一区| 亚洲激情av在线| 伊人夜夜躁av伊人久久| 欧美日韩久久不卡| 久久一区国产| 欧美影院在线| 亚洲影院色无极综合| 9l国产精品久久久久麻豆| 欧美a级片网| 久久久天天操| 午夜一区二区三区在线观看| 亚洲午夜免费视频| 在线视频欧美精品| 亚洲性感美女99在线| 亚洲精选视频在线| 91久久国产综合久久91精品网站| 尤物九九久久国产精品的特点 | 欧美在线日韩| 亚洲天天影视| 午夜精品剧场| 久久精品国产免费观看| 久久免费偷拍视频| 蜜臀99久久精品久久久久久软件| 久久综合色88| 久久精品二区| 老色批av在线精品| 亚洲国产精品va在线看黑人 | 欧美制服丝袜第一页| 性色av一区二区三区在线观看 | 欧美高清在线视频| 欧美男人的天堂| 国产精品一区二区视频 | 国产精品日韩在线播放| 国产日韩精品一区二区浪潮av| 国产亚洲一级| 99精品久久久| 久久久久久久波多野高潮日日| 老鸭窝亚洲一区二区三区| 99re视频这里只有精品| 久久先锋影音| 国产日本欧美在线观看| 韩国福利一区| 欧美在线高清| 一区二区久久久久| 久久综合导航| 国产亚洲欧洲| 欧美在线观看日本一区| 亚洲毛片在线| 欧美大胆人体视频| 合欧美一区二区三区| 久久精品2019中文字幕| 亚洲女性裸体视频| 国产精品久久久久久久久久三级| 亚洲欧洲精品一区二区| 久久久噜噜噜久久| 久久av二区| 国产欧美综合在线| 香蕉av福利精品导航| 一区二区三区日韩精品视频| 欧美黑人国产人伦爽爽爽| 亚洲人成在线观看网站高清| 欧美激情小视频| 欧美手机在线视频| 亚洲欧美在线aaa| 亚洲午夜91| 国产伊人精品| 欧美激情一二区| 欧美日韩精品在线| 久久精品国产一区二区三区免费看 | 欧美一区国产一区| 久久精品一区二区三区四区 | 欧美韩日一区二区三区| 欧美日韩不卡在线| 亚洲一级黄色| 免费在线一区二区| 香蕉av777xxx色综合一区| 欧美成人精品在线视频| 欧美有码在线视频| 欧美激情精品久久久久久| 亚洲一级网站| 欧美日韩黄视频| 久久综合给合| 国产精品男gay被猛男狂揉视频| 亚洲国产91| 亚洲国产精品va在线看黑人动漫| 亚洲久色影视| 中国日韩欧美久久久久久久久| 久久精品国产在热久久| 久久久午夜电影| 国产一区日韩一区| 久久爱www.| 毛片av中文字幕一区二区| 狠狠色2019综合网| 欧美综合二区| 另类成人小视频在线| 怡红院精品视频| 蜜桃av一区| 99re这里只有精品6| 中日韩高清电影网| 国产午夜精品理论片a级大结局| 欧美99久久| 国产欧美亚洲日本| 久久久综合香蕉尹人综合网| 久久网站热最新地址| 国产精品少妇自拍| 亚洲欧美日韩在线| 欧美99久久| 欧美一区二区观看视频| 一区二区亚洲精品| 欧美日韩午夜视频在线观看| 一区二区三区导航| 欧美一区二区三区免费看| 激情综合亚洲| 欧美色网在线| 免费成人高清| 亚洲午夜视频| 亚洲福利视频在线| 久久国产精品亚洲77777| 亚洲人线精品午夜| 黄色亚洲在线| 国产精品久久久久久久免费软件 | 校园春色国产精品| 亚洲精品一区二区在线观看| 久久久精品国产免大香伊| 亚洲一区二区三区777| 亚洲成在线观看| 国产亚洲成年网址在线观看| 国产精品亚洲а∨天堂免在线| 欧美看片网站| 欧美精品在线视频观看| 欧美巨乳在线| 国产精品高潮呻吟久久av无限| 免费亚洲电影在线| 免费国产一区二区| 久久久久网址| 欧美国产免费| 欧美三日本三级少妇三99| 欧美体内she精视频| 欧美日韩一区三区| 国产精品一区二区久久久久| 国产精品永久免费视频| 国精产品99永久一区一区| 伊人色综合久久天天| 亚洲国产成人av好男人在线观看| 在线观看成人小视频| 一区二区三区www| 欧美在线高清视频| 欧美高清视频| 亚洲欧美日产图| 欧美激情亚洲一区| 国产综合色在线| 中文国产成人精品|