Рассчитать, если пересечение между полигоном и растровым изображением

Question

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

У меня есть несколько идей на этот счет, исходя из определения столкновения или алгоритма заполнения, но я не думаю, что они будут оптимальными.Я уверен, что есть проверенный метод для этого, но не могу вспомнить ключевые слова.

Вот пример того, что я имею в виду:

В этом случае он должен вернуть true.

Answer 1

Я бы порекомендовал следующий алгоритм:

Пройдите границу многоугольника, используя алгоритм Брезенхэма для каждой линии, и в каждом пикселе выберите растр.Если это цвет, который вы признаете видимым, например ненулевой альфа, сообщите о пересечении.

Преимущество заключается в том, что вы работаете только с краями многоугольника, поэтому вам не нужно перебирать все пиксели внутри многоугольника.