найти луч, который пересекает многоугольник, столько раз, сколько это возможно

Question

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

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

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

Пуля через вершину Р получает кредит только на одну стену.

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

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

Answer 1

Таким образом, любой оптимальный ответ, не пересекающий многоугольник около любой вершины, будет иметь оптимальный ответ, который почти пересекает вершину многоугольника.

То есть, если у вас есть линия, проходящая через 10 "стен", и она не находится рядом с вершиной, вы можете перевести ее в определенном направлении в сторону вершины, сохраняя при этом 10 стенок.

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

Так что сортируйте по вертикали (nlogn) и затем найдите каждый возможный отрезок линии, который почти пересекает один (3n). Вы можете сделать это, не перераспределяя полный набор пересечений на каждой линии-кандидата, поскольку, когда линия перемещается из одной вершины в другую, она либо добавляет, либо теряет 2 стены (или остается неизменной). Вы можете отслеживать это инкрементное изменение. Постоянное время на каждом шаге.