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

            性能提升-空間二叉查找樹(shù)

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

            性能提升-空間二叉查找樹(shù)

            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

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

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

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

            2 Example

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

            首先,實(shí)現(xiàn)一個(gè)選擇類,通過(guò)選擇類來(lái)進(jìn)行過(guò)濾:

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

            主要實(shí)現(xiàn)兩個(gè)抽象函數(shù)Reject()和Accept(),以及設(shè)置當(dāng)前選擇器的狀態(tài)。Reject()函數(shù)用來(lái)判斷要查找的Box與當(dāng)前空間范圍的狀態(tài),如果在外,則返回True。當(dāng)兩個(gè)Box有相交時(shí),會(huì)調(diào)用Accept()函數(shù),在此函數(shù)中判斷兩個(gè)點(diǎn)的距離是否在容差范圍內(nèi),若在容差范圍內(nèi),則將點(diǎn)記錄起來(lá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個(gè)點(diǎn),并將點(diǎn)通過(guò)BoxTreeFiller添加到查找樹(shù)aBoxTree中,調(diào)用Fill函數(shù)構(gòu)造查找樹(shù)。

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

            3 Conclusion

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

             

            国产—久久香蕉国产线看观看| 久久夜色精品国产噜噜亚洲a| 久久99这里只有精品国产| 久久午夜免费视频| 漂亮人妻被黑人久久精品| 国产毛片久久久久久国产毛片 | 久久九九久精品国产免费直播| 久久国产热精品波多野结衣AV| 女同久久| 久久久久久a亚洲欧洲aⅴ| 欧美精品乱码99久久蜜桃| 99久久无码一区人妻a黑| 波多野结衣久久一区二区| 久久99国产精品一区二区| 香蕉久久av一区二区三区| 亚洲va久久久久| 亚洲一区中文字幕久久| 久久成人国产精品二三区| 久久受www免费人成_看片中文| 99久久综合狠狠综合久久止| 无码人妻精品一区二区三区久久久| 国产精品久久成人影院| 久久精品中文字幕一区| 久久99精品国产麻豆婷婷| 色综合久久天天综合| 亚洲综合伊人久久大杳蕉| 久久免费看黄a级毛片| 久久久久国色AV免费观看| 久久亚洲国产成人影院网站| 久久电影网一区| 丰满少妇高潮惨叫久久久| 久久天天躁狠狠躁夜夜网站 | 久久青青草原亚洲av无码app | 欧美黑人激情性久久| 香蕉99久久国产综合精品宅男自 | 成人免费网站久久久| 欧美黑人激情性久久| 国产午夜精品久久久久免费视| 2021久久国自产拍精品| 99精品久久久久中文字幕| 国内精品久久久久久野外|