Алгоритм проверки полного включения одного полигона в другой?

Question

[ZaptoS]

Доброго времени суток! В данный момент озабочен поиском алгоритма проверки полного включения одного полигона в другой. Интересует верность моей идеи:
- проверяем попарно пересечения сторон исходного полигона с искомым. Если хотя бы 1 пара пересекается, значит полигон не лежит внутри целиком

+ возможно есть готовые реализации алгоритма на java или хотя бы близком к нему(чтоб не clojure какой-нибудь)?

Заранее спасибо!

Answer 1

[nirvimel]

Многоугольник A лежит полностью внутри выпуклого многоугольника B, тогда и только тогда, когда каждая из вершин A лежит внутри B.

Comments

[SeptiM]

Стоит добавить, что это работает только для выпуклого многоугольника B.

[nirvimel]

SeptiM: Благодарю за поправку.

[ZaptoS]

nirvimel: Дело в том, что я как раз рассматриваю общий случай, в том числе и не выпуклый полигон, так что ваше условие является необходимым, но недостаточным.

[nirvimel]

ZaptoS: Тогда остается ваше первоначальное решение. К нему надо только добавить проверку на то что второй многоугольник лежит не во вне первого. Для этого надо взять произвольную точку внутри второго многоугольника и проверить принадлежит ли она первому.

Answer 2

[GavriKos]

nirvimel привел вам абсолютно правильное решение. А ваше не сработает в том случае, один полигон находится полностью вне другого.

Comments

[ZaptoS]

Дело в том, что я как раз рассматриваю общий случай, в том числе и не выпуклый полигон, так что ваше условие является необходимым, но не достаточным. Мой вариант с пересечением сторон неверен в корне? Хотелось бы какого-то комментария касательно его, если можно

[GavriKos]

ZaptoS если ни одна сторона не пересекается - это еще не значит что один полигон лежит внутри другого.