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

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>
            亚洲国产二区| 国产精品视频内| 亚洲人成啪啪网站| 欧美国产日本| 欧美剧在线观看| 亚洲综合国产激情另类一区| 国产精品99久久久久久人| 国产精品国产自产拍高清av王其| 亚洲女人天堂成人av在线| 午夜亚洲视频| 一区在线免费观看| 欧美成人dvd在线视频| 欧美成人r级一区二区三区| 亚洲视频精品| 久久av一区二区三区| 亚洲激情欧美激情| 99综合精品| 伊人久久婷婷色综合98网| 亚洲高清自拍| 国产精品试看| 欧美高清视频免费观看| 国产精品白丝av嫩草影院 | 欧美高清日韩| 亚洲欧美中文另类| 久久综合久色欧美综合狠狠| 亚洲婷婷在线| 久久国产66| 亚洲私人影院在线观看| 久久国产精品久久久久久电车| 亚洲精品一区中文| 欧美一区网站| 国产精品99久久久久久宅男 | 欧美成年人网站| 国产精品手机视频| 欧美国产日韩精品免费观看| 国产精品午夜在线| 亚洲国产日韩欧美综合久久| 国产午夜精品美女视频明星a级| 亚洲黄色在线视频| 精品成人久久| 欧美一区二区啪啪| 午夜国产精品视频| 欧美三级乱人伦电影| 欧美国产日产韩国视频| 好吊日精品视频| 亚洲一区二区三区视频播放| 一区二区三区久久久| 久久综合99re88久久爱| 久久久久久9999| 国产噜噜噜噜噜久久久久久久久| 99re视频这里只有精品| 亚洲精品在线视频观看| 久久亚洲精品中文字幕冲田杏梨| 久久国产精品久久精品国产| 国产精品久久国产三级国电话系列 | 亚洲人精品午夜| 亚洲肉体裸体xxxx137| 久久女同精品一区二区| 欧美自拍偷拍午夜视频| 国产精品久久久久毛片大屁完整版 | 中国日韩欧美久久久久久久久| 另类欧美日韩国产在线| 免费看av成人| 在线高清一区| 噜噜噜91成人网| 亚洲国产成人在线| 夜夜嗨av一区二区三区中文字幕| 国产精品大片wwwwww| 最近看过的日韩成人| 亚洲国产欧美日韩精品| 久久夜色精品亚洲噜噜国产mv | 亚洲国内欧美| 欧美大片在线观看| 日韩视频在线播放| 亚洲欧美日韩一区在线| 国产精品萝li| 欧美在线观看一区二区| 久久夜精品va视频免费观看| 在线日本高清免费不卡| 欧美国产视频在线| 一区二区电影免费观看| 欧美一级理论性理论a| 国产一区在线看| 欧美11—12娇小xxxx| 日韩视频一区二区| 久久国产精品亚洲va麻豆| 激情伊人五月天久久综合| 美女图片一区二区| 一本高清dvd不卡在线观看| 欧美在线免费观看视频| 亚洲第一精品在线| 欧美天堂在线观看| 欧美一区二区免费观在线| 欧美激情一区二区三区成人| 亚洲一区二区三区久久| 国产日韩精品在线观看| 久热精品视频在线观看| 日韩写真在线| 久久综合一区| 亚洲欧美韩国| 亚洲黄色免费电影| 国产美女精品视频免费观看| 欧美77777| 欧美在线观看你懂的| 亚洲精品韩国| 免费在线观看成人av| 亚洲制服av| 亚洲三级网站| 狠狠综合久久av一区二区小说| 欧美性猛交xxxx乱大交蜜桃 | 欧美一区二区视频网站| 亚洲黄色成人| 久久亚洲图片| 欧美中文字幕在线| 亚洲性视频网址| 亚洲精品视频在线观看免费| 国产亚洲欧美日韩一区二区| 欧美日韩国产综合一区二区| 久久久精品网| 欧美一区二区三区啪啪| 亚洲天堂视频在线观看| 日韩写真在线| 亚洲精品国偷自产在线99热| 欧美成人精精品一区二区频| 欧美在线你懂的| 亚洲尤物影院| 亚洲一区在线免费观看| 一本色道久久综合亚洲精品按摩| 一区在线播放| 精品成人在线观看| 韩国精品在线观看| 狠狠色2019综合网| 国产亚洲午夜高清国产拍精品| 国产精品久久久一区二区| 欧美日韩一卡二卡| 欧美日韩一区二区在线视频| 欧美区国产区| 欧美日韩免费观看一区三区| 欧美激情1区| 欧美国产日韩一区| 欧美激情免费观看| 欧美日韩a区| 国产精品v亚洲精品v日韩精品| 欧美日韩三区| 国产精品久久久久久模特| 国产精品国产三级国产普通话蜜臀| 欧美日韩国产区一| 欧美三区在线| 国产欧美亚洲一区| 激情国产一区| 亚洲激情电影在线| 中文在线一区| 欧美一区综合| 久久夜色精品国产噜噜av| 老司机亚洲精品| 亚洲国产天堂久久国产91| 亚洲欧洲精品一区二区三区| 99ri日韩精品视频| 亚洲午夜日本在线观看| 欧美影片第一页| 蜜臀久久久99精品久久久久久| 欧美人与性禽动交情品| 国产精品日韩一区| 在线观看91精品国产入口| 亚洲精品美女在线观看播放| 亚洲无线视频| 久久阴道视频| 亚洲精品欧美精品| 羞羞漫画18久久大片| 美女精品在线观看| 欧美性猛交xxxx乱大交蜜桃| 国产一区深夜福利| 99精品视频免费全部在线| 欧美一区二区| 亚洲丁香婷深爱综合| 亚洲一级高清| 欧美国产亚洲精品久久久8v| 国产精品久久久久久久久婷婷| 一区二区在线视频| 亚洲在线视频| 欧美激情片在线观看| 亚洲一区二区三区乱码aⅴ蜜桃女| 久久精品国产77777蜜臀| 欧美日韩精品高清| 在线成人激情黄色| 欧美一区二区在线免费播放| 亚洲国产精品一区制服丝袜| 午夜欧美大尺度福利影院在线看| 美女脱光内衣内裤视频久久网站| 国产精品呻吟| 中文有码久久| 亚洲品质自拍| 久久综合国产精品| 国产一区二区三区最好精华液 | 国产日韩欧美综合精品| av不卡在线观看| 欧美成人xxx| 久久成人人人人精品欧| 国产精品美女久久久久久免费| 亚洲日本久久|