Показать, что, учитывая точку запроса q, она может быть проверена во времени O (log n), находится ли q внутри P

Question

Я пытаюсь решить некоторые упражнения из книги «Алгоритм и приложения вычислительной геометрии», 3rd-de berg et al "главы 6 - Расположение точек. К сожалению, я не имею ни малейшего представления о том, как решить следующие упражнения:

Given a convex polygon P as an array of its n vertices in sorted order 
along the boundary. Show that, given a query point q, it can be tested in 
time O(log n) whether q lies inside P.

Моя идея до сих пор: Единственный способ я знаю, чтобы определить, находится ли точка внутри р в O (журнал N) является использование направленный ациклический граф. Чтобы использовать ориентированный ациклический граф, мне нужно его построить, что невозможно в O (log n). Итак, каким-то образом мне нужно использовать упорядоченный массив, но единственное решение, которое я знаю с массивом, будет стоить O (N).

Я надеюсь, что кто-то может мне помочь.

Answer 1

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

Чтобы найти, лежит ли q на «левой» или «права» на P[n/2] (под которым я имею в виду против часовой стрелки или по часовой стрелке вращения разница около O), мы делаем 2D кросс-продукт:

Это вещественный скаляр. Если это положительно, то a находится справа от b и наоборот. В нашем коде a = q - O и b = P[i] - O, где i является индексом точки на полигоне, который мы тестируем q против.

Затем мы можем использовать этот тест, чтобы найти «сегмент», который или «клин» q находится, то есть, какие точки полигона q находится между (на диаграмме они являются P[n/2 - 1] и P[n/2]), используя бинарный поиск, который O (log n). (Предположим, вы знаете, как это сделать)

Как только мы это узнаем, нам нужно знать, находится ли q внутри «клина».

От https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection, в течение двух линий, определенных пар точек [(x1, y1), (х2, у2)] и [(х3, у3), (x4, у4)], соответственно, их точка пересечения (Рх, Ру) задается

Compute пересечение между [Pl, Pr] и [q, O], чтобы дать s и вычислить расстояние |s - O|. Если это больше, чем |q - O|, тогда q находится внутри многоугольника P и наоборот.

(Этот шаг, конечно, O (1).Однако могут быть более элегантные способы сделать это - я просто иллюстрирую логику этого)

Общая сложность тогда O (log n) + O (1) = O (log n).