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

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)。它的定義很簡單,就是左子樹上所有節點的值都要小于根節點上的值。右子樹上所有節點值都要大于根節點上的值。在二叉查找樹上執行操作時間與樹的高度成正比。對于一棵含有n個結點的完全二叉樹,這些操作的最壞情況運行時間為O(lg(n))。但是如果樹是含n個結點的線性鏈,則這些操作的最壞的情況運行時間為O(n)。一棵隨機構造的二叉查找樹的期望高度為O(lg(n)),從而這種樹上操作的平均時間為O(lg(n))。

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

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

2 Example

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

首先,實現一個選擇類,通過選擇類來進行過濾:

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;
};

主要實現兩個抽象函數Reject()和Accept(),以及設置當前選擇器的狀態。Reject()函數用來判斷要查找的Box與當前空間范圍的狀態,如果在外,則返回True。當兩個Box有相交時,會調用Accept()函數,在此函數中判斷兩個點的距離是否在容差范圍內,若在容差范圍內,則將點記錄起來。主函數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;
}

先用隨機函數隨機生成100個點,并將點通過BoxTreeFiller添加到查找樹aBoxTree中,調用Fill函數構造查找樹。

再使用類BoxSelector來進行快速查找,查找之前先設置當前點及包圍盒。然后調用aBoxTree.Select(aSelector)進行查找。

3 Conclusion

