В геометрии минимальный ограничивающий ящик или наименьший ограничивающий ящик (также известный как минимальный охватывающий ящик или наименьший охватывающий ящик ) для множества точек S в N измерениях — это ящик с наименьшей мерой ( площадью , объемом или гиперобъемом в более высоких измерениях), внутри которого лежат все точки. Когда используются другие виды меры, минимальный ящик обычно называется соответственно, например, «ограничивающий ящик с минимальным периметром».
Минимальный ограничивающий прямоугольник множества точек совпадает с минимальным ограничивающим прямоугольником его выпуклой оболочки , и этот факт можно использовать эвристически для ускорения вычислений. [1]
В двумерном случае он называется минимальным ограничивающим прямоугольником .
Минимальный ограничивающий ящик, выровненный по осям (или AABB ) для заданного набора точек — это его минимальный ограничивающий ящик, подчиняющийся ограничению, что края ящика параллельны (декартовым) осям координат. Это декартово произведение N интервалов , каждый из которых определяется минимальным и максимальным значением соответствующей координаты для точек в S .
Минимальные ограничивающие рамки, выровненные по осям, используются как приблизительное местоположение рассматриваемого объекта и как очень простое описание его формы. Например, в вычислительной геометрии и ее приложениях, когда требуется найти пересечения в наборе объектов, первоначальной проверкой являются пересечения между их MBB. Поскольку это обычно гораздо менее затратная операция, чем проверка фактического пересечения (потому что она требует только сравнения координат), она позволяет быстро исключить проверки пар, которые находятся далеко друг от друга.
Произвольно ориентированный минимальный ограничивающий ящик — это минимальный ограничивающий ящик, вычисляемый без ограничений относительно ориентации результата. Алгоритмы минимального ограничивающего ящика, основанные на методе вращающихся штангенциркулей, могут использоваться для нахождения минимальной площади или минимального периметра ограничивающего ящика двумерного выпуклого многоугольника за линейное время, а также трехмерного множества точек за время, необходимое для построения его выпуклой оболочки с последующим вычислением за линейное время. [1] Трехмерный алгоритм вращающихся штангенциркулей может найти минимально объемный произвольно ориентированный ограничивающий ящик трехмерного множества точек за кубическое время. [2] Доступны реализации последнего в Matlab, а также оптимальный компромисс между точностью и временем ЦП. [3]
В случае, когда объект имеет собственную локальную систему координат , может быть полезно хранить ограничивающую рамку относительно этих осей, что не требует преобразования, поскольку изменяется собственное преобразование объекта.
В цифровой обработке изображений ограничивающая рамка — это всего лишь координаты прямоугольной границы, которая полностью охватывает цифровое изображение , когда оно помещается на страницу, холст, экран или другой подобный двумерный фон.