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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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