Алгоритм 2D уровня детализации (LOD) - PullRequest
Новая
       75

Алгоритм 2D уровня детализации (LOD)

5 голосов
/ 16 декабря 2010

Я искал в сети алгоритм, который позволяет вам создавать представления уровня детализации (LOD) 2D-полигонов, но я не могу найти ЛЮБУЮ достойную ссылку.Возможно, я использую неправильные условия поиска, но все результаты поиска относятся к алгоритмам 3D LOD, которые, я думаю, не могут (?) Действительно применяться в 2D.

Я уверен, что до наступления трехмерной графики многие люди работали бы над алгоритмами 2D LOD.Любые подсказки или указатели, где я могу получить больше информации?Спасибо!

Ответы [ 2 ]

4 голосов
/ 16 декабря 2010

Поиск Алгоритм Дугласа-Пекера , который используется для упрощения полилиний, но может быть расширен для поддержки многоугольников. Это то, что я использовал. Существуют также топологически стабильные расширения, если вам это нужно.

4 голосов
/ 16 декабря 2010

Помимо очевидного глупого алгоритма, который должен был бы брать каждую N-ую вершину из многоугольника (уменьшая число вершин на N), здесь есть идея, вдохновленная некоторыми 3D-алгоритмами.

Обычно в 3Dтребуется удалить грани, которые вносят меньший вклад в общий объем.Чтобы сделать это, мы попытаемся упростить «самые плоские» области модели.

Теперь в 2D вы можете перевести это, чтобы «упростить сегменты, которые имеют наименьший угол между ними. Первой наивной реализацией может быть:

  1. Вычислить все углы между сегментами Si и Si + 1 многоугольника
  2. Взять все углы ниже заданного порога (или принять М наименьших углов)
  3. Упростим сегменты, которые мы определили в 2. (замените [Pi, Pi + 1] и [Pi + 1, Pi + 2] на [Pi, Pi + 2])
  4. Повторяйте от 1. до тех пор, пока мыдостаточно много уменьшили наш многоугольник

Конечно, это не оптимально, но это должна быть хорошая сделка между качеством и скоростью. Вместо угла вы могли бы взять минимальное расстояние между средней точкойдва сегмента (Pi + 1) и потенциально упрощенный сегмент ([Pi, Pi + 2])

Редактировать:

Другой алгоритм, который я бы попробовал, если бы мне не требовалось слишком много производительности:

  1. Рассмотрим оригинальный полигон Вертльды как контрольные точки сплайна Катмулла-Рома
  2. Тесселяция этого сплайна в нужном количестве точек

Наконец, я нашел для вас некоторый исходный код по этой ссылке: http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html,, а также связанные алгоритмы: http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm

...