В простейшем случае - просто проверьте пересечение со всеми сторонами, у которых y-координаты концов находятся на разных сторонах горизонтальной линии.
Если вы хотите использовать один и тот же многоугольник с некоторыми горизонтальными сегментами - сборка отсортирована список ребер (или даже дерево интервалов) для быстрого поиска кандидатов (за время log (n) с двоичным поиском)