Алгоритм седельной крыши

Question

У меня есть карта (проект openstreetmap) со многими зданиями. Каждое здание является многоугольником. Как я могу сделать многоугольники частей крыши седла для каждого контура здания?

Алгоритм должен преобразовать один многоугольник в 2D в набор многоугольников в 2D (или 3D).

Причиной этого преобразования является визуализация - лучше отрисовывать изометрический вид.

Например (штриховка не важна):

альтернативный текст http://www.freeimagehosting.net/uploads/0168cec03a.png

Спасибо

Answer 1

Основная часть (например, 90%) того, что вы ищете, называется «скелет». Взгляните здесь , на рисунок под названием "Другие примеры". Эта страница взята из руководства по библиотеке компьютерной графики, поэтому вы найдете там общее описание и ссылки на (бесплатный) код.

Answer 2

Ваши примеры, кажется, предполагают, что все скаты крыши одинаковы. Дополнительные линии (если смотреть прямо сверху) - это линии равного расстояния от краев. Их можно построить, взяв угол биссектрисы между двумя ребрами.

Алгоритм будет выглядеть так:

• Начните с любых двух соседних ребер.
• Добавьте линию вдоль их биссектрисы угла.
• Возьмите следующий соседний край.
• Добавьте линию вдоль этого углового биссектрисы.
• Там, где встречаются две новые линии, отметьте новую вершину и обрежьте линии.
• Из этой вершины добавьте линию вдоль биссектрисы угла двух внешних ребер, где начинаются две линии.
• Возьми следующий край и т.д ..
• Позаботьтесь о том, чтобы правильно обрезать новые линии и управлять новыми вершинами.

Answer 3

Разве это не то, что вы получаете с помощью алгоритма водосбора с 4 соседями, плюс отметка всех ребер, которые являются локальными экстремумами, вдоль линии, перпендикулярной направлению самого быстрого подъема? (Конечно, нужно было бы добавить затенение, но не даст ли это положение вершин и углов крыши?)