Помимо очевидного тупого алгоритма, который должен был бы взять каждую N-ю вершину из многоугольника (уменьшая число вершин на N), вот идея, вдохновленная некоторыми 3D-алгоритмами.
Обычно в 3D требуется удалить лица, которые вносят свой вклад в общий объем. Для этого мы пытаемся упростить «самые плоские» области модели.
Сейчас в 2D, вы могли бы перевести это «упростить сегменты, которые имеют наименьший угол между ними первым наивным реализация может быть:.
- Compute все углы между сегментами Si и Si + 1 из многоугольник
- Возьмите все углы ниже заданного порога (или возьмите М наименьших углов)
- Упростите отрезки, идентифицированные в 2. (замените [Pi, Pi + 1] и [Pi + 1, Pi + 2 ] по [Pi, Pi + 2])
- Повторите с 1. до тех пор, пока мы не уменьшим наш полиг по
Конечно, это не оптимально, но это должно быть хорошая торговля между качеством и скоростью. Вместо того, чтобы угол, можно принять минимальное расстояние между средней точкой двух отрезков (Pi + 1) и потенциально упрощенного сегмента ([Pi, Pi + 2])
Edit:
Другой алгоритм I бы попробовать, если мне не нужно слишком много производительности:
- Рассмотрим исходные вершины многоугольника в качестве контрольных точек Catmull-Rom сплайнов
- Tesselate этот сплайн в желаемом количестве пунктов
Наконец, я нашел исходный код для вас по этой ссылке: http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html, а также связанные с ними алгоритмы: http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm
Интересный, возможно, поиск упрощения формы, абстракция изображения или даже сжатие? Каковы требования к LOD? Как в изображении будет уменьшено изображение? Это для производительности, для экономии памяти или эмуляции глубины? – 2010-12-16 12:52:07
Я смотрю на улучшение производительности существующего (устаревшего) алгоритма. По сути, я хочу разумную «сжатие-обертывание» аппроксимации многоугольника, где сохраняются основные внешние признаки и скрытые внутренние детали. +1 для предлагаемых ключевых слов. Благодаря! – tathagata 2010-12-17 10:39:25