Монотонный многоугольник - Monotone polygon
В геометрии , А многоугольника Р в плоскости, называется монотонно по отношению к прямой линии L , если каждая прямая ортогональна L пересекающая P не более чем в два раза.
Аналогично, ломаная цепь C называется монотонной относительно прямой L , если каждая прямая, ортогональная L, пересекает C не более одного раза.
Для многих практических целей это определение может быть расширено , чтобы случаи , когда некоторые ребра P ортогональны L и простой многоугольник можно назвать монотонным , если отрезок , который соединяет две точки Р и ортогонально L полностью принадлежит P .
Следуя терминологии для монотонных функций , первое определение описывает многоугольники строго монотонна относительно L . Часть «относительно» необходима для проведения строгого / нестрогого различия: многоугольник, не строго монотонный относительно L , строго монотонен относительно прямой L 1, повернутой от L на достаточно малый угол.
Характеристики
Предположим, что L совпадает с осью x . Затем крайняя левая и самая правая вершины монотонного многоугольника разбивают его границу на две монотонные многоугольные цепи , так что, когда вершины любой цепи пересекаются в их естественном порядке, их X-координаты монотонно увеличиваются или уменьшаются. Фактически, это свойство можно использовать для определения монотонного многоугольника, и оно дает многоугольнику его имя.
Выпуклый многоугольник монотонна относительно любой прямой и многоугольник , который является монотонным относительно каждой прямой выпукла.
Известно, что алгоритм линейного времени сообщает обо всех направлениях, в которых данный простой многоугольник является монотонным. Он был обобщен, чтобы сообщить обо всех способах разложения простого многоугольника на две монотонные цепочки (возможно, монотонные в разных направлениях).
На запросы точки в многоугольнике относительно монотонного многоугольника можно ответить за логарифмическое время после предварительной обработки линейного времени (чтобы найти крайнюю левую и крайнюю правую вершины).
Монотонный многоугольник легко триангулировать за линейное время.
Для данного набора точек на плоскости битонный тур представляет собой монотонный многоугольник, соединяющий точки. Минимальный битонический обход периметра для данного набора точек относительно фиксированного направления может быть найден за полиномиальное время с использованием динамического программирования . Легко показать, что такой минимальный битонный тур представляет собой простой многоугольник: пара пересекающихся ребер может быть заменена более короткой непересекающейся парой при сохранении битонности нового тура.
Простой многоугольник можно легко разрезать на монотонные многоугольники за время O ( n log n ). Однако, поскольку треугольник является монотонным многоугольником, триангуляция многоугольника фактически разрезает многоугольник на монотонные, и это может быть выполнено для простых многоугольников за время O ( n ).
Разрезание простого многоугольника на минимальное количество однородно монотонных многоугольников (т. Е. Монотонных относительно одной и той же прямой) может быть выполнено за полиномиальное время.
В контексте планирования движения два непересекающихся монотонных многоугольника могут быть разделены одним перемещением (т. Е. Существует перенос одного многоугольника, так что два становятся разделенными прямой линией в разные полуплоскости), и это разделение может быть найдено за линейное время. .
Обобщения
Подметаемые полигоны
Многоугольник называется заметным , если прямая линия может непрерывно перемещаться по всему многоугольнику таким образом, что в любой момент ее пересечение с многоугольной областью представляет собой выпуклое множество. Монотонный многоугольник можно протянуть линией, которая не меняет своей ориентации во время протягивания. Многоугольник является строго протаскиваемым, если никакая часть его площади не протирается более одного раза. Оба типа развертки распознаются в квадратичном времени.
3D
Не существует единого прямого обобщения монотонности многоугольника на более высокие измерения.
В одном подходе консервированной монотонности черты является линия л . Трехмерный многогранник называется слабо монотонным в направлении L, если все сечения, ортогональные L, являются простыми многоугольниками. Если сечения выпуклые, то многогранник называется слабо монотонным в выпуклом смысле . Оба типа можно распознать за полиномиальное время.
В другом подходе сохраняющейся одномерной чертой является ортогональное направление. Это дает начало понятию многогранной местности в трех измерениях: многогранной поверхности со свойством, что каждая вертикальная (т. Е. Параллельная оси Z) линия пересекает поверхность не более чем одной точкой или сегментом.
Смотрите также
- Ортогональная выпуклость для многоугольников, монотонных одновременно по двум взаимно ортогональным направлениям; также обобщение для любого количества фиксированных направлений.
- Звездообразные многоугольники , аналог монотонных многоугольников в полярных координатах