Straight skeleton

Эта статья находится в разработке!

Существует целый класс структур типа [math]\mathrm{skeleton}[/math], которые описывают базовые топологические свойства объектов. Структура [math]\mathrm{straight}\ \mathrm{skeleton}[/math] была придумала Oswin Aichholzer. Она используются в различных практических задачах, а также для доказательства некоторых теорем.

Топологические свойства

Определение:

Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений определяет разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие точки пересечения биссектрис.

Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен [math] \mathrm{straight}\ \mathrm{skeleton} [/math] — множество отрезков, образованных точками пересечения при движении сторон полигона.

Свойства дерева Straight skeleton

TODO: Леммы о свойствах структуры Straight skeleton

Wavefront-алгоритм

TODO: Алгоритм построения простой за n^3 log n (wavefront)

Для монотонных многоугольников

TODO: Алгоритм для монотонных многоугольников за n log n

Сложный алгоритм

TODO: Алгоритм в общем виде за n*m + n log n

Источники информации

• Wikipedia — Straight skeleton
• Straight Skeleton Implementation
• Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice
• Designing roofs and drawing phylogenetic trees