• <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>

            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 閱讀(707) 評論(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都是為了提高搜索速度,在合適的場景中多使用這些算法,會對程序性能的提升有很大幫助。

             

            97久久精品无码一区二区| 久久久无码精品亚洲日韩蜜臀浪潮| 亚洲国产成人久久综合一| 精品久久久久久无码国产| 久久久久国产精品嫩草影院| 国产综合久久久久| 久久精品国产男包| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 亚洲成人精品久久| 2021国内久久精品| 婷婷综合久久狠狠色99h| 亚洲欧美日韩中文久久| 国产成人AV综合久久| 日日躁夜夜躁狠狠久久AV| 久久亚洲天堂| 国产精品99久久久久久猫咪 | 精品久久一区二区三区| 久久久久亚洲AV片无码下载蜜桃| 香蕉久久一区二区不卡无毒影院 | 日韩精品久久久久久| 久久久久高潮毛片免费全部播放| 亚洲乱码日产精品a级毛片久久| 久久综合狠狠综合久久| 中文字幕热久久久久久久| 亚洲国产成人精品女人久久久 | 99久久精品毛片免费播放| 色综合久久久久无码专区| 久久亚洲AV无码精品色午夜麻豆 | 亚洲中文字幕久久精品无码喷水| 久久亚洲中文字幕精品一区| 国产毛片久久久久久国产毛片 | 97久久超碰国产精品旧版| 精品精品国产自在久久高清| 久久久国产乱子伦精品作者| 亚洲第一极品精品无码久久| 亚洲αv久久久噜噜噜噜噜| 午夜人妻久久久久久久久| 久久这里只有精品18| aaa级精品久久久国产片| 久久中文娱乐网| 久久人人爽人爽人人爽av|