Нахождение луча, пересекающего многоугольник максимально возможное число раз

Вот интересное упражнение:

Пусть P — простой, но не обязательно выпуклый многоугольник, а q — произвольная точка, не обязательно в P

Разработайте эффективный алгоритм для нахождения отрезка прямой, исходящего из q, который пересекает максимальное количество ребер P.

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

Пуля, проходящая через вершину P, засчитывается только для одной стены.

Возможен алгоритм O (n log n ). n — количество вершин или ребер, так как это многоугольник, количество ребер примерно равно количеству вершин.

Вот моя мысль:

Соединить q со всеми вершинами (допустим, что есть N вершин )в P сначала. Будет N строк или N -1 пар строк.

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

Я не думаю, что это решение O (n log n ).

Есть идеи?