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