Straight skeleton — различия между версиями
Shersh (обсуждение | вклад) м (→Другие алгоритмы) |
Shersh (обсуждение | вклад) (добавлено про типы event'ов) |
||
| Строка 10: | Строка 10: | ||
[[Файл:Straight_skeleton_definition.png|right]] | [[Файл:Straight_skeleton_definition.png|right]] | ||
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда {{Acronym | вершины будут двигаться вдоль биссектрис | Очевидный факт}}, а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> {{---}} множество отрезков, образованных точками пересечения при движении сторон полигона. | Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда {{Acronym | вершины будут двигаться вдоль биссектрис | Очевидный факт}}, а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> {{---}} множество отрезков, образованных точками пересечения при движении сторон полигона. | ||
| + | |||
| + | Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Существуют два типа изменений, в ходе которых образуются новый вершины дерева: | ||
| + | * <tex> Edge\ event </tex> {{---}} данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными. | ||
| + | * <tex> Split\ event </tex> происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника. | ||
| + | |||
| + | На рисунке <tex> edge\ event </tex> изображён красным кругом, а <tex> split\ event </tex> {{---}} чёрным прямоугольником. | ||
[[Файл:sk_example1.jpg|400px]] | [[Файл:sk_example1.jpg|400px]] | ||
Версия 20:21, 20 октября 2014
Существует целый класс структур типа , которые описывают базовые топологические свойства объектов. Структура была придумала Oswin Aichholzer[1]. Она используются в различных практических задачах, для доказательства некоторых теорем[2], а также имеет связь с диаграммой Вороного.
Содержание
Топологические свойства
| Определение: |
| Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений определяет разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие точки пересечения биссектрис. |
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен — множество отрезков, образованных точками пересечения при движении сторон полигона.
Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева . Существуют два типа изменений, в ходе которых образуются новый вершины дерева:
- — данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
- происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника.
На рисунке изображён красным кругом, а — чёрным прямоугольником.
Свойства дерева Straight skeleton
TODO: Леммы о свойствах структуры Straight skeleton
Wavefront-алгоритм
Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры.
TODO: "Простой" алгоритм построения за n^3 (wavefront)
Другие алгоритмы
Известен алгоритм[3] построения для монотонных полигонов за время с использованием памяти. Существует и более сложный алгоритм[4], который строит за время , где — общее число вершин в полигоне, — число вогнутых вершин в полигоне.
