Войти
ПрограммированиеФорумОбщее

Триангуляция невыпуклых полигонов. Алгоритмы ? (3 стр)

Страницы: 1 2 3
#30
22:41, 6 мая 2008

Gladiator
я парился с этой адачей около месяца. по картографии прогу делал.
перелопатил кучу методов. все не то. либо слишком сложно при переносе в код - либо куча ошибок.
не всегда алгоритмы кашерно работают если вершины в float представлены и еденицы справляются если в double вершины.
и очень большие погрешности из-за чего билизко расположенные вершины зачастую принимались за совпадающие.

вобщем получил что OGL тесселирует зачетно. другого впринципе не надо и кроссплатформенно!!!

Прошло более 4 лет
#31
4:06, 6 апр 2013

Подыму тему.
Задача такая: есть 2д игра, платформер. Графика выводиться полигонами. Сами платформы и интерактивное окружение - полигоны, которые строятся фрактально проходя по двухмерной сетке игрового мира (карты). Ну считай алгоритм, который ищет оптимальные размеры квадратов и прямоугольников, что бы как можно меньше создать лишний вертексов.
В итоге получается полигон, у которого есть некая лесенка, в зависимости от разрешения самой карты мира.
Задался вопросом, как отказаться от массива карты, так как он используется только для расчета самого полигона.
Поделил мир на регионы, что бы быстрее перерисовывать области, где происходит взаимодействие.
Сам вопрос, как из множества точек, составить сам полигон? Если для замкнутого и однородной фигуры получилось (тот же Делоне), то для стены дома (к примеру) с окном - тупик полный.
Или не получиться отвязаться от двух мерной карты?
Подскажите, в какую сторону лучше копать.

Прошло более 1 года
#32
18:44, 7 авг 2014

Моя очередь поднять тему.

Накодил триангуляцию методом Зейделя (трапеизация идет по горизонтальным линиям). Для простых полигонов работает. Лажает на полигонах с горизонтальными ребрами, а также когда на горизонтальной линии более одной точки. В книге "Computational Geometry in C" рассматриваются простые полигоны, у которых нет двух вершин с одинаковой Y-координатой.

Совершенно не ясно, как соединять внутренние углы, когда на горизонтальных линиях больше одной поддерживаемой вершины (т.е. вершины ребра, с Y-координатой как у линии).

С двумя точками думаю поступить так: если угол внутренний, то можно провести хорду, тогда вместо одного полигона будет треугольник и полигон с горизонтальным ребром между двумя вершинами. Если угол внешний, то оставлять их, т.к. диагоналями такие углы соединяться не будут.

Подскажите, пожалуйста, как разруливать ситуацию с горизонтальными ребрами? По идее, можно за O(N) к каждому горизонтальному ребру провести диагональ, поделив тем самым исходный полигон. Тогда в каждом полигоне будет не более одного горизонтального ребра и можно будет особо не париться с диагоналями.

Может быть есть алгоритм Зейделя, который работает не только для полигонов из книжки?

#33
22:05, 7 авг 2014

Алгоритм Вейлера-Азертона не пробовали?

#34
9:24, 8 авг 2014

Skyblade
> Алгоритм Вейлера-Азертона не пробовали?
Нет. Как его использовать для триангуляции?

#35
10:51, 8 авг 2014

А почему нельзя повернуть ваш многоугольник на какой-нибудь угол так, чтобы исчезла ситуация с более чем одной точкой на горизонтальной линии, триангулировать, а потом повернуть обратно?

#36
19:37, 8 авг 2014

OneOne
> А почему нельзя повернуть ваш многоугольник на какой-нибудь угол так, чтобы
> исчезла ситуация с более чем одной точкой на горизонтальной линии,
> триангулировать, а потом повернуть обратно?

В принципе, подобным образом переделал алгоритм сегодня. Только не поворачивал многоугольник, а особым образом рассматривал углы с горизонтальными ребрами. Так, если первое ребро горизонтальное, то оно считается лежащим выше горизонтальной линии. Если второе горизонтальное — считаем это ребро лежащим ниже горизонтальной линии. Другими словами, я поворачивал не весь многоугольник, а лишь горизонтальные ребра.

После такой доработки алгоритм заработал на невыпуклом многоугольнике с горизонтальными ребрами.

Есть еще тестовые модели на которых валится. Один такой случай я починил, уменьшив некий глобальный ε, по которому проверяется, в том числе горизонтальность ребер, а также совпадение координат вершин.

#37
0:00, 9 авг 2014

vlavv
> Нет. Как его использовать для триангуляции?
Как-то так https://github.com/Skybladev2/Weiler-Atherton

#38
11:17, 11 авг 2014

Когда то давно делал, идею брал тут:
algolist
ну и остальных призываю тему орошать ссылками

Прошло более 7 месяцев
#39
17:24, 24 мар 2015

Для JS/C++ Зейдела можно найти https://github.com/mapbox/seidel
Для JS/C++/Java можно найти стандартный "ушной" алгоритм - https://github.com/mapbox/earcut - он немного оптимизирован через Z-curve(Квадкеи) что снижает вычислительную сложность over9000.
В итоге ушки, которые N^3 -> N^2 работают сильно быстрее чем Зейдел, который NlogN. Плюс кода сильно меньше.

Страницы: 1 2 3
ПрограммированиеФорумОбщее

Тема в архиве.