В геометрии , то минимальное или наименьшее ограничивающего или вмещающих окно для множества точек ( S ) в N измерениях есть коробка с наименьшей мерой (площадь, объем, или гиперобъема в более высоких измерениях) , в течение которого все точки лежат. Когда используются другие виды мер, минимальный прямоугольник обычно называется соответственно, например, «ограничивающий прямоугольник с минимальным периметром».
Минимальный ограничивающий прямоугольник набора точек совпадает с минимальным ограничивающим прямоугольником его выпуклой оболочки , факт, который можно эвристически использовать для ускорения вычислений. [1]
Термин «ящик» / «гипер прямоугольник» происходит от его использования в декартовой системе координат , где он действительно визуализируется как прямоугольник (двухмерный случай), прямоугольный параллелепипед (трехмерный случай) и т. Д.
В двумерном случае он называется минимальным ограничивающим прямоугольником .
Минимальная ограничивающая рамка, выровненная по оси [ править ]
Выровненный по оси минимальный ограничивающий прямоугольник (или AABB ) для данного набора точек является его минимальным ограничивающим прямоугольником с учетом ограничения, что края прямоугольника параллельны (декартовым) координатным осям. Это декартово произведение из N интервалов , каждый из которых определяется минимальным и максимальным значением соответствующей координаты для точек в S .
Выровненные по оси минимальные ограничивающие рамки используются для приблизительного местоположения рассматриваемого объекта и как очень простой дескриптор его формы. Например, в вычислительной геометрии и ее приложениях, когда требуется найти пересечения в наборе объектов, первоначальная проверка - это пересечения между их MBB. Поскольку это обычно гораздо менее затратная операция, чем проверка фактического пересечения (поскольку требует только сравнения координат), она позволяет быстро исключить проверки пар, находящихся далеко друг от друга.
Произвольно ориентированная минимальная ограничивающая рамка [ править ]
Произвольно ориентированный минимальный ограничивающий прямоугольник - это минимальный ограничивающий прямоугольник, вычисляемый без ограничений в отношении ориентации результата. Алгоритмы минимального ограничивающего прямоугольника, основанные на методе вращающегося штангенциркуля, могут использоваться для нахождения ограничивающего прямоугольника с минимальной площадью или минимальным периметром двумерного выпуклого многоугольника за линейное время и двухмерной точки, установленной за время, необходимое для построить его выпуклую оболочку с последующим вычислением за линейное время. [1] Алгоритм трехмерного вращающегося штангенциркуля может найти произвольно ориентированную ограничивающую рамку минимального объема трехмерного набора точек за кубическое время. [2]Доступны реализации последнего в Matlab, а также оптимальный компромисс между точностью и временем процессора. [3]
Объектно-ориентированная минимальная ограничивающая рамка [ править ]
В случае, когда объект имеет свою собственную локальную систему координат , может быть полезно сохранить ограничивающую рамку относительно этих осей, которая не требует преобразования при изменении собственного преобразования объекта.
Цифровая обработка изображений [ править ]
В цифровой обработке изображений , то ограничивающий прямоугольник является лишь координаты прямоугольной границы , которая полностью охватывает собой цифровое изображение , когда оно помещается на страницу, холст, экран или другой аналогичный двумерный фоне.
См. Также [ править ]
Ссылки [ править ]
- ^ a b Туссен, G.T (1983). «Решение геометрических задач с вращающимися суппортами» (PDF) . Proc. MELECON '83, Афины. Цитировать журнал требует
|journal=( помощь ) - ↑ Джозеф О'Рурк (1985), «Поиск минимальных закрывающих боксов», Параллельное программирование , Springer, Нидерланды
- ^ Чанг, Чиа-Че; Гориссен, Бастьен; Мельхиор, Самуэль (2018). "Реализация в Matlab нескольких алгоритмов ограничивающего прямоугольника минимального объема" ..
