Minimum bounding box - Wikipedia
文章推薦指數: 80 %
Arbitrarily oriented minimum bounding box Minimumboundingbox FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Smallestboxwhichenclosessomesetofpoints Aseriesofgeometricshapesenclosedbyitsaxis-alignedminimumboundingbox(in2dimensions) Ingeometry,theminimumorsmallestboundingorenclosingboxforapointsetSinNdimensionsistheboxwiththesmallestmeasure(area,volume,orhypervolumeinhigherdimensions)withinwhichallthepointslie.Whenotherkindsofmeasureareused,theminimumboxisusuallycalledaccordingly,e.g.,"minimum-perimeterboundingbox". Theminimumboundingboxofapointsetisthesameastheminimumboundingboxofitsconvexhull,afactwhichmaybeusedheuristicallytospeedupcomputation.[1] Theterms"box"and"hyperrectangle"comefromtheirusageintheCartesiancoordinatesystem,wheretheyareindeedvisualizedasarectangle(two-dimensionalcase),rectangularparallelepiped(three-dimensionalcase),etc. Inthetwo-dimensionalcaseitiscalledtheminimumboundingrectangle. Contents 1Axis-alignedminimumboundingbox 2Arbitrarilyorientedminimumboundingbox 3Object-orientedminimumboundingbox 4Digitalimageprocessing 5Seealso 6References Axis-alignedminimumboundingbox[edit] Theaxis-alignedminimumboundingbox(orAABB)foragivenpointsetisitsminimumboundingboxsubjecttotheconstraintthattheedgesoftheboxareparalleltothe(Cartesian)coordinateaxes.ItistheCartesianproductofNintervalseachofwhichisdefinedbytheminimalandmaximalvalueofthecorrespondingcoordinateforthepointsinS. Axis-alignedminimalboundingboxesareusedtoanapproximatelocationofanobjectinquestionandasaverysimpledescriptorofitsshape.Forexample,incomputationalgeometryanditsapplicationswhenitisrequiredtofindintersectionsinthesetofobjects,theinitialcheckistheintersectionsbetweentheirMBBs.Sinceitisusuallyamuchlessexpensiveoperationthanthecheckoftheactualintersection(becauseitonlyrequirescomparisonsofcoordinates),itallowsquicklyexcludingchecksofthepairsthatarefarapart. Arbitrarilyorientedminimumboundingbox[edit] Thearbitrarilyorientedminimumboundingboxistheminimumboundingbox,calculatedsubjecttonoconstraintsastotheorientationoftheresult.Minimumboundingboxalgorithmsbasedontherotatingcalipersmethodcanbeusedtofindtheminimum-areaorminimum-perimeterboundingboxofatwo-dimensionalconvexpolygoninlineartime,andofathree-dimensionalpointsetinthetimeittakestoconstructitsconvexhullfollowedbyalinear-timecomputation.[1]Athree-dimensionalrotatingcalipersalgorithmcanfindtheminimum-volumearbitrarily-orientedboundingboxofathree-dimensionalpointsetincubictime.[2]MatlabimplementationsofthelatteraswellastheoptimalcompromisebetweenaccuracyandCPUtimeareavailable.[3] Object-orientedminimumboundingbox[edit] Inthecasewhereanobjecthasitsownlocalcoordinatesystem,itcanbeusefultostoreaboundingboxrelativetotheseaxes,whichrequiresnotransformationastheobject'sowntransformationchanges. Digitalimageprocessing[edit] Indigitalimageprocessing,theboundingboxismerelythecoordinatesoftherectangularborderthatfullyenclosesadigitalimagewhenitisplacedoverapage,acanvas,ascreenorothersimilarbidimensionalbackground. Seealso[edit] Boundingsphere Boundingvolume Minimumboundingrectangle Darbouxintegral References[edit] ^abToussaint,G.T(1983)."Solvinggeometricproblemswiththerotatingcalipers"(PDF).Proc.MELECON'83,Athens.{{citejournal}}:Citejournalrequires|journal=(help) ^JosephO'Rourke(1985),"Findingminimalenclosingboxes",ParallelProgramming,SpringerNetherlands ^Chang,Chia-Tche;Gorissen,Bastien;Melchior,Samuel(2018)."Matlabimplementationofseveralminimum-volumeboundingboxalgorithms".GitHub.. Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Minimum_bounding_box&oldid=1095161342" Categories:GeometryGeometricalgorithmsHiddencategories:CS1errors:missingperiodicalArticleswithshortdescriptionShortdescriptionisdifferentfromWikidata Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk English Views ReadEditViewhistory More Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Inotherprojects WikimediaCommons Languages ItalianoPortuguêsРусскийУкраїнська Editlinks
延伸文章資訊
- 1Bounding volume - Wikipedia
In computer graphics and computational geometry, a bounding volume for a set of objects is a clos...
- 2AABB(axis-aligned bounding box) - CSDN博客
在游戏中,为了简化物体之间的碰撞检测运算,通常会对物体创建一个规则的几何外形将其包围。 其中,AABB(axis-aligned bounding box)包围盒被称为轴对其 ...
- 3Axis-aligned bounding boxes(AABB) for the wall partitions
Download scientific diagram | Axis-aligned bounding boxes(AABB) for the wall partitions from publ...
- 4Aligned Bounding Box - an overview | ScienceDirect Topics
An axis-aligned bounding box (AABB) is simply a rectangular parallelepiped whose faces are each p...
- 53D collision detection - Game development - MDN Web Docs
As with 2D collision detection, axis-aligned bounding boxes (AABB) are the quickest algorithm to ...