Я просматривал сообщения об определении того, находится ли точка внутри многоугольника или нет, и ответы либо слишком расплывчаты, либо абстрактны, либо сложны для меня. Поэтому я попытаюсь задать свой вопрос конкретно о том, что мне нужно сделать.
У меня есть набор точек, описывающих непрямую линию (иногда замкнутый многоугольник). У меня есть прямоугольная область просмотра. Мне нужно как можно эффективнее определить, проходят ли какие-либо сегменты линий (или границы полигонов) через область просмотра.
Я не могу просто проверить каждую точку, чтобы увидеть, находится ли она в области обзора. Отрезок может проходить через регион без какой-либо точки внутри региона (т. е. линия проходит через регион).
Вот пример того, что я хочу определить (красный означает, что функция должна возвращать истину для набора точек, синий означает, что она должна возвращать ложь, в примере используются прямые линии и прямоугольники, потому что я не художник).
Еще одно условие, которое я хочу учитывать (хотя метод/функция могут быть отдельными), заключается в определении не только того, проходит ли граница многоугольника через прямоугольную область, но и того, полностью ли область охватывается многоугольником. Нюанс здесь в том, что в ситуации, впервые описанной выше, если меня интересует только отрисовка границ, метод должен возвращать false. Но в ситуации, описанной здесь, если мне нужно заполнить полигональную область, мне нужно, чтобы функция возвращала значение true. В настоящее время мне не нужно беспокоиться о тестировании полигонов в форме «бублика» (слава Богу!).
Вот пример, иллюстрирующий нюанс (красный прямоугольник не имеет ни одной вершины или граничного сегмента, проходящего через экранную область, но его все равно следует считать экранным):
Для вопроса «проходит ли какой-либо сегмент линии или граница многоугольника или лежит на экране?» проблемы, которую я знаю, я могу найти решение (хотя, возможно, и не эффективное). Несмотря на то, что это более подробно, условия мне понятны. А вот второй вопрос "есть ли полигональная область на экране?" проблема немного сложнее. Я надеюсь, что у кого-то может быть хорошее предложение для этого. И если одно решение легко реализуется поверх другого, ну и ладно.
Как всегда, заранее спасибо за любую помощь или предложения.
PS У меня есть функция для определения пересечения линий, но использование ее для сравнения каждого сегмента с каждой стороной экранной области кажется излишним, потому что экранная область ВСЕГДА является плоской [0, 0, ширина, высота] прямоугольник. Нет ли какого-нибудь короткого пути?
