Здравствуйте, m1st, Вы писали:


M>Подскажите, куда копать?

Наивное решение — floodfill.
Более быстрое — через ориентированную площадь, наименьший общий делитель и теорему Пика.

Здравствуйте, m1st, Вы писали:


M>Подскажите, куда копать?

Наивное решение — floodfill.
Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.

Если линейный размер исходного многоугольника принять равным D, то временная сложность floodfill (и прочих модификаций, уже предложенные в этой теме) будет Ω(ND+D²), а временная сложность с использованием теоремы Пика — O(NlogD).