Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1686212 Wed, 05 Sep 2007 10:37:37 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1686212
Возьмем две точки 0 и 1 как начальные A,B.
Начнем искать точку C влево и вправо от A и B.
Условие остановки - слева и справа у нас две соседние точки или точка одна и та же.
...
Для наглядности возьмем треугольник 23,25,14. Его основа - 24,14/
Запускаем рекурсию для грани 23-14.
Запускаем алгоритм перебора точек влево и вправо.
вправо: от 23 - 22. //за линией
влево: от 14 - 15. //записали угол
22 и 15 - не смежные и не одна и та же точка.
вп: 22 - 21. //пересечение 23-24 и 20-29
вл: 15-16. //записали угол
21 и 16 - не смежные и не одна и та же точка.
вп: 21-20. //пересечение 23-24 и 20-29
вл: 16-17. //записали угол (он останется наибольшим)
20 и 17 не смежные и не одна и та же точка
вп: 20-19. //сравнили угол без записи
вл: 17-18. //сравнили угол без записи
19 и 18 - смежные. конец перебора.

Получили точку 17.


Сложностью данного алгоритма является выбор направления влево и вправо.
К примеру, если пойти 23-24-0-1... нельзя, потому что 24 - грань базового треугольника, то
14-13-12-11-10-9-... пойти можно. Можно перебрать лишние точки и влипнуть в бесконечный цикл перебора (обе проверки идут по кругу).]]> Slukad Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1686157 Wed, 05 Sep 2007 09:55:14 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1686157
В общем,
Во-первых, алгоритм надо усиливать. Сейчас он медленный слишком. А та версия, что печаталась мной - вообще сакс.

Дополнения:
1) При поиске точки-вершины угла нужно проверять чтобы грани AC и BC (где C - данная точка) не пересекали ни одной грани многоугольника. Или будет Ж.
2) Если в начале не удалось найти две точки по условию, то берем любые соседние. Как показывает разбор алгоритма - главное в данной задаче будет поставить точку за пределами многоугольника. Тогда алгоритм сработает. На практике и без этой вещи такие многоугольники как звезда и пр. триангулируются, но не совсем корректно - алгоритм добавляет одну грань между двумя лучами звезды.
3) Нужно обязательно отсекать рекурсию. Проверка на вхождение многоугольника не будет панацеей. Рекурсия, как показывает практика, все равно попробует стартануть. Вообще, обычно, хватает одной ветки рекурсии. В идеальном случае выбора начальных точек (в начале, например, вытянутого многоугольника) возможна триангуляция вообще в одну грань (все дочерние рекурсии идут только в одну сторону, вторая грань не прорабатывается).

Третий пункт важен для многоугольников с большим количеством точек.
На практике объект с 900 точек обрабатывается ок. 13 сек.
1800 уже занимает более 5 минут.
7600 я не дождался =)

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

Объясняю идею:
1) Заводим два списка - real (все точки полигона),our;
2) Из real копируем в our все точки
Начинаем рекурсию
1) Из our удаляем точки A,B;
2) Ищем в our точку C;
3) Создаем треугольник;
4) Удаляем из our точку C;

Таким образом для каждого следующего шага рекурсии количество точек на просмотр будет меньше на одну.
Какое-никакое, а подспорье.

Метод этот я еще не тестировал. Возможно, завтра создам алгоритм и выложу код.]]> Slukad Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1682308 Fri, 31 Aug 2007 09:30:55 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1682308 1) Находим две такие соседние точки многоугольника, которые составляют линию, по одну сторону которой лежат все точки многоугольника.
А если таких точек нет? К примеру, это звезда?]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1680390 Thu, 30 Aug 2007 05:05:54 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1680390 Оптимизация векторной графики для КПК]]> Slukad Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1676617 Mon, 27 Aug 2007 10:52:24 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1676617
1) Сазедленд-Ходжман. Нормальных реализаций готовых не нашел. Кроме того он неустойчив и косячит =)
2) Леонов. Суть алгоритма я уловил, но до конца не понял. Минус алгоритма - время вычисления.
3) О'Рурк. Не подходит. Полигон отсекаемый может быть не выпуклым.
4) Холверда. Не врубился - не читал )
5) Триангуляционный. Лучший по скорости и устойчивости. ПО крайней мере, так пишут. Но его реализации в cpp/c/cs/pas я не нашел. Сам триангулировать не пробовал.

(лучший из найденных источников - http://www.inf.tsu.ru/library/Publications/2004/46.pdf)

prografix, на самом деле, учитывая, что полигон может представлять собой, скажем, реку, отсечь его не просто =) Кроме того, желательно учитывать ситуации, когда отсекается полигон, который даже не пересекает отсекающий прямоугольник.

Плюс в том, что отсекающий прямоугольник хотя бы имеет стороны, параллельные осям координат.

ors_archangel, в общем-то, предложенный тобой способ - это несколько упрощенная версия триангуляционного алгоритма. Отличие в том, что при триангуляции (взаимной) немного быстрее получается результат, хотя алгоритм триангулирования сам по себе дольше алгоритма разбиения на выпуклые многоугольники.

mo3r, спасибо, сейчас попробую.

Добавлено
Нет, ссылка не подошла. Готовая библиотека мало чем поможет =(]]> Slukad Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1675110 Sat, 25 Aug 2007 10:14:00 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1675110 http://www.cs.man.ac.uk/~toby/alan/software/).
Там, кстати, приводится ссылочка на Vatti, B.R., "A Generic Solution to Polygon Clipping", Communications of the ACM, 35(7), July 1992, pp.56-63 и на другие описания методов.]]> mo3r Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1675104 Sat, 25 Aug 2007 09:54:15 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1675104 prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1674652 Fri, 24 Aug 2007 14:46:29 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1674652 Цитата Slukad @
Алгоритм пересечения невыпуклых многоугольников
Разбить невыпуклые многоугольники на выпуклые, применить алгоритм пересечения выпуклых многоунольниов попарно между получившимися многоугольниками для первой и второй фигур, полученные (выпуклые) многоигольники объединить?]]> ors_archangel Алгоритмы https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1673744 Fri, 24 Aug 2007 04:29:36 +0000 Алгоритм пересечения невыпуклых многоугольников https://forum.sources.ru/index.php?showtopic=200324&view=findpost&p=1673744 Оптимизация векторной графики для КПК]]> Slukad Алгоритмы