Самая быстрая горизонтальная линия < - > алгоритм пересечения выпуклых многоугольников?
-
06-07-2019 - |
Вопрос
Мне нужно решить относительно простую вещь - у меня n-вершинный выпуклый 2D-многоугольник и горизонтальная (!) линия с некоторой координатой y. Мне нужно только одно: проверить, пересекается ли многоугольник с этой линией (то есть имеет 2 пересечения) или нет.
Самый быстрый способ, который я могу придумать, - это найти координаты min / max y внутри многоугольника (цикл повторяется n раз с двумя сравнениями и двумя хранилищами), а затем сравнить, если min y < = y < макс у.
Как-то я чувствую, что это можно решить более "математически" но я всегда заканчиваю более медленным кодом (например, векторным способом - мне нужно вычислить различия для n [i] и n [i + 1], затем умножить их, добавить и т. д. - гораздо медленнее, чем 2 cmps + store). р>
Решение
Вам нужно только проверить, есть ли у вашего многоугольника точка с y1 < у и один с у2 > у. Как только вы нашли такие две точки, все готово. Если вы можете индексировать свои точки по y-координате, это должен быть быстрый поиск.
Другие советы
Если это горизонтальная двухмерная линия, то да, описанный вами метод, вероятно, самый быстрый. Вы можете также замкнуть его, как будто вы проходите проверку частично и получаете min + max, которые являются > и < ваше значение у, то у вас есть пересечение.
Если вам придется делать это каждый раз, тогда вы, вероятно, не найдете какой-либо хитрости, чтобы сделать это быстрее.
Если вы можете кэшировать значение min / max Y с помощью многоугольника, тогда вы можете сэкономить время, не зацикливая каждую вершину каждый раз, когда вы проводите тест.
Если с вашим полигоном связан выровненный ограничивающий прямоугольник, вы можете проверить его по экстентам блока вместо полигона и получить тот же результат быстрее.
Другой подход, описанный здесь: оптимальный алгоритм, если линия пересекает выпуклый многоугольник . Но поскольку вы работаете с ортогональными линиями, вы можете немного упростить это :). Таким образом, общая сложность составляет log N без сохранения значений.