Попробуйте это:http://www.cs.man.ac.uk/~toby/alan/software/Обратите внимание, что это не бесплатно для коммерческого использования. Для более подробной информации вы можете перейти к этому аналогичному вопросу:
Простой алгоритм пересечения полигонов
Чтобы определить, просты ли два 1013 * полигоны пересекаются:
Если два простых полигона имеют пересечение без пустот, то произойдет одно из следующего:
A) Один из них имеет угол внутри внутренней частидругой.
B) Один из них имеет целый край внутри другого (углы этого края не обязательно должны быть внутри).Это означает, что середина этого края будет внутри.
C) Полигоны идентичны.
D) Есть два ребра, которые пересекаются под углом.Точка пересечения не является углом ни к одному из многоугольников.
Вам нужно проверить, идентичны ли многоугольники (имеют одинаковые углы), один из углов или один из серединыребра лежат внутри другого многоугольника или если есть два ребра, которые пересекаются где-то еще, чем в углу.
Определение, находится ли точка внутри многоугольника.