3622
правки
Изменения
→Топологические свойства
|definition='''Straight skeleton''' (Angular Bisector Network, ABN) полигона без самопересечений называется планарный [[Основные определения теории графов | граф]], определяющий разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие вершины straight skeleton, образовавшиеся в результате сжатия полигона.
}}
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда {{Acronym | вершины будут двигаться вдоль биссектрис | Очевидный факт}}, а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). На рис. 2 синим цветом выделен <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> {{---}} множество отрезков, образованных точками пересечения при движении сторон полигона. Чем-то структура похожа на строение крыши в домах (рис. 3). И для решения этой задачи как раз <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> и может применяться: по стенам здания необходимо спроектировать его крышу.
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
| [[Файл:Skeleton_pic1.png|thumb|Рис. 1 {{---}} слои в разные моменты времени]]
| [[Файл:Skeleton_pic2.png|thumb|Рис. 2 {{---}} дерево <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>]]
| [[Файл:Skeleton_pic3.png|thumb|Рис. 3 {{---}} пример крыши по <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>]]
|}
[[Файл:Straight_roof.png|500px|center|thumb|Проектирование крыши здания по готовым стенам]]
Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Существуют два типа изменений, в ходе которых образуются новые вершины дерева:
* <tex> Edge\ event </tex> {{---}} данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
* <tex> Split\ event </tex> {{---}} происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника. И тогда стягиваемая многоугольником область разбивается на две непересекающиеся многоугольные области.
На рисунке <tex> edge\ event' </tex>ы изображён красным изображен зелёным кругом, а <tex> split\ event' </tex>ы {{---}} чёрным красным прямоугольником.
[[Файл:sk_example1skeleton_event_example.jpg|400px]]
Таким образом, <tex> event' </tex>ы соответствуют внутренним вершинам <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, гранями являются области многоугольника, заметаемые сторонами многоугольника в процессе стягивания, дуги <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> соединяют либо две внутренние вершины либо внутреннюю вершину с листом {{---}} вершиной многоугольника.
