Алгоритмы минимального ограничивающего прямоугольника
В вычислительной геометрии задача наименьшего охватывающего прямоугольника — это задача поиска ориентированного минимального ограничивающего прямоугольника, охватывающего набор точек. Это своего рода ограничивающий объем . «Наименьший» может относиться к объему , площади , периметру и т. д . коробки.
Достаточно найти наименьшую объемлющую коробку для выпуклой оболочки рассматриваемых предметов. Несложно найти наименьшую ограждающую коробку, стороны которой параллельны осям координат; Сложная часть проблемы — определить ориентацию коробки.
Два измерения [ править ]
Для выпуклого многоугольника алгоритм линейного времени для охватывающего прямоугольника минимальной площади известен . Он основан на наблюдении, что сторона ограничивающего прямоугольника минимальной площади должна быть коллинеарна стороне выпуклого многоугольника. [1] Перечислить ящики такого типа можно за линейное время с помощью подхода, называемого вращающимися штангенциркулями : Годфрид Туссен в 1983 году. [2] Тот же подход применим для нахождения окружающего прямоугольника с минимальным периметром . [2] Доступна реализация алгоритма на C++, устойчивая к ошибкам с плавающей запятой. [3]
Три измерения [ править ]
В 1985 году Джозеф О'Рурк опубликовал алгоритм кубического времени для поиска рамки минимального объема трехмерного набора точек. Подход О'Рурка использует технику трехмерного вращающегося штангенциркуля и основан на леммах, характеризующих минимальную вмещающую коробку:
- Должны существовать две соседние грани объемлющего прямоугольника наименьшего объема, каждая из которых содержит ребро выпуклой оболочки множества точек. Этому критерию удовлетворяет один выпуклый край оболочки, коллинеарный краю ящика, или два различных края оболочки, лежащие на соседних гранях ящика.
- Остальные четыре грани должны содержать только точку выпуклой оболочки. Опять же, точки, которые они содержат, не обязательно должны быть различными: одна точка оболочки, лежащая в углу ящика, уже удовлетворяет трем из этих четырех критериев.
Отсюда следует, что в самом общем случае, когда ни одна вершина выпуклой оболочки не лежит на краях минимального охватывающего прямоугольника, по крайней мере 8 точек выпуклой оболочки должны лежать внутри граней прямоугольника: две конечные точки каждого из двух ребер и еще четыре точки. по одному на каждую из оставшихся четырех граней коробки. И наоборот, если выпуклая оболочка состоит из 7 или менее вершин, хотя бы одна из них должна лежать в пределах края минимального охватывающего прямоугольника оболочки. [4]
Также возможно аппроксимировать минимальный объем ограничивающей рамки с точностью до любого постоянного коэффициента, превышающего единицу, за линейное время . Алгоритм для этого включает в себя поиск приближения к диаметру набора точек и использование рамки, ориентированной по этому диаметру, в качестве начального приближения к ограничивающей рамке минимального объема. Затем этот первоначальный ограничивающий прямоугольник разбивается на сетку из более мелких кубов, а точки сетки вблизи границы выпуклой оболочки входных данных используются в качестве базового набора — небольшого набора точек, оптимальная ограничивающая рамка которого аппроксимирует оптимальную ограничивающую рамку входных данных. оригинальный ввод. Наконец, алгоритм О'Рурка применяется для нахождения точного оптимального ограничивающего прямоугольника этого базового набора. [5]
Доступна реализация алгоритма в Matlab. [6]
Минимальная окружающая рамка правильного тетраэдра представляет собой куб, длина стороны которого равна 1/ √ 2 длине стороны тетраэдра; например, правильный тетраэдр с длиной стороны √ 2 вписывается в единичный куб с вершинами тетраэдра, лежащими в вершинах (0,0,0), (0,1,1), (1,0,1) и ( 1,1,0) единичного куба. [7]
См. также [ править ]
Ссылки [ править ]
- ^ Фриман, Х .; Шапира, Р. (1975), «Определение охватывающего прямоугольника минимальной площади для произвольной замкнутой кривой», Communications of the ACM , 18 (7): 409–413, doi : 10.1145/360881.360919 , MR 0375828 , S2CID 2079688 .
- ↑ Перейти обратно: Перейти обратно: а б Туссен, Г.Т. (1983), «Решение геометрических задач с помощью вращающихся суппортов» (PDF) , Proc. МЕЛЕКОН '83, Афины .
- ^ Эберли, Д. (2015), «Прямоугольник минимальной площади, содержащий набор точек» , Geometric Tools, LLC .
- ^ О'Рурк, Джозеф (1985), «Нахождение минимальных закрывающих коробок», Международный журнал компьютерных и информационных наук , 14 (3): 183–199, doi : 10.1007/BF00991005 , MR 0824371 , S2CID 8311538 .
- ^ Бареке, Гилл; Хар-Пелед, Сариэль (2001), «Эффективное приближение ограничивающего прямоугольника минимального объема набора точек в трех измерениях», Journal of Algorithms , 38 (1): 91–109, doi : 10.1006/jagm.2000.1127 , MR 1810433 , S2CID 1542799 .
- ^ Мельхиор, Самуэль (2018). «Реализация в Matlab алгоритма ограничивающего прямоугольника минимального объема» . Гитхаб . .
- ^ О'Рурк (1985) , рис. 1, с. 186.