Алгоритм пересечения невыпуклых многоугольников , + алгоритм "сжатия" многоугольника до другого многоугольника

Подробнее на этом же форуме вопрос: Оптимизация векторной графики для КПК

Сообщение отредактировано: Slukad - 24.08.07, 04:45

Цитата Slukad @ 24.08.07, 04:29

Алгоритм пересечения невыпуклых многоугольников

Разбить невыпуклые многоугольники на выпуклые, применить алгоритм пересечения выпуклых многоунольниов попарно между получившимися многоугольниками для первой и второй фигур, полученные (выпуклые) многоигольники объединить?

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

Можно посмотреть на библиотечку GPC (General polygon clipping) (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 - 25.08.07, 10:14

Итак, на данный момент имею из стандартных:

1) Сазедленд-Ходжман. Нормальных реализаций готовых не нашел. Кроме того он неустойчив и косячит =)
2) Леонов. Суть алгоритма я уловил, но до конца не понял. Минус алгоритма - время вычисления.
3) О'Рурк. Не подходит. Полигон отсекаемый может быть не выпуклым.
4) Холверда. Не врубился - не читал )
5) Триангуляционный. Лучший по скорости и устойчивости. ПО крайней мере, так пишут. Но его реализации в cpp/c/cs/pas я не нашел. Сам триангулировать не пробовал.

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

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

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

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

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

Добавлено 27.08.07, 11:19
Нет, ссылка не подошла. Готовая библиотека мало чем поможет =(

Нате ссылку на параллельную тему. Там есть некоторое описание и алгоритм триангуляции. Триангуляция, может, кому понадобится.
Оптимизация векторной графики для КПК

У тебя алгоритм начинается с фразы:
1) Находим две такие соседние точки многоугольника, которые составляют линию, по одну сторону которой лежат все точки многоугольника.
А если таких точек нет? К примеру, это звезда?

Ну, как показала практика, это не проблема =)

В общем,
Во-первых, алгоритм надо усиливать. Сейчас он медленный слишком. А та версия, что печаталась мной - вообще сакс.

Дополнения:
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;

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

Метод этот я еще не тестировал. Возможно, завтра создам алгоритм и выложу код.

Есть еще один способ перебора точек для нахождения точки C.

Возьмем две точки 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-... пойти можно. Можно перебрать лишние точки и влипнуть в бесконечный цикл перебора (обе проверки идут по кругу).

Прикреплённая картинка