Только влево? 🤔
или только вправо... Или только вверх или только вниз) Влево просто проще считать накопительным эффектом для каждой строки
Я когда в рекламе Яндекса работал, была задача атрибуцировать оффлайновые билборды по геопозиции к районам Москвы. Нашел в интернете геоточки районов... Встал вопрос - как понять, биллборд внутри замкнутого многоугольника этих точек или снаружи... С учетом того, что многоугольники не обязательно выпуклые, всякий линал был отброшен и найден алгоритм - просто считать число пересечений луча, уходящего влево, с периметром района. 1/3/5/... пересечений - мы внутри контура. 0/2/4... - снаружи.
Тут такой же контур, только иногда две точки, это одно пересечение