Алгоритм крыши седла
У меня есть карта (openstreetmap проект) со многими зданиями. Каждое здание является полигоном. Как я могу сделать полигоны частей крыши седла для каждой схемы здания?
Алгоритм должен преобразовать один полигон в 2D к набору полигонов в 2D (или 3D).
Причиной этого преобразования является визуализация - лучше представляющее изометрическое представление.
Например (штриховка не важна):
сопроводительный текст http://www.freeimagehosting.net/uploads/0168cec03a.png
Спасибо
3 ответа
Основная часть (например, 90%) того, что вы ищете, называется «скелет». Взгляните здесь , на рисунок под названием «Другие примеры». Эта страница - из руководства библиотеки компьютерной графики, поэтому вы найдете там общее описание и ссылки на (бесплатный) код.
Ваши примеры, похоже, предполагают, что все скаты крыши одинаковы. Тогда дополнительные линии (если смотреть непосредственно сверху) - это линии равного расстояния от краев. Их можно построить, взяв биссектрису угла между двумя краями.
Алгоритм выглядит следующим образом:
- Начните с любых двух соседних ребер.
- Добавьте линию вдоль их биссектрисы угла.
- Возьмите следующее соседнее ребро.
- Добавьте линию вдоль биссектрисы этого угла.
- Там, где две новые линии пересекаются, отметьте новую вершину и скрепите линии.
- Из этой вершины добавьте линию вдоль биссектрисы угла двух внешних ребер, где возникли две линии.
- Возьмите следующее ребро и т.д..
- Следите за тем, чтобы правильно зажать новые линии и управлять новыми вершинами.
Разве это не то, что вы получаете с алгоритмом водораздела с 4 соседями, плюс отметка всех ребер, которые являются локальными экстремумами, вдоль линии, перпендикулярной направлению самое быстрое восхождение? (Затенение, конечно, нужно как-то добавить, но разве это не даст вам положение вершин и углов крыши?)