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

Материал из testwiki
Перейти к навигации Перейти к поиску
Процесс сокращения, прямолинейный скелет (синий) и модель крыши.

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

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

Определение

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

Алгоритмы

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

  • Айхгольцер и др.Шаблон:SfnШаблон:Sfn показали, каким образом можно вычислить прямолинейные скелеты для произвольных двумерных многоугольников за время O(n3 log n), или, более точно, за время O((n2+f) log n), где n — число вершин входного многоугольника, а f — число событий перевёртывания во время построения. Лучшая известная оценка для f — O(n3).
  • Алгоритм со временем работы в наихудшем случае O(nr log n), или просто O(n2 log n), дали Хубер и Хелд, и они утверждают, что их алгоритм работает практически за линейное время для большинства исходных данныхШаблон:SfnШаблон:Sfn.
  • Пётр Фелькель и Степан Обдржалек разработали алгоритм, который, по их словам, имеет эффективность O(nr + n log r)Шаблон:SfnШаблон:Sfn. Однако поступали сообщения, что их алгоритм неверенШаблон:SfnШаблон:Sfn.
  • Используя структуру данных для задачи о ближайшей паре точек двух цветов, Шаблон:Не переведено 5 и Эриксон показали, каким образом построить прямолинейные скелеты при помощи линейного числа обновлений структуры данных ближайших пар точек. Структура данных ближайших пар точек, основанная на дереве квадрантов, даёт алгоритм со временем работы O(nr + n log n), а существенно более сложная структура данных приводит к лучшей асимптотической границе времени работы Шаблон:Nowrap, или, проще, Шаблон:Nowrap, где ε — любая константа, большая нуляШаблон:Sfn. Это остаётся лучшей (для худшего случая) границей времени работы для построения прямолинейного скелета без ограничений входных данных, но алгоритм сложен и имплементирован не был.
  • Для простых многоугольников задача построения прямолинейного скелета проще. Ченг и Вингерон показали, каким образом вычислить прямолинейный скелет простого многоугольника с n вершинами, из которых r имеют углы, большие π, за время O(n log2 n + r3/2 log r)Шаблон:Sfn. В худшем случае r может быть линейно и время работы упрощается до O(n3/2 log n).
  • Шаблон:Не переведено 5 по отношению к прямой L — это многоугольник со свойством, что пересечение любой ортогональной L прямой с многоугольником представляет собой один отрезок. Если на вход принимается монотонный многоугольник, его прямолинейный скелет можно построить за время O(n log n)[1].

Приложения

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

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

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

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

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

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

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

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Книга Шаблон:Книга

Шаблон:Книга Шаблон:Refend

Ссылки

Шаблон:Rq

  1. ↑ Шаблон:Harv. Как заметил Бидл с соавторами, алгоритм, который ранее опубликовал Дас с соавторами, не является корректным в том виде, в каком он описан, и работает хорошо только для входных данных в общем положении, когда не возникает событий вершина-вершина Шаблон:Harv
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Прямолинейный_скелет&oldid=18340