Straight skeleton
Существует целый класс структур типа , которые описывают базовые топологические свойства объектов. Структура была придумала Oswin Aichholzer[1]. Она используются в различных практических задачах, а также для доказательства некоторых теорем[2].
Содержание
Топологические свойства
| Определение: |
| Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений определяет разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие точки пересечения биссектрис. |
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен — множество отрезков, образованных точками пересечения при движении сторон полигона.
Свойства дерева Straigh skeleton
TODO: Леммы о свойствах структуры Straight skeleton
Wavefront-алгоритм
TODO: Алгоритм построения простой за n^3 log n (wavefront)
Для монотонных многоугольников
TODO: Алгоритм для монотонных многоугольников за n log n
Сложный алгоритм
TODO: Алгоритм в общем виде за n*m + n log n
