Прямолинейный скелет

Прямолинейный скелет — это метод представления многоугольника его топологическим скелетом. Прямолинейный скелет подобен в некотором роде срединным осям, но отличается тем, что скелет состоит из отрезков, в то время как срединные оси многоугольника могут включать параболические кривые.

Прямолинейные скелеты впервые определили для простых многоугольников Айхгольцер, Ауренхаммер, Альбертс и Гэртнер и обобщили до планарных прямолинейных графов Айхгольцер и Ауренхаммер. В интерпретации прямолинейных скелетов как проекции поверхности крыш их интенсивно обсуждал Г. А. Пешка.

Определение

Прямолинейный скелет многоугольника определяется как процесс непрерывного сжатия, при котором стороны движутся параллельно себе с постоянной скоростью. Когда стороны движутся таким образом, вершины, где пары сторон пересекаются, также движутся со скоростью, зависящей от угла при вершине. Если одна из этих движущихся вершин сталкивается с несмежной стороной, многоугольник распадается на два и процесс продолжается для каждой части отдельно. Прямолинейный скелет — это множество кривых, по которым проходят вершины в процессе сжатия. На иллюстрации показан процесс сжатия многоугольника (верхняя фигура), на средней фигуре синим цветом выделен прямолинейный скелет.

Алгоритмы

Прямолинейный скелет можно получить путём моделирования процесса сжатия. Много различных алгоритмов вычисления скелета поступают именно так, отличаясь во входных данных и в структурах данных, которые они используют для обнаружения комбинаторных изменений во входном многоугольнике во время сжатия.

• Айхгольцер и др. показали, каким образом можно вычислить прямолинейные скелеты для произвольных двумерных многоугольников за время O(n3 log n), или, более точно, за время O((n2+f) log n), где n — число вершин входного многоугольника, а f — число событий перевёртывания во время построения. Лучшая известная оценка для f — O(n3).
• Алгоритм со временем работы в наихудшем случае O(nr log n), или просто O(n2 log n), дали Хубер и Хелд, и они утверждают, что их алгоритм работает практически за линейное время для большинства исходных данных.
• Пётр Фелькель и Степан Обдржалек разработали алгоритм, который, по их словам, имеет эффективность O(nr + n log r). Однако поступали сообщения, что их алгоритм неверен.
• Используя структуру данных для задачи о ближайшей паре точек двух цветов, Эппштейн и Эриксон показали, каким образом построить прямолинейные скелеты при помощи линейного числа обновлений структуры данных ближайших пар точек. Структура данных ближайших пар точек, основанная на дереве квадрантов, даёт алгоритм со временем работы O(nr + n log n), а существенно более сложная структура данных приводит к лучшей асимптотической границе времени работы O(n1 + ε + n8/11 + εr9/11 + ε), или, проще, O(n17/11 + ε), где ε — любая константа, большая нуля. Это остаётся лучшей (для худшего случая) границей времени работы для построения прямолинейного скелета без ограничений входных данных, но алгоритм сложен и имплементирован не был.
• Для простых многоугольников задача построения прямолинейного скелета проще. Ченг и Вингерон показали, каким образом вычислить прямолинейный скелет простого многоугольника с n вершинами, из которых r имеют углы, большие π {displaystyle pi } , за время O(n log2 n + r3/2 log r). В худшем случае r может быть линейно и время работы упрощается до O(n3/2 log n).
• Монотонный многоугольник по отношению к прямой L — это многоугольник со свойством, что пересечение любой ортогональной L прямой с многоугольником представляет собой один отрезок. Если на вход принимается монотонный многоугольник, его прямолинейный скелет можно построить за время O(n log n).

Приложения

Каждая точка внутри входного многоугольника может быть поднята (z-координата точки) в трёхмерном пространстве на время, за которое в процессе сокращения достигается эта точка. Получающаяся трёхмерная поверхность имеет постоянную высоту на сторонах многоугольника и поднимается под постоянным углом от них, за исключением точек самого прямолинейного скелета, где части поверхности встречаются под разными углами. Таким образом, прямолинейный скелет можно использовать как набор хребтов крыши здания, опирающейся на стены в форме начального многоугольника. Нижняя фигура на иллюстрации показывает поверхность, полученную таким образом из прямолинейного скелета.

Эрик Демейн, Мартин Демейн и Анна Любив использовали прямолинейный скелет как часть техники сгибания листа бумаги, чтобы заданный многоугольник можно было получить одним прямым разрезом (Вырезание многоугольника одним разрезом), и связанные задачи оригами.

Баркет и др. использовали прямолинейные скелеты в алгоритме поиска трёхмерной поверхности, являющейся интерполяцией двух заданных ломаных.

Тэнасе и Велткамп предложили разложение вогнутых многоугольников на объединение выпуклых областей с помощью прямолинейных скелетов как шаг подготовки к распознаванию форм при обработке изображений.

Багери и Раззази использовали прямолинейные скелеты для расположения вершин в алгоритме визуализации графов с условием, что весь граф должен лежать внутри многоугольника.

Прямолинейный скелет можно использовать для построения характеристической кривой коррекций многоугольника со скошенными углами, аналогично построению характеристической кривой со скруглёнными углами, образованными из серединных осей. Томоеда и Сугихара приложили эту идею для разработки (дорожных) знаков, видимых под большими углами и с кажущейся объёмностью. Подобным же образом Асенте и Карр использовали прямолинейные скелеты для разработки цветовых градиентов для контуров букв и других фигур.

Как и для других видов скелетов, таких как срединные оси, прямолинейный скелет можно использовать для преобразования двухмерной области в её одномерное упрощённое представление. Например, Хаунтерт и Сестер описывают применение такого типа прямолинейных скелетов в геоинформационных системах для нахождения центральной линии дорог.

Любое дерево без вершин степени два можно реализовать как прямолинейный скелет выпуклого многоугольника. Выпуклая оболочка крыши, соответствующей этому прямолинейному скелету, образует реализацию Штайница графа Халина, образованного из дерева путём соединения его листьев в цикл.

Более высокие размерности

Баркет, Эппштейн, Гуудрих и Ваксман определили версию прямолинейных скелетов для трёхмерных многогранников, описали алгоритм для их вычисления и проанализировали сложность алгоритма на нескольких типах многоугольников.

Хубер, Айхгольцер, Хакл и Фогтенхубер исследовали метрические пространства, в которых соответствующие диаграммы Вороного и прямолинейные скелеты совпадают. Для двумерных пространств существует полное описание таких метрик. Для более высоких размерностей этот метод можно понимать как обобщение прямолинейных скелетов на некоторые формы объектов в произвольной размерности с помощью диаграмм Вороного.