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