сколько отрезков линии будет пересекаться в плоскости, пересекается с горизонтальной линией? что будет самым эффективным способом найти это

Question

Я пытаюсь решить этот вызов Cyberchef :

Вам дано N очков на плоскости (пронумерованных от 1 до N); для каждого действительного i i-ая точка равна Pi = (i, Ai). Между ними имеется N − 1 линейных сегментов (пронумерованных от 1 до N − 1); для каждого действительного i, i-й сегмент линии формируется путем соединения точек Pi и Pi + 1.

Вам даны Q горизонтальных отрезков. Каждый горизонтальный отрезок запроса обозначается двумя точками, от точки (x1, y) до точки (x2, y) (где он останавливается и не распространяется дальше). Для каждого горизонтального сегмента линии вы должны найти количество сегментов линии из тех (N-1 линейных сегментов), с которыми он сталкивается в пути.

Так вот в чем проблема:

• 2 <= N <= 100000 </li>
• 1 <= Q <= 100000 </li>

Может ли кто-нибудь научить меня, какой подход будет наилучшим и наиболее эффективным с точки зрения сложности времени?

Answer 1

Я использовал kd tree для решения этой проблемы. Также не задавайте вопросы, которые являются постоянными проблемами.

Answer 2

Итак, у вас есть единственная ломаная линия, и вы хотите проверить множество запросов на пересечение с горизонтальными сегментами.

Стоит построить некоторое разбиение двоичного пространства (BSP) поверх этой ломаной линии. В этом случае вы можете проверить пересечение за O(log(n)) время, поэтому общее время составляет O(nlogn)+O(qlogn) (построение и проверка)

---

Если ваша полилиния, к счастью, выпуклый многоугольник (без один закрывающий край), все гораздо проще - просто сортируйте ребра по Y-координате и проверяйте только те, которые пересекают запрос Y (двоичный поиск, log (n) для запроса). В общем случае (невыпуклая) ваша ломаная линия может выглядеть как WMWMWMW, и вам нужно проверить слишком много ребер.

Answer 3

поэтому для решения этого вопроса вам необходимо знать алгоритм строчной линии.