Определение : Многоугольник на плоскости называется монотонным относительно прямой , если каждая прямая, ортогональная пересекает не более двух раз.
Для данного многоугольника возможно ли определить, существует ли какая-либо прямая такая, что многоугольник является монотонным относительно ? Если да, то как?
Ранее я задал соответствующий вопрос (где я спросил , как определить , является ли многоугольник монотонна по отношению к определенной линии), но сейчас я заинтересован в том случае , когда является не дано или не указано заранее.
Ответы:
Возможно.
Считайте себя многоугольником и рассмотрите «вогнутые» вершины. Они точно определяют, какие линии будут пересекать многоугольник более чем в два раза. На следующем рисунке я отметил интервалы (красным) запрещенных углов. Если вы сложите их вместе и увидите дыру в красном диске, то есть разрешенные углыδ (синим цветом). В этом случае многоугольник является монотонным по отношению к любой линии наклона −1/tanδ (зеленым цветом).
Теперь алгоритм.
Пусть быть я й вершина многоугольника. Сначала вычисляют абсолютный угол α i ребра ( v i v i + 1 ) и внутренний угол β i вершины v i . Используйте функцию, доступную на всех хороших языках программирования.vi=(xi,yi) i αi (vivi+1) βi vi
atan2
β i = α i + 1 - α i + { 0, если α i + 1 ≥ α i 2 π, если α i + 1 < α я
Обратный порядок вершин, если они не в порядке против часовой стрелки, т. Е. Если не является отрицательным. ( s = - 2 π : против часовой стрелки, сs=∑iβi−nπ 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 в [ 0 , π ) . Второй случай соответствует интервалу, выходящему за пределы π (поэтому на этот раз δ должен быть «внутри»).αj αj [0,π) π δ
Вероятно, есть более быстрый способ сделать это, но в можно отсортировать значения α j mod π на γ 1 , … γ m и проверить δ ∈ { γ 1O(n2) αj mod π γ1,…γm δ∈{γ12,γ1+γ22,…,γm−1+γm2,γm+π2}
источник