Алгоритмы минимального ограничивающего прямоугольника - Minimum bounding box algorithms
В вычислительная геометрия, то самая маленькая закрывающая коробка проблема в том, чтобы найти ориентированная минимальная ограничивающая рамка охватывающий набор точек. Это тип ограничивающий объем. «Наименьший» может относиться к объем, площадь, периметр, и Т. Д. коробки.
Достаточно найти самую маленькую коробку для выпуклый корпус рассматриваемых объектов. Несложно найти наименьшую ограничивающую коробку, стороны которой параллельны осям координат; сложная часть проблемы - определить ориентацию коробки.
Два измерения
Для выпуклый многоугольник, а линейное время алгоритм для охватывающий прямоугольник с минимальной площадью известен. Он основан на наблюдении, что сторона ограничивающего прямоугольника с минимальной площадью должна быть коллинеарна стороне выпуклого многоугольника.[1] Можно перечислить такие коробки за линейное время с помощью подхода, называемого вращающиеся суппорты к Годфрид Туссен в 1983 г.[2] Тот же подход применим для поиска прямоугольник с минимальным периметром.[2]
Три измерения
В 1985 г. Джозеф О'Рурк опубликовал алгоритм кубического времени, чтобы найти ограничивающий прямоугольник минимального объема трехмерного набора точек. Подход О'Рурка использует технику трехмерного вращающегося штангенциркуля и основан на леммах, характеризующих минимальный охватывающий прямоугольник:
- Должны существовать две соседние грани охватывающего бокса наименьшего объема, каждая из которых содержит край выпуклой оболочки множества точек. Этому критерию удовлетворяет одно выпуклое ребро корпуса, коллинеарное краю ящика, или два различных края корпуса, лежащие в соседних гранях ящика.
- Остальные четыре грани должны содержать только точку выпуклой оболочки. Опять же, точки, которые они содержат, не обязательно должны быть различными: одна точка корпуса, лежащая в углу коробки, уже удовлетворяет трем из этих четырех критериев.
Из этого следует, что в наиболее общем случае, когда никакие вершины выпуклой оболочки не лежат в ребрах минимального охватывающего бокса, по крайней мере 8 точек выпуклой оболочки должны лежать внутри граней бокса: две конечные точки каждого из двух ребер и еще четыре точки, по одному для каждой из оставшихся четырех граней коробки. И наоборот, если выпуклая оболочка состоит из 7 или менее вершин, по крайней мере одна из них должна лежать в пределах края минимального ограничивающего прямоугольника корпуса.[3]
Также возможно приблизить минимальный объем ограничивающей рамки с точностью до любого постоянного множителя, превышающего единицу, в линейное время. Алгоритм для этого включает поиск приближения к диаметру набора точек и использование прямоугольника, ориентированного на этот диаметр, в качестве начального приближения к ограничивающему прямоугольнику минимального объема. Затем этот начальный ограничивающий прямоугольник разбивается на сетку из более мелких кубов и точек сетки около границы выпуклый корпус входа используются как Coreset, небольшой набор точек, оптимальный ограничивающий прямоугольник которых приближается к оптимальному ограничивающему прямоугольнику исходного ввода. Наконец, алгоритм О'Рурка применяется для нахождения точного оптимального ограничивающего прямоугольника этого ядра.[4]
Доступна реализация алгоритма в Matlab.[5]
Минимальная закрывающая коробка правильный тетраэдр куб со стороной 1 /√2 тетраэдр; например, правильный тетраэдр с длиной стороны √2 вписывается в единичный куб, причем вершины тетраэдра лежат в вершинах (0,0,0), (0,1,1), (1,0,1) и (1,1,0) единичного куба.[6]
Смотрите также
Рекомендации
- ^ Фриман, Х.; Шапира, Р. (1975), "Определение окружающего прямоугольника минимальной площади для произвольной замкнутой кривой", Коммуникации ACM, 18: 409–413, Дои:10.1145/360881.360919, МИСТЕР 0375828.
- ^ а б Туссен, Г. Т. (1983), «Решение геометрических задач с вращающимися суппортами» (PDF), Proc. MELECON '83, Афины.
- ^ О'Рурк, Джозеф (1985), «Нахождение минимальных ограничивающих коробок», Международный журнал компьютерных и информационных наук, 14 (3): 183–199, Дои:10.1007 / BF00991005, МИСТЕР 0824371.
- ^ Барекет, Гилл; Хар-Пелед, Сариэль (2001), "Эффективная аппроксимация ограничивающей рамки минимального объема точки, заданной в трех измерениях", Журнал алгоритмов, 38 (1): 91–109, Дои:10.1006 / jagm.2000.1127, МИСТЕР 1810433.
- ^ Мельхиор, Самуэль (2018). "Реализация в Matlab алгоритма ограничивающего прямоугольника минимального объема"..
- ^ О'Рурк (1985), Рис. 1, стр. 186.