Составляя мозаику произвольный полигон путем мозаичного размещения треугольников
Я должен заполнить произвольный полигон с помощью почти универсального мозаичного размещения треугольников. Как я сделал бы это? Можно обеспечить или ссылки на существующие алгоритмы или даже просто идеи или собственные подсказки.
Следующее предполагается:
- Полигон может быть выпуклым (но бонусные очки при предложении алгоритма, который работает на вогнутые формы),
- Полигон имеет произвольное число краев (3 или больше)
- Сумма составления мозаики (предпочтительно количество вершин, добавленных алгоритмом), должна быть параметризована
- Края полигона могут быть разделены на алгоритм
- Треугольники должны быть почти универсальными в размере и форме (т.е. углы будут склоняться к 60 градусам),
- Предпочтительно края числа в вершине должны быть немногими, а не многими. Это будет, вероятно, следовать из предыдущей точки (Т.е. алгоритм должен произвести "чистую сетку").
Это не легкая проблема для решения, и я ожидаю, что "эвристическое" решение может быть самым эффективным... (право?)
3 ответа
Как отметил Джейсон Орендорфф, для создания качественной сетки следует попробовать использовать треугольник. В нем есть много вариантов, с которыми вы можете поиграть, чтобы попытаться получить изотропную сетку. Затем вы можете попробовать использовать итеративный алгоритм для создания хорошо сфокусированной триангуляции. Более подробная информация приведена на этой странице публикаций . Я реализовал работу 2007 года "Хорошоцентрированная плоскостная триангуляция - итеративный подход", и она дает достойные результаты на сетках среднего размера. Хорошо центрированная триангуляция - это та, в которой все центры треугольников лежат внутри соответствующего треугольника. Так как вы хотите что-то немного другое, вы можете просто попробовать изменить метрику ошибки. Вы можете найти меру "несоответствия" среди треугольников и минимизировать эту ошибку. Скорее всего, такая функция ошибки будет неконфигурационной, поэтому описанная нелинейно-сопряженная градиентная оптимизация также применима.
.Делает ли Треугольник то, что вы хотите?
(Объяснения алгоритмов на этом сайте лучше, чем то, что я мог придумать)
.] На самом деле это не звучит так сложно, алгоритмически. Или я что-то упускаю? [
] []Some pseudocode:[
] [- ]
[
- ] Расположите осевое ограждение вокруг многоугольника плотно. [ ] [
- ] Разделите каждый квадрат на четыре дочерних (типа четырёх деревьев), где число итераций определяет ваше "количество тесселий". [ ]. [
- ] Каждая результирующая клетка либо чисто находится вне вашего полигона (=игнор), либо чисто внутри вашего полигона (= разделена на два треугольника результирующей мозаики вдоль диагонали), либо пересекает ваш полигон.[ ]. [
- ] Точные случаи квадратов пересечения оставляются читателю в качестве упражнения ;-). [На данный момент, по крайней мере.] [ ] [
] Но это даст вам треугольники с углами 45°/45°/90°. Если вы хотите, чтобы угол был как можно ближе к 60°, вам следует начать с тесселяции поверхности вашего многоугольника шестиугольниками (при этом размер шестиугольника является вашим "количеством тесселий"), а затем проверить каждый из шести треугольников 60°/60°/60°, из которых состоят эти шестиугольники. Для этих треугольников вы делаете то же самое, что и для квадратов в вышеупомянутом псевдокоде, за исключением того факта, что вам не нужно делить те треугольники, которые чисто внутри вашего многоугольника, так как они уже сами являются треугольниками.[
]. [] Это хоть какая-то помощь? Должно сработать для любого полигона (выпуклого/ вогнутого/ с отверстиями в них), я думаю, учитывая, что именно то, что вы делаете для пересекающихся квадратов/треугольников, обрабатывает такие полигоны.[
].