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

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一区二区国产馆| 亚洲午夜视频在线观看| 艳妇臀荡乳欲伦亚洲一区| 欧美视频四区| 久久久久久网站| 麻豆九一精品爱看视频在线观看免费| 亚洲黄色在线观看| 亚洲开发第一视频在线播放| 国产精品电影网站| 久久久免费精品| 欧美人在线视频| 欧美一二三区精品| 欧美成人自拍视频| 午夜精品久久久久久久白皮肤| 久久国产免费| 99精品视频一区二区三区| 亚洲欧美日韩精品久久| 亚洲激情成人在线| 亚洲一区二区免费视频| 亚洲国产欧美日韩精品| 亚洲一区二区三区在线视频| 国产在线不卡精品| 99视频精品免费观看| 伊人久久男人天堂| 亚洲一级黄色片| 亚洲精品黄色| 久久久另类综合| 亚洲综合精品四区| 欧美激情视频一区二区三区在线播放| 午夜欧美精品久久久久久久| 欧美a级理论片| 久久久精彩视频| 欧美午夜视频在线观看| 欧美成人午夜激情在线| 国产日产亚洲精品| 艳妇臀荡乳欲伦亚洲一区| 亚洲国产天堂久久国产91| 香蕉成人久久| 亚洲男人av电影| 欧美日本视频在线| 欧美激情视频网站| 韩国久久久久| 欧美一级片在线播放| 亚洲欧美一区二区激情| 欧美日韩国产一区精品一区| 欧美成ee人免费视频| 国产日韩专区| 亚洲欧美视频一区二区三区| 亚洲欧美另类综合偷拍| 欧美日韩免费观看一区| 亚洲国产免费看| 亚洲第一久久影院| 久久人人97超碰精品888| 久久九九国产精品| 国产一区二区三区久久久| 亚洲在线视频免费观看| 亚洲自拍另类| 国产精品啊啊啊| 亚洲一区二区三区免费视频| 亚洲欧美春色| 国产日韩精品在线| 午夜综合激情| 久久九九全国免费精品观看| 国产综合欧美| 久久香蕉国产线看观看av| 欧美成人第一页| 亚洲精品一区二区三| 欧美风情在线| 亚洲精品国产欧美| 亚洲男女毛片无遮挡| 国产视频一区二区在线观看 | 久热精品在线视频| 在线观看一区视频| 欧美激情精品久久久久久大尺度| 亚洲黄色小视频| 亚洲一区二区三区精品视频| 国产精品色婷婷| 久久xxxx精品视频| 欧美国产欧美亚洲国产日韩mv天天看完整 | 99视频精品免费观看| 欧美日韩一区二区视频在线 | 亚洲第一区色| 中国女人久久久| 国产欧美韩日| 麻豆免费精品视频| 一本色道精品久久一区二区三区 | 日韩亚洲欧美综合| 国产精品免费视频xxxx| 久久精品免费播放| 亚洲精品乱码久久久久久| 亚洲欧美日韩国产精品| 一区二区三区在线不卡| 欧美精品三区| 欧美一区二区三区免费视频| 欧美黄色小视频| 亚洲欧美日韩综合| 亚洲高清av| 国产精品日韩专区| 欧美高清视频一二三区| 亚洲欧美国产日韩天堂区| 亚洲第一精品福利| 欧美在线一二三区| 一区二区欧美日韩| 一区在线视频观看| 国产精品久久久久久影视| 狂野欧美一区| 午夜综合激情| 一区二区三区视频在线播放| 久久最新视频| 欧美在线free| 亚洲性感美女99在线| 在线视频国内自拍亚洲视频| 国产精品毛片在线| 欧美精品videossex性护士| 欧美中文字幕视频在线观看| 99精品视频免费在线观看| 亚洲成人在线网| 久久只精品国产| 欧美在线观看视频一区二区| 一本综合久久| 99re66热这里只有精品3直播| 国内久久精品| 国产在线视频欧美| 国产欧美一区在线| 国产精品自拍网站| 国产精品久久久久aaaa樱花| 欧美啪啪一区| 欧美日韩国产一级| 欧美片在线观看| 欧美电影在线免费观看网站| 美女脱光内衣内裤视频久久网站| 久久国产精品色婷婷| 久久国产精品黑丝| 欧美与欧洲交xxxx免费观看| 午夜久久久久久| 亚洲欧美在线网| 午夜久久久久久| 久久成人免费网| 欧美资源在线| 久久久久www| 久久综合伊人77777尤物| 久久美女性网| 欧美大片在线观看一区| 欧美成人精品一区二区三区| 欧美电影在线| 欧美三日本三级少妇三2023| 欧美亚州在线观看| 国产日韩欧美在线视频观看| 国产日韩欧美亚洲一区| 黄色日韩精品| 亚洲精品美女91| 一区二区三区视频免费在线观看| 亚洲无人区一区| 欧美专区在线| 嫩草伊人久久精品少妇av杨幂| 亚洲高清不卡一区| 99视频+国产日韩欧美| 亚洲男女毛片无遮挡| 久久精品视频免费| 免费不卡欧美自拍视频| 欧美日韩免费观看中文| 国产日韩欧美日韩大片| 亚洲高清av在线| 亚洲在线观看视频网站| 久久亚洲高清| 亚洲区欧美区| 欧美一级视频精品观看| 欧美成人嫩草网站| 国产精品日韩欧美| 亚洲国产精品99久久久久久久久| 妖精视频成人观看www| 久久成人18免费观看| 亚洲大胆人体在线| 亚洲午夜国产成人av电影男同| 欧美一区亚洲| 欧美日韩精品免费看| 国产一区亚洲| 亚洲一区二区三区三| 牛牛影视久久网| 亚洲嫩草精品久久| 欧美精品91| 黄网站色欧美视频| 午夜精品三级视频福利| 欧美国产欧美亚洲国产日韩mv天天看完整 | 宅男精品导航| 欧美.www| 国产一区二区三区在线观看免费| 99国产精品国产精品久久| 久久久美女艺术照精彩视频福利播放 | 亚洲高清久久久| 亚欧美中日韩视频| 欧美啪啪一区| 亚洲国产老妈| 免费成人av| 欧美一级电影久久| 国产精品一二三四| 一本色道久久综合精品竹菊| 欧美二区不卡|