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

eryar

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

性能提升-空間二叉查找樹

Posted on 2023-08-06 18:53 eryar 閱讀(722) 評論(0)  編輯 收藏 引用 所屬分類: 2.OpenCASCADE

性能提升-空間二叉查找樹

eryar@163.com

Abstract.  OpenCASCADE provides NCollection_UBTree to achieve high performance search overlapped boxes. The algorithm of unbalanced binary tree of overlapped bounding boxes. Once the tree of boxes  of geometric objects is constructed, the algorithm is capable of fast geometric selection of objects.  The tree can be easily updated by adding to it a new object with bounding box. The time of adding to the tree  of one object is O(log(N)), where N is the total number of  objects, so the time  of building a tree of  N objects is O(N(log(N)). The search time of one object is O(log(N)). Defining  various classes  inheriting NCollection_UBTree::Selector  we can perform various kinds of selection over the same b-tree object.

Key Words. Unbalanced Binary Tree, Binary Search Tree, Binary Sort Tree, Bounding Box

1 Introduction

非平衡二叉樹(Unbalanced Binary Tree)又叫二叉查找樹(Binary Search Tree)或二叉排序樹(Binary Sort Tree)。它的定義很簡單,就是左子樹上所有節(jié)點的值都要小于根節(jié)點上的值。右子樹上所有節(jié)點值都要大于根節(jié)點上的值。在二叉查找樹上執(zhí)行操作時間與樹的高度成正比。對于一棵含有n個結(jié)點的完全二叉樹,這些操作的最壞情況運(yùn)行時間為O(lg(n))。但是如果樹是含n個結(jié)點的線性鏈,則這些操作的最壞的情況運(yùn)行時間為O(n)。一棵隨機(jī)構(gòu)造的二叉查找樹的期望高度為O(lg(n)),從而這種樹上操作的平均時間為O(lg(n))。

幾何搜索(geometry searching)大致分兩類:一類是區(qū)域搜索問題(range searching problem),另一類是點的定位問題(point location problem)。區(qū)域搜索問題要回答的是給定一個區(qū)域,看有多少模型屬于這個區(qū)域。當(dāng)然,我們可以對所有模型進(jìn)行遍歷,這種算法時間復(fù)雜度為O(N),效率不高。常見的高效的區(qū)域搜索算法有k-D樹,k-D樹就是一種多維的平衡二叉樹。還有比較常見的KNN問題,這些都是計算幾何處理的問題。

OpenCASCADE中提供一種空間查找二叉樹算法NCollection_UBTree,字面意思是非平衡二叉樹Unbalanced Binary Tree。把上圖中的數(shù)字換成包圍盒,構(gòu)造二叉查找樹。為了解決查找二叉樹單鏈問題,加入隨機(jī)處理,可以使查找性能達(dá)到O(log(N)),相對普通遍歷速度而言還是不錯的。本文結(jié)合示例代碼說明如何使用這個非平衡二叉樹。

2 Example

在OpenCASCADE中有多個函數(shù)來實現(xiàn)將很多無序邊Edges連接成Wire,需要查詢一條邊Edge的一個頂點Vertex在一定精度范圍內(nèi)相連的頂點Vertex有哪些?

首先,實現(xiàn)一個選擇類,通過選擇類來進(jìn)行過濾:

typedef NCollection_UBTree<Standard_Integer, Bnd_Box> BoxTree;
typedef NCollection_UBTreeFiller<Standard_Integer, Bnd_Box> BoxTreeFiller;
class BoxSelector : public BoxTree::Selector
{
public:
    BoxSelector(const TColgp_SequenceOfPnt& thePoints, Standard_Real theTolerance)
        : Selector()
        , myPoints(thePoints)
        , myTolerance(theTolerance)
    {
    }
    virtual Standard_Boolean Reject(const Bnd_Box& theBox) const
    {
        return theBox.IsOut(myBox);
    }
    virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
    {
        if (theIndex > myPoints.Size() || theIndex == myIndex)
        {
            return Standard_False;
        }
        const gp_Pnt& aPnt = myPoints.Value(theIndex);
        if (aPnt.SquareDistance(myPnt) < myTolerance)
        {
            myResultIndex.Append(theIndex);
            return Standard_True;
        }
        return Standard_False;
    }
    void SetCurrentPoint(const gp_Pnt& thePnt, Standard_Integer theIndex)
    {
        myPnt = thePnt;
        myBox.Add(thePnt);
        myIndex = theIndex;
    }
    const TColStd_ListOfInteger& GetResultIndex() const
    {
        return myResultIndex;
    }
    void ClearResultIndex()
    {
        myResultIndex.Clear();
    }
protected:
private:
    const TColgp_SequenceOfPnt& myPoints;
    gp_Pnt myPnt;
    Bnd_Box myBox;
    Standard_Integer myIndex;
    Standard_Real myTolerance;
    TColStd_ListOfInteger myResultIndex;
};

主要實現(xiàn)兩個抽象函數(shù)Reject()和Accept(),以及設(shè)置當(dāng)前選擇器的狀態(tài)。Reject()函數(shù)用來判斷要查找的Box與當(dāng)前空間范圍的狀態(tài),如果在外,則返回True。當(dāng)兩個Box有相交時,會調(diào)用Accept()函數(shù),在此函數(shù)中判斷兩個點的距離是否在容差范圍內(nèi),若在容差范圍內(nèi),則將點記錄起來。主函數(shù)main代碼如下:

int main(int argc, char* argv[])
{
    // Fill tree with random points.
    BoxTree aBoxTree;
    BoxTreeFiller aTreeFiler(aBoxTree);
    math_BullardGenerator aRandom;
    TColgp_SequenceOfPnt aPoints;
    for (Standard_Integer i = 1; i <= 100; ++i)
    {
        gp_Pnt aPnt(aRandom.NextReal(), aRandom.NextReal(), aRandom.NextReal());
        aPoints.Append(aPnt);
        Bnd_Box aBox;
        aBox.Add(aPnt);
        aTreeFiler.Add(i, aBox);
    }
    aTreeFiler.Fill();
    // Query points near the given point.
    BoxSelector aSelector(aPoints, 0.1);
    for (Standard_Integer i = aPoints.Lower(); i <= aPoints.Upper(); ++i)
    {
        const gp_Pnt& aPnt = aPoints.Value(i);
        aSelector.SetCurrentPoint(aPnt, i);
        Standard_Integer aSize = aBoxTree.Select(aSelector);
        if (aSize > 0)
        {
            std::cout << "Search Point : " << aPnt.X() << " \t " << aPnt.Y() << " \t " << aPnt.Z() << std::endl;
            const TColStd_ListOfInteger& aResult = aSelector.GetResultIndex();
            for (TColStd_ListOfInteger::Iterator aIt(aResult); aIt.More(); aIt.Next())
            {
                const gp_Pnt& aPoint = aPoints.Value(aIt.Value());
                std::cout << "Target Point : " << aPoint.X() << " \t " << aPoint.Y() << " \t " << aPoint.Z() << std::endl;
            }
            std::cout << "=============================" << std::endl;
        }
        aSelector.ClearResultIndex();
    }
    return 0;
}

先用隨機(jī)函數(shù)隨機(jī)生成100個點,并將點通過BoxTreeFiller添加到查找樹aBoxTree中,調(diào)用Fill函數(shù)構(gòu)造查找樹。

再使用類BoxSelector來進(jìn)行快速查找,查找之前先設(shè)置當(dāng)前點及包圍盒。然后調(diào)用aBoxTree.Select(aSelector)進(jìn)行查找。

3 Conclusion

類NCollection_UBTree通過構(gòu)造包圍盒的非平衡二叉樹來加快區(qū)域搜索速度。如何提高搜索速度,是計算幾何處理的范疇。在OpenCASCADE中這個類使用場景比較多,如將無序邊構(gòu)造成Wire時都用這個類:BRepLib_MakeWire::Add(const TopTools_ListOfShape& L), ShapeAnalysis_FreeBounds::ConnectEdgesToWires()。包括后面引入的BVH都是為了提高搜索速度,在合適的場景中多使用這些算法,會對程序性能的提升有很大幫助。

 

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            在线亚洲+欧美+日本专区| 免费视频一区| 亚洲一区精彩视频| 国产精品久久网站| 久久久午夜电影| 免费欧美网站| 亚洲一区二区三区四区五区黄| 最近看过的日韩成人| 欧美精品v日韩精品v韩国精品v| 中文日韩在线| 欧美在线视频观看| 亚洲精品日日夜夜| 亚洲小说春色综合另类电影| 国产综合久久久久久鬼色| 麻豆精品视频在线| 欧美日韩综合在线| 久久免费国产精品1| 欧美精品一区二区三区一线天视频 | 亚洲综合欧美| 久久久7777| 日韩亚洲精品视频| 欧美一级视频精品观看| 亚洲精选91| 欧美在线黄色| 一区二区久久| 久久另类ts人妖一区二区| 一本色道88久久加勒比精品| 欧美一区二区在线免费观看 | 国产精品视频自拍| 欧美激情一区在线观看| 国产乱码精品一区二区三区五月婷 | 午夜国产精品影院在线观看| 91久久久国产精品| 午夜视频在线观看一区二区三区 | 国产午夜精品全部视频播放 | 欧美怡红院视频| 欧美精品99| 欧美va天堂在线| 国产欧美日韩综合| 一本久久综合亚洲鲁鲁| 亚洲国产精品一区二区第四页av| 亚洲综合电影| 亚洲一区二区综合| 欧美精品在线观看| 欧美jizz19性欧美| 国内视频精品| 午夜精品国产更新| 午夜日韩激情| 国产精品伦一区| 亚洲精品之草原avav久久| 亚洲国产精品一区二区三区| 性做久久久久久久免费看| 亚洲一区二区欧美日韩| 欧美日本不卡视频| 亚洲精品影院| 一区二区三区日韩精品视频| 欧美电影打屁股sp| 亚洲高清视频中文字幕| 亚洲国产欧美一区二区三区同亚洲 | 亚洲性感激情| 午夜精品剧场| 国产精品专区第二| 亚洲伊人第一页| 欧美在线视频全部完| 国产精品亚洲精品| 午夜久久黄色| 久久九九久久九九| 伊人久久大香线蕉av超碰演员| 欧美一级片久久久久久久| 久久久国产一区二区三区| 狠狠久久综合婷婷不卡| 久久亚洲精品欧美| 亚洲精品欧美激情| 亚洲女人天堂成人av在线| 国产精品一区二区a| 久久国产福利| 亚洲福利视频三区| 在线亚洲精品福利网址导航| 国产精品久久久久久av福利软件| 亚洲欧美中文日韩v在线观看| 久久久国际精品| 亚洲人人精品| 国产精品成人播放| 欧美中文字幕在线| 亚洲国产精品精华液网站| 亚洲夜间福利| 国产主播一区二区三区| 美国三级日本三级久久99| 亚洲激情精品| 欧美在线观看视频在线| 1024成人网色www| 欧美特黄一级大片| 欧美一级网站| 亚洲精品中文在线| 久久久精品五月天| 夜夜嗨av一区二区三区四季av | 欧美屁股在线| 欧美一区二区观看视频| 亚洲国产一区二区在线| 羞羞视频在线观看欧美| 亚洲激情在线| 国产欧美日韩精品专区| 欧美福利视频在线观看| 亚洲一区二区在线| 欧美国产大片| 久久精品免费| 亚洲校园激情| 91久久精品国产91久久性色tv| 国产精品久久久久久久久久尿| 久热精品在线视频| 欧美一级二级三级蜜桃| 日韩视频免费在线观看| 欧美成人精品影院| 久久国产一区| 午夜宅男欧美| 99精品99久久久久久宅男| 狠狠色综合网站久久久久久久| 欧美性色视频在线| 欧美大片91| 麻豆成人在线播放| 欧美一进一出视频| 亚洲午夜精品一区二区三区他趣| 亚洲激情啪啪| 亚洲国产婷婷综合在线精品| 久久午夜av| 久久久久久夜| 久久电影一区| 欧美专区在线观看一区| 亚洲欧美亚洲| 亚洲欧美国产毛片在线| 一区二区国产在线观看| 亚洲日本精品国产第一区| 亚洲第一伊人| 亚洲国产91色在线| 亚洲高清免费| 亚洲高清精品中出| 亚洲成在线观看| 亚洲国产成人91精品| 亚洲国产精品久久久久秋霞不卡| 黄色资源网久久资源365| 国产色视频一区| 黄色成人91| 亚洲激情偷拍| 日韩亚洲不卡在线| 这里只有精品在线播放| 亚洲一区视频| 欧美一区二区啪啪| 久久精品国产第一区二区三区| 久久精品免费播放| 久久一二三区| 欧美激情女人20p| 亚洲看片网站| 亚洲一区二区三区中文字幕在线| 午夜精品久久久| 久久嫩草精品久久久久| 欧美国产日韩一区二区在线观看| 欧美老女人xx| 国产乱码精品| 亚洲韩国一区二区三区| 在线视频欧美日韩| 欧美一区午夜精品| 欧美18av| 一区二区日韩伦理片| 亚洲欧美综合一区| 麻豆精品网站| 国产精品超碰97尤物18| 国产一区二区三区网站| 亚洲人成免费| 久久av一区二区三区漫画| 欧美国产三区| 亚洲一区二区三区色| 久久久久九九视频| 欧美视频二区36p| 国产专区欧美精品| 宅男精品导航| 嫩草影视亚洲| 亚洲一区二区三区午夜| 鲁大师成人一区二区三区| 国产精品国产三级国产专区53| 一区二区在线视频观看| 在线视频中文亚洲| 麻豆av一区二区三区| 亚洲视频第一页| 老司机67194精品线观看| 国产精品久久久久久影院8一贰佰| 在线视频国内自拍亚洲视频| 亚洲影院色在线观看免费| 免费看亚洲片| 欧美一区二区三区四区在线| 欧美日韩精品是欧美日韩精品| 激情成人亚洲| 欧美一区二区三区免费在线看| 亚洲欧洲一区二区三区在线观看| 欧美一级片久久久久久久| 国产精品www994| 日韩一区二区精品视频| 欧美大秀在线观看| 久久精品国产视频| 国产日韩欧美91| 亚洲欧美一级二级三级|