Тесселяция произвольного многоугольника мозаичными треугольниками
Мне нужно заполнить произвольный многоугольник, используя почти равномерную мозаику треугольников. Как бы я это сделал? Вы можете предоставить либо ссылки на существующие алгоритмы, либо даже просто свои идеи или подсказки.
Предполагается следующее:
- Многоугольник может быть выпуклым (но бонусные баллы, если вы придумаете алгоритм, который работает для вогнутых форм)
- Многоугольник имеет произвольное количество ребер (3 или более)
- Количество тесселяции (предпочтительно количество вершин, добавленных алгоритмом) должно быть параметризовано
- Ребра полигона могут быть разделены алгоритмом
- Треугольники должны быть почти одинаковыми по размеру и форме (т.е. углы будут стремиться к 60 градусам)
- Предпочтительно число ребер в вершине должно быть немного, а не много. Вероятно, это будет следовать из предыдущего пункта (т. Е. Алгоритм должен создавать "чистую сетку").
Это непростая проблема, и я ожидаю, что "эвристическое" решение может быть наиболее эффективным... (верно?)
4 ответа
Как отметил Джейсон Орендорфф, вы должны попытаться использовать треугольник для создания качественной сетки. У него есть множество опций, с которыми вы можете поиграть, чтобы получить изотропную сетку. Затем вы можете попытаться использовать итерационный алгоритм для создания хорошо центрированной триангуляции. Более подробная информация приведена на этой странице публикаций. Я реализовал статью 2007 года "Хорошо центрированная плоская триангуляция - итеративный подход", и она дает достойные результаты на сетках среднего размера. Хорошо центрированная триангуляция - это такая, в которой все окружные центры треугольников лежат внутри соответствующего треугольника. Поскольку вы хотите что-то немного другое, вы можете просто попытаться изменить соответствующий показатель ошибки. Вы можете найти меру "неконгруэнтности" среди треугольников и минимизировать эту ошибку. Скорее всего, такая функция ошибки будет невыпуклой, поэтому описанная нелинейная методика сопряженного градиента также хороша, как и вы.
Треугольник делает то, что вы хотите?
(Объяснения алгоритмов на этом сайте лучше, чем я мог придумать.)
На самом деле не кажется, что это сложно, алгоритмически. Или я что-то упустил?
Какой-то псевдокод:
- Поместите ограничивающий ось квадрат вокруг вашего многоугольника.
- Разделите каждый квадрат на четыре дочерних элемента (например, на квад-дерево), где количество итераций определяет ваш "объем тесселяции".
- Каждый полученный квадрат либо находится за пределами вашего многоугольника (= игнорируется), либо полностью внутри вашего многоугольника (= разбивается на два треугольника результирующего тесселяции по диагонали) или пересекает ваш многоугольник.
- Точные случаи для квадратов пересечения оставлены читателю в качестве упражнения.;-) [На данный момент времени, по крайней мере.]
Это даст вам треугольники с углами 45°/45°/90°. Если вы хотите максимально приблизиться к 60°, вам следует начать с тесселяции поверхности вашего многоугольника шестиугольниками (с размером шестиугольника, являющегося вашим "количеством тесселяции"), а затем проверить каждую из шести 60°/60°. / 60° треугольники, которые составляют эти шестиугольники. Для этих треугольников вы делаете то же самое, что и с квадратами в приведенном выше псевдокоде, за исключением того факта, что вам не нужно разбивать те, которые находятся внутри вашего многоугольника, поскольку они уже сами являются треугольниками.
Это поможет? Я думаю, что он должен работать для любого многоугольника (выпуклый / вогнутый / с отверстиями в них), учитывая, что именно то, что вы делаете для пересечения квадратов / треугольников, обрабатывает такие многоугольники.
Это можно сделать для вогнутых / выпуклых многоугольников, используя простой метод обрезания ушей (при условии, что нам не нужно поддерживать отверстия).
- Тесселяция многоугольника
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291 - Поверните ребра между треугольниками, где площадь, разделенная по периметру, станет меньше, когда ребро повернуто в новое состояние.
Это 2 шага, поэтому может быть более эффективно итеративно обрезать "лучшее" ухо, чтобы получить более ровные результаты, поэтому вам не нужно переставлять топологию как второй проход (YMMV).
(Обратите внимание, что причина, по которой здесь используются 2 шага, заключается в том, что расчет более равномерного распределения не всегда необходим).
Полное раскрытие, я столкнулся с этой проблемой сам, когда мне понадобился быстрый тесселлятор для полигонов для приложения моделирования в реальном времени.
Рабочая реализация написана на С,
которые берут и возвращают POD (float[2] массив, заполнив uint[3] массив):
- polyfill2d.c ( тесселляты)
polyfill2d_beautify.c (корректирует топологию для более ровных результатов)
(Обратите внимание, что отсечение ушей основано на libgdx с пространственной оптимизацией для проверок пересечений, чтобы масштабировать до тысяч сторон без такого существенного снижения производительности, поскольку при обрезании каждого уха каждый раз проверялись все остальные точки).
