Как проверить, пересекает ли сегмент линии простой многоугольник

Question

Я пытаюсь реализовать алгоритм графа видимости из книги вычислительной геометрии Де Берга и др. Вы можете найти алгоритм здесь: http://cs.smith.edu/~streinu/Teaching/Courses/274/Spring98/Projects/Philip/fp/algVisibility.htm

У меня возникли проблемы с первой линией ВИДИМОМ алгоритма:

if pwi intersects the interior of the obstacle of which wi is a vertex, locally at wi then return false 

В книге говорится, что она должна принять O (Г п) (где п все точки в плоскости), но это не объясняет, как сделать проверку. Найденные алгоритмы принимают линейное время по отношению к числу вершин многоугольника.

Любая помощь приветствуется.

Answer 1

Я считаю, что шаг, с которым вы беспокоитесь занимает не более O (журнал п) время, , потому что вы можете использовать бинарный поиск на препятствие, для которого ж _я является вершиной.