Алгоритм пересечения выпуклых многоугольников с самой быстрой горизонтальной линией ‹-›?

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

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

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


intersection horizontal-line convex-polygon
person Miro Kropacek    schedule 21.06.2009    source источник
comment
Спасибо за ответы, ребята. К сожалению, кэширование/ограничение прямоугольников возможно очень ограниченным образом (многоугольники перемещаются/вращаются, очень мало места в оперативной памяти и т. д.), но я обязательно посмотрю.   -  person Miro Kropacek    schedule 23.06.2009
comment
Мне нужно точно такое же. Просто интересно, для чего он нужен? Каково ваше приложение?   -  person nimcap    schedule 11.11.2012

Ответы (4)


arrow_upward
3
arrow_downward

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

person balpha    schedule 21.06.2009

arrow_upward
2
arrow_downward

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

person workmad3    schedule 21.06.2009

arrow_upward
1
arrow_downward

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

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

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

person Gerald    schedule 21.06.2009

arrow_upward
0
arrow_downward

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

person Miguel    schedule 03.05.2013
comment
Было бы полезно, если бы вы добавили код в свой ответ и сослались на него ссылкой. Таким образом, если ссылка перестанет работать, ваш ответ все равно будет полезен. - person Ren; 03.05.2013