Самая быстрая горизонтальная линия < - > алгоритм пересечения выпуклых многоугольников?

Question

Мне нужно решить относительно простую вещь - у меня n-вершинный выпуклый 2D-многоугольник и горизонтальная (!) линия с некоторой координатой y. Мне нужно только одно: проверить, пересекается ли многоугольник с этой линией (то есть имеет 2 пересечения) или нет.

Самый быстрый способ, который я могу придумать, - это найти координаты min / max y внутри многоугольника (цикл повторяется n раз с двумя сравнениями и двумя хранилищами), а затем сравнить, если min y < = y < макс у.

Как-то я чувствую, что это можно решить более "математически" но я всегда заканчиваю более медленным кодом (например, векторным способом - мне нужно вычислить различия для n [i] и n [i + 1], затем умножить их, добавить и т. д. - гораздо медленнее, чем 2 cmps + store).

Answer 1

Вам нужно только проверить, есть ли у вашего многоугольника точка с y1 < у и один с у2 > у. Как только вы нашли такие две точки, все готово. Если вы можете индексировать свои точки по y-координате, это должен быть быстрый поиск.

Answer 2

Если это горизонтальная двухмерная линия, то да, описанный вами метод, вероятно, самый быстрый. Вы можете также замкнуть его, как будто вы проходите проверку частично и получаете min + max, которые являются > и < ваше значение у, то у вас есть пересечение.

Answer 3

Если вам придется делать это каждый раз, тогда вы, вероятно, не найдете какой-либо хитрости, чтобы сделать это быстрее.

Если вы можете кэшировать значение min / max Y с помощью многоугольника, тогда вы можете сэкономить время, не зацикливая каждую вершину каждый раз, когда вы проводите тест.

Если с вашим полигоном связан выровненный ограничивающий прямоугольник, вы можете проверить его по экстентам блока вместо полигона и получить тот же результат быстрее.

Answer 4

Другой подход, описанный здесь: оптимальный алгоритм, если линия пересекает выпуклый многоугольник . Но поскольку вы работаете с ортогональными линиями, вы можете немного упростить это :). Таким образом, общая сложность составляет log N без сохранения значений.