Изменения

Существует целый класс структур типа <tex>\mathrm{skeleton}</tex>, которые описывают базовые топологические свойства объектов. Структура <tex>\mathrm{straight}\ \mathrm{skeleton}</tex> была придумала Oswin Aichholzer. Она используются в различных практических задачах (проектирование крыш для зданий) и , для доказательства некоторых теорем<ref>[http://en.wikipedia.org/wiki/Fold-and-cut_theorem Wikipedia {{---}} Fold-and-cut theorem]</ref>, но самое главное {{---}} можно оффсетить полигоны и упрощать их.

Далее будет дано процедурное определение <tex>\mathrm{straight}\ \mathrm{Определение|id=defss |definition='''Straight skeleton''' (Angular Bisector Network, ABN) полигона без самопересечений называется планарный [[Основные определения теории графов | граф]], определяющий разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие вершины straight skeleton, образовавшиеся }</tex>. То есть эта структура данных получается в результате сжатия полигонаследующей процедуры.}}

Опишем подробней, как получается такое разбиение. Мы можем Можно представить, будто все стороны прямоугольника многоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда {{Acronym | вершины будут двигаться вдоль биссектрис | Очевидный факт}}, а точки пересечения биссектрис будут являться точками, в которых рёбра полностью сократились (выродились в точку). В каждый момент времени от начала движения рёбер мы получаем слоистую структуру получается слоистая структура (рис 1.). На рис. 2 синим цветом выделен <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> {{---}} множество отрезков, образованных точками пересечения при движении сторон полигона. Чем-то структура похожа на строение крыши в домах (рис. 3). И для решения этой задачи как раз <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> и может применяться: по стенам здания необходимо спроектировать его крышу.

Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Существуют два типа изменений, в ходе которых они образуются новые вершины дерева:

Задача построения такого <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> является частным случаем задачи построения <tex> \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} </tex>, где каждому ребру можно задавать ''вес'', то есть скорость движения ребра. И эта скорость может быть даже отрицательной. Таким образом можно оффсетить полигоны и решать задачу Но задача построения <tex>\mathrm{WSS}</tex> является в общем случае неопределённой. В процессе её решения возникают неоднозначности<ref>[[Visibility graph и motion planning | motion planning]http://twak.blogspot.ru/2009/05/ambiguous-weighted-skeleton.html Ambiguous weighted skeleton]</ref>. Задача <tex> \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} </tex> является более сложной, и здесь рассматриваться не будет. Алгоритм построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> можно модифицировать, чтобы ''волновой фронт'' шёл от полигона. То есть сначала можно построить <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, тем самым упростив структуру полигона и сделав его более "гладким", а затем распространить волну в обратную сторону.