Вращающиеся калиперы
Также: Rotating calipers · антиподальные пары · antipodal pairs · ширина многоугольника · width of a polygon · наименьший описанный прямоугольник · minimum-area rectangle · oriented bounding box · диаметр множества точек
Две параллельные прямые прижаты к выпуклому многоугольнику с двух сторон и поворачиваются вокруг него, перескакивая с вершины на вершину. За один оборот они перебирают все пары противолежащих вершин — и за O(n) находят диаметр, ширину и наименьший прямоугольник вокруг многоугольника. На кварталах центра Алматы — в какую сторону повёрнута сетка улиц.
В центре Алматы 2679 кварталов — кусков города между улицами. Опишем вокруг каждого наименьший по площади прямоугольник и посмотрим, как он повёрнут. Если бы улицы шли строго с севера на юг и с запада на восток, прямоугольники стояли бы ровно. Но у 971 квартала прямоугольник повёрнут на 4–8°, и половина из них — больше чем на 5,6°: сетка центра города развёрнута на несколько градусов. Находит эти прямоугольники приём, похожий на работу штангенциркуля: две параллельные губки сжимают многоугольник и обходят его кругом.
Цвет прямоугольника — его поворот по модулю 90°: прямоугольник, повёрнутый на 90°, смотрит в ту же сторону. Гистограмма под картой — сколько площади приходится на каждый градус поворота; самый высокий столбик — 5–6°, на него приходится почти пятая часть всей площади прямоугольников. Переключитесь на рамки вдоль осей: они больше — 200,3 квадратного километра против 143,0 — и про повороты ничего не говорят.
Идея
Всё, что можно спросить о «размере» множества точек, — самая далёкая пара, самая узкая полоса, наименьший прямоугольник, — зависит только от его выпуклой оболочки: полоса и прямоугольник выпуклы, и если в них лежат точки, лежит и оболочка. Дальше работаем с выпуклым многоугольником из n вершин.
Прижмём к многоугольнику две параллельные прямые — опорные: обе касаются его, и весь он лежит между ними. Такие две вершины, через которые проходят прямые, называются антиподальными. Повернём прямые на малый угол: точки касания не меняются, пока одна из прямых не ляжет на сторону многоугольника. Тогда её точка касания перескакивает на следующую вершину. За полоборота прямые ложатся на каждую сторону ровно один раз, а каждая точка касания обходит многоугольник один раз.
Поэтому вместо углов можно перебирать стороны. Для каждой стороны многоугольника нужна вершина, самая далёкая от её прямой, — противоположная опорная прямая проходит через неё. При переходе к следующей стороне эта вершина сдвигается только вперёд по обходу, как второй указатель в приёме двух указателей. Весь оборот — O(n) шагов, а не O(n²).
Слева — оболочка района и две пары опорных прямых: одна пара под углом θ, другая — перпендикулярно. Справа — ширина полосы и площадь прямоугольника для каждого угла от 0 до 180°, тонкими вертикалями отмечены направления сторон оболочки. Самые низкие точки обеих кривых попадают на эти вертикали. Это не совпадение.
Почему достаточно сторон
Среди всех полос, содержащих выпуклый многоугольник, у самой узкой одна граница содержит сторону многоугольника. То же верно для прямоугольника наименьшей площади: одна его сторона лежит на стороне многоугольника.
Пусть θ — угол прямых. Пока θ меняется внутри промежутка между двумя соседними «особыми» углами — направлениями сторон, — точки касания постоянны. Пусть это вершины P и Q на двух прямых, и a — длина вектора P − Q. Ширина полосы — проекция P − Q на нормаль к прямым, и при повороте прямых она меняется как w(θ) = a cos(θ − β), где постоянный угол β задан направлением P − Q. Внутри промежутка w > 0, а у функции a cos(θ − β) единственный внутренний минимум — там, где косинус равен −1, то есть w < 0. Значит, внутри промежутка минимума нет, и наименьшее значение — на его краю, где одна из прямых лежит на стороне.
Для прямоугольника особые углы — направления сторон и они же плюс 90°; внутри промежутка четыре точки касания постоянны. Ширина в одном направлении — a cos(θ − α′), в перпендикулярном — b sin(β′ − θ), и площадь
A(θ) = ab/2 · [sin(β′ − α′) + sin(α′ + β′ − 2θ)].
Это прибавка к постоянной, пропорциональная синусу от линейной функции θ. Внутренний минимум возможен только там, где этот синус равен −1, а тогда A ≤ ab/2 · (1 − 1) = 0 — но площадь прямоугольника вокруг многоугольника положительна. Значит, и площадь достигает наименьшего значения на краю промежутка, где одна из сторон прямоугольника лежит на стороне многоугольника.
Для самой далёкой пары — диаметра — рассуждение другое: если p и q — самые далёкие точки, прямые через них перпендикулярно отрезку pq опорные: точка за такой прямой была бы дальше от другого конца. Значит, диаметр — среди антиподальных пар, а их калиперы перечисляют все за один оборот. Для каждой стороны достаточно сравнить с самой далёкой вершиной оба конца стороны.
Код
Для наименьшего прямоугольника нужны три упора на сторону: самая далёкая вершина j и две крайние вдоль стороны — r впереди и l позади. Все три только идут вперёд. Сравнения при движении — векторные и скалярные произведения в целых числах; деление на длину стороны нужно лишь для самого ответа.
Листинг сверяет каждый квартал с перебором «каждая сторона против каждой вершины» и выдаёт те же числа: наибольшая доля площади — у поворотов 5–6°. Кварталы здесь маленькие — у оболочки в среднем пять вершин, самое большее 26, — и O(n) против O(n²) на них ничего не решает. Разница появляется на больших многоугольниках.
Сколько это стоит
Каждый упор за оборот проходит оболочку не больше одного раза, поэтому на n сторон уходит O(n) шагов: при тысяче вершин калиперы в Python быстрее перебора почти в сто раз, при шестнадцати тысячах в Go — больше чем в десять тысяч. Перед калиперами нужна оболочка — O(n log n), и она обычно дороже самих калиперов.
Где легко ошибиться
- Невыпуклый многоугольник. Опорные прямые и антиподальные пары определены для выпуклого; для любого контура сначала строится оболочка. Калиперы на невыпуклом многоугольнике упираются в «пещеры» и пропускают ответ.
- Точки на сторонах и повторы. Три вершины на одной прямой дают сторону нулевого поворота, и упор может застрять на ней. Проще выбросить такие точки при построении оболочки.
- Только одна вершина из пары. Когда сторона многоугольника параллельна противоположной, антиподальных вершин у неё две, и для диаметра нужно проверить обе. Сравнение обоих концов стороны с самой далёкой вершиной это покрывает.
- Ширина — не диаметр. Самая узкая полоса — минимум по направлениям, самая далёкая пара — максимум. Если перепутать, проём для детали получится в несколько раз шире нужного.
- Наименьший по площади — не наименьший по периметру и не самый узкий. Это разные прямоугольники, хотя у каждого из них одна сторона лежит на стороне оболочки, — и все находятся одним оборотом калиперов.
Где работает
Геометрические библиотеки. В GEOS наименьший прямоугольник вокруг геометрии считается двойными вращающимися калиперами за линейное время, ширина — отдельной процедурой MinimumDiameter. Через GEOS их получают PostGIS и Shapely: повёрнутая рамка вокруг участка, здания или острова.
Компьютерное зрение. Найденный на снимке контур — номер машины, деталь на конвейере, клетка под микроскопом — обводят повёрнутым прямоугольником: он показывает, как объект лежит, и его стороны дают длину и ширину. Так работает minAreaRect в OpenCV.
Раскрой и упаковка. Из какого наименьшего листа вырезать деталь, в какой самый узкий проём её пронести, какой длины нужен ящик — всё это ширина, диаметр и наименьший прямоугольник оболочки.
Задачи о двух многоугольниках. Тем же оборотом находятся «мосты» — общие опорные прямые двух выпуклых многоугольников, — а через них расстояние между многоугольниками и оболочка их объединения.
История
Герберт Фримен и Рут Шапира в 1975 году доказали, что у наименьшего прямоугольника вокруг замкнутой кривой одна сторона лежит на стороне её выпуклой оболочки, и искали его перебором сторон. Майкл Шеймос в диссертации 1978 года нашёл диаметр множества точек за O(n) после оболочки, перебирая антиподальные пары. Годфрид Туссен в 1983 году показал, что это один приём, дал ему имя «вращающиеся калиперы» и решил им несколько задач — от наименьшего прямоугольника за O(n) до расстояния между двумя выпуклыми многоугольниками. Ширину множества точек калиперами в 1988 году нашли Майкл Хоул и Туссен.
Задачи
Самая узкая полоса и наименьший прямоугольник вокруг детали, а в задаче к статье о выпуклой оболочке — самая далёкая пара.
Пронести в проём Самая далёкая параДанные: Дороги Алматы © участники OpenStreetMap, ODbL Границы районов Алматы © участники OpenStreetMap, ODbL