Мінімальна обмежувальна коробка
У геометрії, мінімальна або найменша обмежувальна коробка (англ. minimum bounding box), яка вміщує множину точок в N-вимірному просторі — паралелепіпед з найменшою мірою (площі або об'єма або гіпероб'єма, залежно від вимірності простору), що містить всю множину точок. При використанні інших видів вимірювання, мінімальне вікно зазвичай називають: «обмежувальна коробка з мінімальним периметром».
Мінімальна обмежувальна коробка множини точок — це те ж, що мінімальна обмежувальна коробка своєї опуклої оболонки, факт, який можна використати для прискорення обчислень.[1]
Терміни «вікно» або «гіперпрямокутник» походять від їх використання в декартовій системі координат, де вони візуалізуються у вигляді прямокутника (в двовимірному просторі) і прямокутного паралелепіпеда (в тривимірному просторі) і т. д. Якщо сторони чи ребра коробки паралельні осям координат, то такі коробки називають AABB від англ. axis-aligned minimum bounding box.
У двовимірному випадку це називається мінімальний обмежувальний прямокутник.
Мінімальна обмежувальна коробка вирівняна за осями[en] (англ. axis-aligned minimum bounding box, AABB) для даної множини точок є його мінімальною обмежувальною коробкою за умови обмеження, що краї коробки паралельні (декартовим) координатним осям. Це просто декартів добуток N інтервалів, кожен з яких визначається мінімальним і максимальним значенням відповідної координати для точок у множині S.
Мінімальні обмежувальні коробки вирівняні за осями використовуються для визначення наближеного місця розташування об'єкта і як дуже простий дескриптор його форми. Так, наприклад, в обчислювальній геометрії та в її додатках, коли треба знайти перетин множини об'єктів, спочатку перевіряється перетин їхніх мінімальних обмежувальних прямокутників. Оскільки, як правило, ця операція є менш важкою, ніж операція фактичного перетину (оскільки вона вимагає тільки порівняння координат), що дозволяє швидко виключати з перевірок пари фігур, які знаходяться далеко одна від одної.
Активно використовується в програмуванні (наприклад, у фізичних рушіях різних ігор) для виявлення зіткнень або перетинів різних об'єктів між собою.
Частіше за все розміри паралелепіпеда береться модуль максимальної різниці проєкцій на обрану вісь між двома точками. Хоча замість паралелепіпеда може використовуватись куб зі стороною, що дорівнює максимальному розміру об'єкта. Використовуючи цей метод, об'єкт ніколи не вийде за межі куба, хоча може втратитись точність.
Зображення спеціального інструмента, що показує параметри мінімально обмежувального прямокутника вирівняного по осях в комп'ютерних програмах 3D-моделювання називають гізмо.
Довільно орієнтований мінімальний обмежувальний прямокутник є мінімально обмежувальним прямокутником, обчисленим з урахуванням будь-яких обмежень щодо орієнтації результату. Алгоритми мінімальної обмежувальної коробки[en] засновані на методі обертового штангенінструмента[en], що можуть бути використані, щоб знайти мінімальну область або мінімальний периметр рамки двовимірного опуклого багатокутника у лінійний час, і периметр рамки будь-якого набору точок, за час необхідний для побудови опуклої оболонки цього набору[1]. Алгоритм тривимірних обертового штангенінструменту може знайти мінімальний об'єм довільно орієнтованого мінімального обмежувального прямокутника для тривимірного набору точок за кубічний час.[2]
У разі, коли об'єкт має свою власну локальну систему координат, це може бути корисно для зберігання обмежувальної рамки щодо цих осей, не вимагає ніякого перетворення таких як власні перетворення об'єкта.
При обробці цифрових зображень, обмежувальна рамка є просто координатами прямокутного кордону, яка повністю оточує цифрове зображення, коли воно поміщається на сторінку, полотно, екран або інше аналогічне двовимірне тло.
- ↑ а б 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