Пересечение многоугольников.

[Imperator]

На плоскости заданы координатами своих вершин два многоугольника (необязательно выпуклых). Как можно определить, пересекаются ли они?

[незваный гость]

Вас интересует алгорифм? Для компа? Тогда это — вычислительная геометрия, и ее лучше переместить в «Computer Science».

Один из подходов (сложность $\Theta(n \times m)$: просто проверяете попарное пересечение отрезков. Обычно это организовывают при помощи алфавитного упорядоченного отрезков. (я обычно рекомендую книгу Препарата Ф., Шеймос М. — Вычислительная геометрия: введение).

[Dandan]

Рассмотрения попарного пересечения отрезков не хватит, один многоугольник может лежать в другом (я так понимаю тогда тоже имеет место пересечение). В этом случае нужно брать точку одного многоугольника и смотреть, лежит ли она в другом. Это не очень сложно делается. Проводим через эту точку луч. Если он пересекает границу многоугольника в нечетном числе точек(вершина считается за две) - значит взятая точка лежит внутри, иначе - снаружи.

[незваный гость]

Dandan писал(а):

Рассмотрения попарного пересечения отрезков не хватит

Тоже верно.

Dandan писал(а):

пересекает нечетном числе точек(вершина считается за две)

С этим нужно поосторожнее. Намного поосторожнее. Потому как возможны два варианта (1) луч касается ломаной внешним образом (считаем два раза); (2) пересекает ломаную (считаем один раз). Проще всего этого избежать, выбрав луч не проходящий ни через одну из точек. Благо в выборе луча мы свободны. Альтернатива (может быть и много лучшая): смотреть, находятся ли свободные концы отрезков в разных полуплоскостях. Плюс проверять на еще одну радость, лежащие на луче отрезки (их выбрасываем, но как-бы совмещаем смежные с ними).

Итого, суммарный алгорифм выглядит так: быстро проверяем вложенность многоугольника $A$ в $B$, потом $B$ в $A$. Если не повезло и ответа не получили, гоним пересечение отрезков.

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

[Zai]

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

[sadomovalex]

любой многоугольник можно представить в виде объединения конечного числа треугольников - провести триангуляцию. А для треугольника проверить принадлежность точки не трудно

По поводу же определения, лежит ли точка внутри многоугольника, в википедии есть статья Алгоритм точки в многоугольнике
PS. незваный гость, спасибо за книгу

проверяйте отображение ссылок // нг

[Someone]

Dandan писал(а):

(вершина считается за две)

Это неправильно. Иногда за две, а иногда за одну. А ещё целая сторона может лежать на этом луче, и не одна... Лучше выбирать луч, не проходящий через вершины.

[Dandan]

ну да, да, уже писали, что лучше чтобы луч не проходил через вершины и был непараллелен сторонам

[_irdis_]

а может лучше так:
берете, описываете множество неравенствами вида k*x+b<=y
потом решаете полученную систему чем-нибудь(хоть бы симплекс-метод). И узнаете, есть ли точки принадлежащие этому множеству.

[Gen.Lio]

Привет,

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

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

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