Монотонный многоугольник - Monotone polygon

Зеленый цвет указывает на одно пересечение, синий - два, а красный - три или более. Два верхних многоугольника монотонны относительно L, а два нижних - нет.

В геометрия, а многоугольник п в самолете называется монотонный по прямой L, если каждая линия ортогональна L пересекает п самое большее дважды.[1]

Аналогично многоугольная цепь C называется монотонный по прямой L, если каждая линия ортогональна L пересекает C максимум один раз.

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

Следуя терминологии для монотонные функции, первое определение описывает полигоны строго монотонные относительно L. Часть "относительно" необходима для проведения строгого / нестрогого различия: многоугольник нестрого монотонен относительно L строго монотонна относительно прямой L1 повернут из L на достаточно малый угол.

Характеристики

Предположить, что L совпадает с Икс-ось. Тогда крайняя левая и правая вершины монотонного многоугольника разбивают его границу на два монотонных многоугольника. многоугольные цепи такие, что когда вершины любой цепи пересекаются в их естественном порядке, их координаты X равны монотонно увеличение или уменьшение. Фактически, это свойство можно использовать для определения монотонного многоугольника, и оно дает многоугольнику его имя.

А выпуклый многоугольник монотонен относительно любой прямой, а многоугольник, монотонный относительно любой прямой, выпуклый.

Известно, что алгоритм линейного времени сообщает обо всех направлениях, в которых данный простой многоугольник является монотонным.[2] Он был обобщен, чтобы сообщить обо всех способах разложения простого многоугольника на две монотонные цепи (возможно, монотонные в разных направлениях).[3]

Точка в многоугольнике на вопросы относительно монотонного многоугольника можно ответить в логарифмическое время после линейное время предварительная обработка (чтобы найти крайнюю левую и крайнюю правую вершины).[1]

Монотонный многоугольник легко триангулированный в линейное время.[4]

Для данного набора точек на плоскости битонический тур представляет собой монотонный многоугольник, соединяющий точки. Минимум периметр битонический тур для заданного набора точек относительно фиксированного направления можно найти в полиномиальное время с помощью динамическое программирование.[5] Легко показать, что такой минимальный битонный тур представляет собой простой многоугольник: пара пересекающихся ребер может быть заменена более короткой непересекающейся парой с сохранением битоничности нового тура.

Разбиение многоугольника на монотонные многоугольники

Простой многоугольник легко разрезать на монотонные многоугольники в О(п бревноп) время. Однако, поскольку треугольник представляет собой монотонный многоугольник, триангуляция многоугольника фактически разрезает многоугольник на монотонные, и это может быть выполнено для простых многоугольников в О(п) время.[нужна цитата ]

Разрезание простого многоугольника на минимальное количество однородно монотонных многоугольников (т. Е. Монотонных относительно одной и той же прямой) может быть выполнено за полиномиальное время.[6]

В контексте планирование движения, два непересекающихся монотонных многоугольника могут быть разделены одним перемещением (т.е. существует перенос одного многоугольника, так что два становятся разделенными прямой линией в разные полуплоскости), и это разделение может быть обнаружено за линейное время.[7]

Обобщения

Подметаемые полигоны

Многоугольник называется подметаемый, если прямая линия может непрерывно перемещаться по всему многоугольнику так, что в любой момент ее пересечение с многоугольной областью является выпуклым множеством. Монотонный многоугольник можно развернуть линией, которая не меняет своей ориентации во время развертки. Многоугольник строго подметаемый если никакая часть его площади не пройдена более одного раза. Оба типа развертки распознаются в квадратичном времени.[8]

3D

Не существует единого прямого обобщения монотонности многоугольника на более высокие измерения.

В одном подходе сохраняющейся чертой монотонности является линия L. Трехмерный многогранник называется слабо монотонный в направлении L если все сечения ортогональны L простые многоугольники. Если сечения выпуклые, то многогранник называется слабо монотонный в выпуклом смысле.[7] Оба типа можно распознать за полиномиальное время.[8]

В другом подходе сохраняющейся одномерной чертой является ортогональное направление. Отсюда возникает понятие многогранный рельеф в трех измерениях: многогранная поверхность со свойством, что каждая вертикальная (т. е. параллельная оси Z) линия пересекает поверхность не более чем одной точкой или сегментом.

Смотрите также

Рекомендации

  1. ^ а б Препарата, Франко П.; Шамос, Майкл Ян (1985), Вычислительная геометрия - Введение, Springer-Verlag, ISBN  0-387-96131-3, 1-е издание:; 2-е издание, исправленное и расширенное, 1988 г .:; Русский перевод, 1989 г .:CS1 maint: лишняя пунктуация (связь)
  2. ^ Препарата, Франко П.; Суповит, Кеннет Дж. (1981), "Проверка простого многоугольника на монотонность", Письма об обработке информации, 12 (4): 161–164, Дои:10.1016/0020-0190(81)90091-0.
  3. ^ Раппапорт, Дэвид; Розенблум, Арнольд (1994), "Формируемые и отливаемые многоугольники", Вычислительная геометрия, 4 (4): 219–233, Дои:10.1016/0925-7721(94)90020-5.
  4. ^ Фурнье, А.; Монтуно, Д. Ю. (1984), "Триангуляция простых многоугольников и эквивалентные задачи", Транзакции ACM на графике, 3 (2): 153–174, Дои:10.1145/357337.357341, ISSN  0730-0301, S2CID  33344266
  5. ^ Введение в алгоритмы, 2-е изд., Т. Х. Кормен, К. Э. Лейзерсон, Р. Ривест, и К. Штейн, MIT Press, 2001. Задача 15-1, с. 364.
  6. ^ Лю, Робин (1988), "О разложении многоугольников на равномерно монотонные части", Письма об обработке информации, 27 (2): 85–89, Дои:10.1016 / 0020-0190 (88) 90097-X.
  7. ^ а б Туссен, Г. Т.; Эль Гинди, Х.А. (1984), "Разделение двух монотонных многоугольников за линейное время", Роботика, 2 (4): 215–220, Дои:10.1017 / S0263574700008924.
  8. ^ а б Бозе, Просенджит; Ван Кревельд, Марк (2005), «Обобщающая монотонность: о распознавании специальных классов многоугольников и многогранников путем вычисления хороших разверток», Международный журнал вычислительной геометрии и приложений, 15 (6): 591–608, Дои:10.1142 / S0218195905001877, HDL:1874/24150.