類NCollection_UBTree通過構造包圍盒的非平衡二叉樹來加快區域搜索速度。如何提高搜索速度,是計算幾何處理的范疇。在OpenCASCADE中這個類使用場景比較多,如將無序邊構造成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>
            亚洲综合首页| 亚洲激情在线观看| 欧美日韩免费在线| 久久亚洲精品视频| 国产精品亚洲视频| 一区二区三区高清在线| 亚洲精品久久| 欧美黄色日本| 亚洲国产欧美在线 | 国产精品裸体一区二区三区| 亚洲经典视频在线观看| 亚洲电影天堂av| 久久久久久久网站| 免费成人美女女| 黄色日韩精品| 久久久午夜精品| 欧美成人性生活| 亚洲国产日韩在线| 蜜桃av一区二区三区| 欧美黄色大片网站| 亚洲欧洲视频| 欧美日韩不卡一区| 夜夜嗨网站十八久久| 一本久久青青| 欧美三级中文字幕在线观看| 日韩视频在线观看| 亚洲视频国产视频| 国产精品视区| 欧美与黑人午夜性猛交久久久| 久久久综合网站| 亚洲国产欧美一区二区三区久久| 欧美凹凸一区二区三区视频| 亚洲精品视频免费| 亚洲免费婷婷| 国产在线欧美日韩| 免费影视亚洲| 9国产精品视频| 久久超碰97中文字幕| 伊人久久亚洲美女图片| 蜜桃伊人久久| 亚洲视频在线一区| 久久久在线视频| 亚洲七七久久综合桃花剧情介绍| 欧美日韩国产综合新一区| 亚洲午夜在线观看视频在线| 久久久久久电影| 亚洲精品综合久久中文字幕| 欧美三区在线视频| 久久久久久一区| 亚洲精品专区| 久久久久免费视频| 一区二区三区国产盗摄| 国产欧美精品久久| 蜜臀久久久99精品久久久久久| 亚洲美女精品成人在线视频| 久久精品国产99国产精品| 亚洲人成网站在线播| 国产精品久久久久av免费| 久久久99爱| 一区二区精品| 欧美激情一区二区三区四区| 亚洲欧美视频一区| 亚洲欧洲一区二区天堂久久| 国产精品午夜久久| 欧美高清在线观看| 欧美一区亚洲一区| 99热这里只有成人精品国产| 免费的成人av| 欧美在线啊v一区| 日韩一区二区免费看| 国产亚洲精品久久久久婷婷瑜伽| 欧美激情亚洲另类| 久久视频在线视频| 亚洲欧美日韩综合| 夜夜嗨av一区二区三区网站四季av| 免费高清在线一区| 久久精品国产免费看久久精品| 一区二区精品| 亚洲日本精品国产第一区| 国产一区二区观看| 国产精品日韩精品欧美精品| 欧美精品激情| 蜜臀av一级做a爰片久久| 久久国产主播精品| 亚洲免费视频网站| 亚洲视频你懂的| 亚洲精品五月天| 亚洲国产欧美不卡在线观看| 久久综合网络一区二区| 久久精品在线观看| 久久精品视频网| 欧美中文字幕在线观看| 亚洲欧美日韩视频二区| 亚洲天堂成人在线观看| 日韩视频免费观看高清在线视频| 亚洲国产精品久久久久秋霞不卡 | 一区二区三区自拍| 黄色日韩网站视频| 国产一区二区三区高清| 国产欧美日韩精品一区| 国产精品日韩| 国产欧美va欧美va香蕉在| 国产精品蜜臀在线观看| 国产精品久久午夜夜伦鲁鲁| 国产精品日韩一区二区三区| 国产美女在线精品免费观看| 国产欧美日韩视频一区二区三区 | 久久久免费精品| 每日更新成人在线视频| 欧美不卡视频一区发布| 蜜臀久久99精品久久久画质超高清| 久久综合色天天久久综合图片| 久久夜色精品国产欧美乱极品| 久久综合色综合88| 欧美乱妇高清无乱码| 欧美视频在线观看视频极品| 欧美性片在线观看| 国产欧美丝祙| 在线免费观看欧美| 亚洲精一区二区三区| 一区二区毛片| 欧美一区二视频| 欧美成人国产一区二区| 亚洲国产1区| 亚洲视频一区二区在线观看| 欧美一区1区三区3区公司| 久久在线精品| 欧美日韩精品二区第二页| 国产农村妇女精品| 激情小说另类小说亚洲欧美| 日韩视频免费在线观看| 亚洲欧美一区二区三区在线| 裸体一区二区| 99re这里只有精品6| 小处雏高清一区二区三区 | 欧美在线观看一二区| 女人香蕉久久**毛片精品| 亚洲精品乱码久久久久久按摩观| 亚洲男女自偷自拍| 久久人人超碰| 国产精品久久久久久久久免费桃花| 一区二区三区在线观看国产| 亚洲视频欧美视频| 欧美亚洲成人精品| 国产中文一区| 亚洲一区精品视频| 免费观看成人| 亚洲伊人久久综合| 欧美国产91| 国产三级欧美三级| 一区二区三区欧美在线观看| 久久久人成影片一区二区三区 | 欧美女主播在线| 国产一区二区日韩精品欧美精品 | 午夜视频在线观看一区二区| 亚洲国产另类久久精品| 久久av一区二区三区漫画| 99精品国产在热久久下载| 久久亚洲视频| 亚洲欧美成人综合| 欧美日韩色综合| 亚洲精品日本| 欧美成人免费播放| 久久国产婷婷国产香蕉| 国产精品午夜在线| 亚洲一区999| 亚洲国产毛片完整版 | 亚洲精品国产品国语在线app | 亚洲一区一卡| 欧美视频一区二| 亚洲伦理网站| 亚洲国产美女| 鲁大师影院一区二区三区| 韩国av一区二区三区在线观看| 香蕉国产精品偷在线观看不卡| 亚洲乱码日产精品bd| 欧美激情五月| 一本久道久久综合中文字幕| 亚洲福利视频免费观看| 麻豆av一区二区三区| 亚洲电影第三页| 牛牛国产精品| 欧美成人高清视频| 91久久在线视频| 亚洲国产精品嫩草影院| 欧美高清一区二区| 日韩午夜在线播放| 亚洲人体偷拍| 欧美日韩视频在线| 亚洲一区二区在线视频| 亚洲最新色图| 国产精品一区视频| 欧美在线观看网址综合| 欧美在线日韩精品| 激情欧美日韩| 欧美成人午夜激情| 欧美人成在线| 亚洲欧美国产精品va在线观看| 亚洲自拍偷拍一区| 国产一区自拍视频|