Как определить находится ли один четырехугольник внутри другого?

Пока ответ не полный, но это частный случай алгоритма Бентли — Оттманна. Сам алгоритм про пересечение отрезков. Есть его модификация для вычисления пересечений/объединений/дополнений многоугольников.

Так как у нас задача небольшого размера, нам все сложности алгоритма не нужны, но нужна основная идея:

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

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

Итак имеем полосу, которую пересекают какие-то стороны многоугольников. Между собой они не пересекаются. Тогда их можно упорядочить по горизонтали. Например, в середине полосы проводим прямую, пересекаем с отрезками, упорядочиваем точки пересечения. Пройдем по отрезкам слева направо, выпишем какому четырёхугольнику принадлежат отрезки. Например: 1221. В этом примере второй четырёхугольник внутри первого. Есть простой способ по последовательности цифр сказать что в этой полосе второй четырёхугольник внутри первого.

Если этот тест будет верен для все полос, то все точки второго многоугольника принадлежат первому.

Звучит сложно, но не боги горшки обжигают. Решение хорошо тем что оно успешно борется с ситуациями когда вершины одного многоугольника попадают на стороны другого или когда многоугольники имеют общие вершины или стороны.

TODO: добавить картинки

Кода много: https://github.com/StanislavVolodarskiy/poly-inside-poly.

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

contains_in_stripe проверяет что стороны многоугольников внутри одной полосы идут в таком порядке что первый многоугольник содержит второй (внутри полосы).

Расчёты ведутся в double но так устроены что если передавать целые координаты (не очень большие по модулю), то вычисления точные: правильно обрабатываются случаи когда вершина одного многоугольника попадает на сторону второго, когда вершины совпадают или стороны накладываются.

Сложность алгоритма NMlog(NM), где N и M числа вершин многоугольников. В исходной задаче два четырёхугольника, с этим можно смириться. Сложность плохая в угоду "простому" коду - всего 206 строк кода.

P.S. 206 строк кода. Не устроить ли нам конкурс на самое простое решение задачи?