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

16

Определение : Многоугольник P на плоскости называется монотонным относительно прямой L , если каждая прямая, ортогональная L пересекает п не более двух раз.

Для данного многоугольника P возможно ли определить, существует ли какая-либо прямая L такая, что многоугольник P является монотонным относительно L ? Если да, то как?

Ранее я задал соответствующий вопрос (где я спросил , как определить , является ли многоугольник монотонна по отношению к определенной линии), но сейчас я заинтересован в том случае , когда L является не дано или не указано заранее.

ком
источник
Почему бы просто не повернуть / сдвинуть систему координат так, чтобы L стала осью x а затем снова запустить старый алгоритм? Дополнительная работа должна быть управляемой в O(1) .
HDM
4
@HdM: Линия L не указана как часть ввода.
Цуёси Ито

Ответы:

16

Возможно.

Считайте себя многоугольником и рассмотрите «вогнутые» вершины. Они точно определяют, какие линии будут пересекать многоугольник более чем в два раза. На следующем рисунке я отметил интервалы (красным) запрещенных углов. Если вы сложите их вместе и увидите дыру в красном диске, то есть разрешенные углы δ (синим цветом). В этом случае многоугольник является монотонным по отношению к любой линии наклона 1/tanδ (зеленым цветом).

Астероиды

Теперь алгоритм.

Пусть быть я й вершина многоугольника. Сначала вычисляют абсолютный угол α i ребра ( v i v i + 1 ) и внутренний угол β i вершины v i . Используйте функцию, доступную на всех хороших языках программирования.vi=(xi,yi)iαi(vivi+1)βiviatan2

β i = α i + 1 - α i + { 0,  если  α i + 1α i 2 π,  если  α i + 1 < α я

αi=atan2(yi+1yi,xi+1xi)
βi=αi+1αi+{0 if αi+1αi2π if αi+1<αi

Обратный порядок вершин, если они не в порядке против часовой стрелки, т. Е. Если не является отрицательным. ( s = - 2 π : против часовой стрелки, сs=iβinπs=2π : по часовой стрелке).s=2π

Следующее только для внутренних углов больше, чем π, то есть β j > π . Красные на моей картинке. Цель состоит в том, чтобы найти угол δ, который не входит в j [ α j + 1 , α j ] по модулю π . А именно такой, что для всех j таких, что β j > π :mπβj>πδj[αj+1,αj]πjβj>π

( α j < δ < α j + 1 ),  если  α j < α j + 1

(δ<αj+1αj<δ) if αj+1<αj
(αj<δ<αj+1) if αj<αj+1

где - здесь нормализованное значение α j в [ 0 , π ) . Второй случай соответствует интервалу, выходящему за пределы π (поэтому на этот раз δ должен быть «внутри»).αjαj[0,π)πδ

Вероятно, есть более быстрый способ сделать это, но в можно отсортировать значения α j  mod  π на γ 1 , γ m и проверить δ{ γ 1O(n2)αj mod πγ1,γmδ{γ12,γ1+γ22,,γm1+γm2,γm+π2}

δL1/tanδP

jmad
источник
Какое программное обеспечение вы использовали, чтобы сделать эту иллюстрацию?
Jojman
@jojman Я не помню, но это должен был быть GIMP, я не могу вспомнить ни одну другую программу, которую я бы использовал тогда.
Джмад