Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
У геометрії, мінімальна або найменша обмежувальна коробка (англ. minimum bounding box), яка вміщує множину точок в N-вимірному просторі — паралелепіпед з найменшою мірою (площі або об'єма або гіпероб'єма, залежно від вимірності простору), що містить всю множину точок. При використанні інших видів вимірювання, мінімальне вікно зазвичай називають: «обмежувальна коробка з мінімальним периметром».
Мінімальна обмежувальна коробка множини точок — це те ж, що мінімальна обмежувальна коробка своєї опуклої оболонки, факт, який можна використати для прискорення обчислень.
Терміни «вікно» або «гіперпрямокутник» походять від їх використання в декартовій системі координат, де вони візуалізуються у вигляді прямокутника (в двовимірному просторі) і прямокутного паралелепіпеда (в тривимірному просторі) і т. д. Якщо сторони чи ребра коробки паралельні осям координат, то такі коробки називають AABB від англ. axis-aligned minimum bounding box.
У двовимірному випадку це називається мінімальний обмежувальний прямокутник.
Мінімальна обмежувальна коробка вирівняна за осями (AABB)
Мінімальна обмежувальна коробка [en] (англ. axis-aligned minimum bounding box, AABB) для даної множини точок є його мінімальною обмежувальною коробкою за умови обмеження, що краї коробки паралельні (декартовим) координатним осям. Це просто декартів добуток N інтервалів, кожен з яких визначається мінімальним і максимальним значенням відповідної координати для точок у множині S.
Мінімальні обмежувальні коробки вирівняні за осями використовуються для визначення наближеного місця розташування об'єкта і як дуже простий дескриптор його форми. Так, наприклад, в обчислювальній геометрії та в її додатках, коли треба знайти перетин множини об'єктів, спочатку перевіряється перетин їхніх мінімальних обмежувальних прямокутників. Оскільки, як правило, ця операція є менш важкою, ніж операція фактичного перетину (оскільки вона вимагає тільки порівняння координат), що дозволяє швидко виключати з перевірок пари фігур, які знаходяться далеко одна від одної.
Активно використовується в програмуванні (наприклад, у фізичних рушіях різних ігор) для виявлення зіткнень або перетинів різних об'єктів між собою.
Частіше за все розміри паралелепіпеда береться модуль максимальної різниці проєкцій на обрану вісь між двома точками. Хоча замість паралелепіпеда може використовуватись куб зі стороною, що дорівнює максимальному розміру об'єкта. Використовуючи цей метод, об'єкт ніколи не вийде за межі куба, хоча може втратитись точність.
Зображення спеціального інструмента, що показує параметри мінімально обмежувального прямокутника вирівняного по осях в комп'ютерних програмах 3D-моделювання називають гізмо.
Довільно орієнтований мінімальний обмежувальний прямокутник
Довільно орієнтований мінімальний обмежувальний прямокутник є мінімально обмежувальним прямокутником, обчисленим з урахуванням будь-яких обмежень щодо орієнтації результату. [en] засновані на методі [en], що можуть бути використані, щоб знайти мінімальну область або мінімальний периметр рамки двовимірного опуклого багатокутника у лінійний час, і периметр рамки будь-якого набору точок, за час необхідний для побудови опуклої оболонки цього набору. Алгоритм тривимірних обертового штангенінструменту може знайти мінімальний об'єм довільно орієнтованого мінімального обмежувального прямокутника для тривимірного набору точок за кубічний час.
Об'єктно орієнтовний мінімальний обмежувальний прямокутник
У разі, коли об'єкт має свою власну локальну систему координат, це може бути корисно для зберігання обмежувальної рамки щодо цих осей, не вимагає ніякого перетворення таких як власні перетворення об'єкта.
Цифрова обробка зображення
При обробці цифрових зображень, обмежувальна рамка є просто координатами прямокутного кордону, яка повністю оточує цифрове зображення, коли воно поміщається на сторінку, полотно, екран або інше аналогічне двовимірне тло.
Див. також
Примітки
- Toussaint, G. T. Solving geometric problems with the rotating calipers. — Proc. MELECON '83, Athens, 1983. з джерела 24 липня 2011. Процитовано 14 травня 2017.
- Joseph O'Rourke (1985), Finding minimal enclosing boxes, Parallel Programming, Springer Netherlands
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U geometriyi minimalna abo najmensha obmezhuvalna korobka angl minimum bounding box yaka vmishuye mnozhinu tochok v N vimirnomu prostori paralelepiped z najmenshoyu miroyu ploshi abo ob yema abo giperob yema zalezhno vid vimirnosti prostoru sho mistit vsyu mnozhinu tochok Pri vikoristanni inshih vidiv vimiryuvannya minimalne vikno zazvichaj nazivayut obmezhuvalna korobka z minimalnim perimetrom Geometrichni figuri obmezheni minimalnim obmezhuvalnim pryamokutnikom na ploshini Minimalna obmezhuvalna korobka mnozhini tochok ce te zh sho minimalna obmezhuvalna korobka svoyeyi opukloyi obolonki fakt yakij mozhna vikoristati dlya priskorennya obchislen Termini vikno abo giperpryamokutnik pohodyat vid yih vikoristannya v dekartovij sistemi koordinat de voni vizualizuyutsya u viglyadi pryamokutnika v dvovimirnomu prostori i pryamokutnogo paralelepipeda v trivimirnomu prostori i t d Yaksho storoni chi rebra korobki paralelni osyam koordinat to taki korobki nazivayut AABB vid angl axis aligned minimum bounding box U dvovimirnomu vipadku ce nazivayetsya minimalnij obmezhuvalnij pryamokutnik Minimalna obmezhuvalna korobka virivnyana za osyami AABB Minimalna obmezhuvalna korobka en angl axis aligned minimum bounding box AABB dlya danoyi mnozhini tochok ye jogo minimalnoyu obmezhuvalnoyu korobkoyu za umovi obmezhennya sho krayi korobki paralelni dekartovim koordinatnim osyam Ce prosto dekartiv dobutok N intervaliv kozhen z yakih viznachayetsya minimalnim i maksimalnim znachennyam vidpovidnoyi koordinati dlya tochok u mnozhini S Minimalni obmezhuvalni korobki virivnyani za osyami vikoristovuyutsya dlya viznachennya nablizhenogo miscya roztashuvannya ob yekta i yak duzhe prostij deskriptor jogo formi Tak napriklad v obchislyuvalnij geometriyi ta v yiyi dodatkah koli treba znajti peretin mnozhini ob yektiv spochatku pereviryayetsya peretin yihnih minimalnih obmezhuvalnih pryamokutnikiv Oskilki yak pravilo cya operaciya ye mensh vazhkoyu nizh operaciya faktichnogo peretinu oskilki vona vimagaye tilki porivnyannya koordinat sho dozvolyaye shvidko viklyuchati z perevirok pari figur yaki znahodyatsya daleko odna vid odnoyi Gizma nizhnogo sabtula Aktivno vikoristovuyetsya v programuvanni napriklad u fizichnih rushiyah riznih igor dlya viyavlennya zitknen abo peretiniv riznih ob yektiv mizh soboyu Chastishe za vse rozmiri paralelepipeda beretsya modul maksimalnoyi riznici proyekcij na obranu vis mizh dvoma tochkami Hocha zamist paralelepipeda mozhe vikoristovuvatis kub zi storonoyu sho dorivnyuye maksimalnomu rozmiru ob yekta Vikoristovuyuchi cej metod ob yekt nikoli ne vijde za mezhi kuba hocha mozhe vtratitis tochnist Zobrazhennya specialnogo instrumenta sho pokazuye parametri minimalno obmezhuvalnogo pryamokutnika virivnyanogo po osyah v komp yuternih programah 3D modelyuvannya nazivayut gizmo Dovilno oriyentovanij minimalnij obmezhuvalnij pryamokutnik Dovilno oriyentovanij minimalnij obmezhuvalnij pryamokutnik ye minimalno obmezhuvalnim pryamokutnikom obchislenim z urahuvannyam bud yakih obmezhen shodo oriyentaciyi rezultatu en zasnovani na metodi en sho mozhut buti vikoristani shob znajti minimalnu oblast abo minimalnij perimetr ramki dvovimirnogo opuklogo bagatokutnika u linijnij chas i perimetr ramki bud yakogo naboru tochok za chas neobhidnij dlya pobudovi opukloyi obolonki cogo naboru Algoritm trivimirnih obertovogo shtangeninstrumentu mozhe znajti minimalnij ob yem dovilno oriyentovanogo minimalnogo obmezhuvalnogo pryamokutnika dlya trivimirnogo naboru tochok za kubichnij chas Ob yektno oriyentovnij minimalnij obmezhuvalnij pryamokutnik U razi koli ob yekt maye svoyu vlasnu lokalnu sistemu koordinat ce mozhe buti korisno dlya zberigannya obmezhuvalnoyi ramki shodo cih osej ne vimagaye niyakogo peretvorennya takih yak vlasni peretvorennya ob yekta Cifrova obrobka zobrazhennya Pri obrobci cifrovih zobrazhen obmezhuvalna ramka ye prosto koordinatami pryamokutnogo kordonu yaka povnistyu otochuye cifrove zobrazhennya koli vono pomishayetsya na storinku polotno ekran abo inshe analogichne dvovimirne tlo Div takozh Obmezhuvalna sfera Bounding BoxPrimitkiToussaint G T Solving geometric problems with the rotating calipers Proc MELECON 83 Athens 1983 z dzherela 24 lipnya 2011 Procitovano 14 travnya 2017 Joseph O Rourke 1985 Finding minimal enclosing boxes Parallel Programming Springer Netherlands