Найти столкновение между 2 полигонами

Question

Это проблема из книги:

"Вычислительная геометрия: алгоритмы и приложения", Springer-Verlag.

Даны два простых и непересекающихся многоугольника P и Q,где P лежит строго слева от Q, вычисляет первые точки на многоугольниках, которые будут сталкиваться, если P переведен горизонтально и в положительном направлении x, или определяет, что они не сталкиваются.

У меня есть квадратичное решение, но оно должно быть O ((n + m) log (n + m))

Answer 1

Сортировка обоих полигонов сверху вниз и выполнение процесса разметки.Вершины - это точки события.Во время подметания сохраняйте трассировку самого правого края P и самого левого края Q. Вы можете рисовать горизонтальные сегменты между ними и сохранять самый короткий из всех.

Answer 2

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

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

Пиксельное идеальное обнаружение столкновения