Minimální ohraničující rámeček - Minimum bounding box
V geometrii je minimální nebo nejmenší ohraničující nebo uzavírací rámeček pro množinu bodů ( S ) v rozměrech N pole s nejmenší mírou (plocha, objem nebo nadbytek ve vyšších rozměrech), ve které leží všechny body. Pokud se používají jiné druhy měr, minimální pole se obvykle nazývá odpovídajícím způsobem, např. „Minimální ohraničující rámeček“.
Minimální ohraničující rámeček množiny bodů je stejný jako minimální ohraničující rámeček jeho konvexního trupu , což je skutečnost, kterou lze heuristicky použít k urychlení výpočtu.
Termín „rámeček“ / „hyperrektangel“ pochází z jeho použití v kartézském souřadnicovém systému , kde je skutečně zobrazen jako obdélník (dvourozměrný případ), obdélníkový rovnoběžnostěn (trojrozměrný případ) atd.
V dvourozměrném případě se nazývá minimální ohraničující obdélník .
Minimální ohraničovací rámeček zarovnaný s osou
Osa zarovnaný minimální ohraničující box (nebo AABB ) pro daný bod sady je jeho minimální ohraničovací rámeček s výhradou omezení, že okraje krabice byly rovnoběžné s (kartézského) souřadných os. To je kartézský produkt z N intervalů, z nichž každý je definován minimální a maximální hodnotou odpovídající souřadnici bodů v S .
Osy zarovnané minimální ohraničovací rámečky se používají k přibližnému umístění dotyčného objektu a jako velmi jednoduchý deskriptor jeho tvaru. Například ve výpočetní geometrii a jejích aplikacích, když je nutné najít průsečíky v sadě objektů, je počáteční kontrolou průsečík mezi jejich MBB. Vzhledem k tomu, že se obvykle jedná o mnohem méně nákladnou operaci než kontrola skutečné křižovatky (protože vyžaduje pouze srovnání souřadnic), umožňuje rychle vyloučit kontroly párů, které jsou od sebe vzdálené.
Libovolně orientovaný minimální ohraničující rámeček
Libovolně orientovaný minimální ohraničující rámeček je minimální ohraničující rámeček, počítaný bez omezení, pokud jde o orientaci výsledku. Algoritmy minimálního ohraničovacího rámečku založené na metodě rotujících třmenů lze použít k vyhledání ohraničovacího rámečku minimální plochy nebo minimálního obvodu dvojrozměrného konvexního polygonu v lineárním čase a dvojrozměrného bodu nastaveného v čase potřebném k postavit jeho konvexní trup následovaný výpočtem lineárního času. Algoritmus trojrozměrných rotujících třmenů může najít libovolně orientovaný ohraničovací rámeček minimálního objemu trojrozměrného bodu nastaveného v kubickém čase. K dispozici jsou implementace Matlab a také optimální kompromis mezi přesností a časem CPU.
Objektově orientovaný minimální ohraničovací rámeček
V případě, že má objekt svůj vlastní lokální souřadný systém , může být užitečné uložit ohraničující rámeček vzhledem k těmto osám, což nevyžaduje žádnou transformaci, protože se mění vlastní transformace objektu.
Digitální zpracování obrazu
V digitálním zpracování obrazu je ohraničujícím rámečkem pouze souřadnice obdélníkového ohraničení, které plně obklopuje digitální obraz, když je umístěn na stránku, plátno, obrazovku nebo jiné podobné dvojrozměrné pozadí.