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

[AlinkoMalinko]

Добрый день, уважаемые форумчане. У меня следующая задача: найти площадь пересечения двух многоугольников, заданных координатами вершин.
1) Многоугольники могут быть не выпуклыми и даже иметь самопересечения
2) Можно считать что у каждого не более 100 вершин.
Пол дня чтения литературы привели к следующему плану: найти точки пересечения всех сторон многоугольников при помощи "Алгоритма Бентли-Оттмана". (Если отрезки "пересеклись" концами, то этот вариант отбрасывается )
Потом по точкам самопересечения разбить каждый многоугольник на несколько.
Потом Алгоритм Уайлера — Атертона, ним найти пересечения каждого многоугольника из группы А с каждым многоугольником из группы Б.

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

[slavav]

Что такое площадь многоугольника с самопересечениями?

Способ 1.
Вам придётся все точки пересечения границ многоугольников. Без этого никак. Так как вы ограничили число вершин константой, то можно это проделать просто попарно пересекая все отрезки. После того как вы это проделали вы можете объединить границы в общий планарный граф. В этом графе вам надо будет выделить/разметить все грани. У каждой грани вы можете вычислить площадь (возможно со знаком) - теперь грань простой многоугольник. Если вы сумеете ответить на вопрос в начале моего сообщения, то вы сумеете правильно сложить/вычесть/проигнорировать площади всех граней графа чтобы получить площадь пересечения.

Способ 2.
Ищем все пересечения, как в способе 1. Теперь учимся по любой прямой искать её пересечение с пересечением многоугольников (если вы это умеете, то вы умеете отвечать на вопрос в начале сообщения). Переходим к заметанию: все вершины многоугольников и все точки пересечения сортируем по $x$. Рассмотрим полосу между двумя вершинами соседними по $x$. Её пересечение с пересечением многоугольников - комплект трапеций. Основания трапеций вам выдаёт алгоритм пересечения с прямой. У все трапеций в полосе считаете площадь. Все площади для всех полос складываете.

Способ 3.
Триангулируете оба многоугольника (это сравнительно просто для простых многоугольников, если вы не спешите). Попарно пересекаете все треугольники. Складываете площади пересечений.

И так далее...

Вряд ли вам подскажут простой способ. Все способы сложны, к сожалению.

-- 03.04.2016, 21:18 --

Ищите Препарата-Шеймос.

[_Ivana]

Реализуете процедуру проверки принадлежности произвольной точки многоугольнику (через триангуляцию или как еще), потом сыпете сверху песок Монте-Карло и считаете количество нужных песчинок.

[B@R5uk]

Я бы сделал так:

1) разрезал каждый многоугольник на непересекающиеся треугольники (потребуется нормализация многоугольника, так как в условии сказано, что границы могут иметь пересечения);
2) реализовал процедуру расчёта площади пересечения двух треугольников;
3) прошёлся бы двумя вложенными циклами по каждой паре треугольников и сложил бы результаты расчёта площади пары.

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

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

П.С. Уже предложили выше...