Прямолинейный многоугольник - Rectilinear polygon
А прямолинейный многоугольник это многоугольник все пересечения ребер находятся в прямые углы. Таким образом, внутренний угол в каждой вершине равен 90 ° или 270 °. Прямолинейные многоугольники - частный случай изотетические многоугольники.
Во многих случаях предпочтительнее другое определение: прямолинейный многоугольник многоугольник, стороны которого параллельны осям Декартовы координаты. Различие становится решающим, когда речь идет о наборах многоугольников: последнее определение подразумевает, что стороны всех многоугольников в наборе выровнены по одним и тем же осям координат. В рамках второго определения естественно говорить о горизонтальные края и вертикальные края прямолинейного многоугольника.
Прямолинейные многоугольники также известны как ортогональные многоугольники. Другие используемые термины: изоориентированный, выровненный по оси, и многоугольники с осевой ориентацией. Эти прилагательные менее запутаны, когда многоугольники этого типа прямоугольники, а срок выровненный по оси прямоугольник предпочтительнее, хотя ортогональный прямоугольник и прямолинейный прямоугольник тоже используются.
Важность класса прямолинейных многоугольников заключается в следующем.
- Они удобны для представления форм в Интегральная схема макеты масок за счет простоты конструкции и изготовления. Многие изготовленные объекты образуют ортогональные многоугольники.
- Проблемы в вычислительная геометрия заявленные в терминах многоугольников, часто позволяют эффективные алгоритмы при ограничении ортогональными многоугольниками. Примером может служить Теорема о художественной галерее для ортогональных многоугольников, что приводит к более эффективному защитному покрытию, чем это возможно для произвольных многоугольников.
Элементы
У прямолинейного многоугольника есть ребра двух типов: горизонтальный и вертикальный.
- Лемма: Количество горизонтальных краев равно количеству вертикальных краев (поскольку за каждым горизонтальным краем следует вертикальный край и наоборот).
- Следствие: ортогональные многоугольники имеют четное число ребер.
У прямолинейного многоугольника есть углы двух типов: углы, в которых меньший угол (90 °) находится внутри многоугольника, называются выпуклый а углы, в которых больший угол (270 °) является внутренним, называются вогнутый.[1]
А ручка ребро, два конца которого - выпуклые углы. An антикнопка край, две конечные точки которого являются вогнутыми углами.[1]
Простой прямолинейный многоугольник
Прямолинейный многоугольник, который также просто также называется без дыр потому что в нем нет дыр - только одна сплошная граница. У него есть несколько интересных свойств:
- Количество выпуклых углов на четыре больше, чем количество вогнутых углов. Чтобы понять почему, представьте, что вы пересекаете границу многоугольника по часовой стрелке (правая рука находится внутри многоугольника, а левая - снаружи). В выпуклом углу поворачиваешься на 90 ° вправо; в любом вогнутом углу вы поворачиваете на 90 ° влево. Наконец, вы должны сделать полный поворот на 360 ° и вернуться в исходную точку; следовательно, количество поворотов вправо должно быть на 4 больше, чем количество поворотов влево.
- Следствие: каждый прямолинейный многоугольник имеет не менее 4 выпуклых углов.
- Количество выступов (сторон, соединяющих два выпуклых угла) на четыре больше, чем количество анти-выступов (сторон, соединяющих два вогнутых угла). Чтобы понять, почему, пусть Икс количество выпуклых углов и Y количество вогнутых углов. По предыдущему факту, Х = Y + 4. Позволять XX количество выпуклых углов, за которыми следует выпуклый угол, XY количество выпуклых углов, за которыми следует вогнутый угол, YX и YY определяется аналогично. Тогда очевидно X = XX + XY = XX + YX и Y = XY + YY = YX + YY. Следовательно XX = X-XY = X- (Y-YY) = YY + (X-Y) = YY + 4.[2]
- Следствие: у каждого прямолинейного многоугольника не менее 4 выступов.
Квадраты и прямоугольники в прямолинейном многоугольнике
Прямолинейный многоугольник может быть покрыт конечным числом квадратов или прямоугольников с ребрами, параллельными ребрам многоугольника (см. Полигональное покрытие ). Можно выделить несколько типов квадратов / прямоугольников, содержащихся в определенном прямолинейном многоугольнике. п:[1]
А максимальный квадрат в многоугольнике п квадрат в п который не содержится ни в каком другом квадрате в п. Точно так же максимальный прямоугольник - это прямоугольник, не содержащийся ни в одном другом прямоугольнике в п.
Площадь s максимально в п если каждая пара смежных ребер s пересекает границу п. Доказательство обеих сторон от противоречия:
- Если некоторая соседняя пара в s не пересекает границу п, то эта пара будет продвинута дальше к границе, поэтому s не является максимальным.
- Если s не является максимальным в п, то в п содержащий s; внутри этого большего квадрата есть пара смежных ребер s, следовательно, эта пара не пересекает границу п.
Первое направление также верно для прямоугольников, то есть: если прямоугольник s максимальна, то каждая пара смежных ребер s пересекает границу п. Второе направление не обязательно верно: прямоугольник может пересекать границу п в даже 3 смежных сторонах и все же не быть максимальным, так как может растягиваться в 4-й стороне.
Следствие: каждый максимальный квадрат / прямоугольник в п имеет по крайней мере две точки на двух противоположных краях, которые пересекают границу п.
А угловой квадрат это максимальный квадрат s в многоугольнике п так, чтобы хотя бы один угол s перекрывает выпуклый угол п. Для каждого выпуклого угла существует ровно один максимальный (угловой) квадрат, покрывающий его, но один максимальный квадрат может покрывать более одного угла. Для каждого угла может быть много разных максимальных прямоугольников, покрывающих его.
А разделительный квадрат в многоугольнике п это квадрат s в п такой, что п−s не связано.
- Лемма: в простом прямолинейном многоугольнике максимальный квадрат, не содержащий ручки, является разделителем.[3] Квадрат с ручкой может быть или не быть разделителем. Количество различных квадратов разделителей может быть бесконечным и даже несчетным. Например, в прямоугольнике каждый максимальный квадрат, не касающийся одной из более коротких сторон, является разделителем.
А квадрат продолжения это квадрат s в многоугольнике п такое, что пересечение границы s и граница п непрерывно. Максимальный продолжитель - всегда угловой квадрат. Более того, максимальный продолжитель всегда содержит ручку. Следовательно, число продолжателей всегда конечно и ограничено числом выступов.
Существует несколько различных типов продолжителей, в зависимости от количества ручек, которые они содержат, и их внутренней структуры (см. Рисунок). В балкон континуатора определяется как его точки, не покрытые никаким другим максимальным квадратом (см. рисунок).
Никакой квадрат не может быть одновременно продолжателем и разделителем. В обычных многоугольниках могут быть квадраты, которые не являются ни продолжателями, ни разделителями, но в простых многоугольниках этого не может быть:[1]
- В простом прямолинейном многоугольнике каждый максимальный квадрат является либо разделителем, либо продолжением. Это также верно для прямоугольников: каждый максимальный прямоугольник является либо разделителем, либо продолжателем.
- В простом прямолинейном многоугольнике, не являющемся квадратом, есть как минимум два продолжения.
Существует интересная аналогия между максимальными квадратами в простом многоугольнике и узлами в дереве: продолжитель аналогичен листовому узлу, а разделитель аналогичен внутреннему узлу.
Особые случаи
Простейший прямолинейный многоугольник - это выровненный по оси прямоугольник - прямоугольник с 2 сторонами, параллельными оси x и 2 сторонами, параллельными оси y. Смотрите также: Минимальный ограничивающий прямоугольник.
А голигон представляет собой прямолинейный многоугольник, длины сторон которого последовательно равны последовательным целым числам.
Прямолинейный многоугольник, который не является прямоугольником, никогда не выпуклый, но может быть ортогонально выпуклым. Видеть Ортогонально выпуклый прямолинейный многоугольник .
А монотонный прямолинейный многоугольник это монотонный многоугольник которая также прямолинейна.
А Т-образный квадрат представляет собой фрактал, образованный из последовательности прямолинейных многоугольников с интересными свойствами.
Обобщения
- Ортогональные многогранники - естественное обобщение ортогональных многоугольников на 3D.
- Прямолинейность [1]
Алгоритмические задачи с прямолинейными многоугольниками
Большинство из них можно указать и для обычных многоугольников, но ожидание более эффективных алгоритмов требует отдельного рассмотрения.
- Поиск ортогонального диапазона
- Ортогональная выпуклая оболочка строительство
- Логические операции над полигонами для ортогональных многоугольников (например, пересечение и союз )
- Планирование движения /планирование пути /маршрутизация среди прямолинейных препятствий
- Проблемы с видимостью (Проблемы с освещением )
- Максимальный пустой прямоугольник
Прямоугольное разложение
Особый интерес для прямолинейных многоугольников представляют проблемы разложения данного прямолинейного многоугольника на простые элементы - обычно прямоугольники или квадраты. Есть несколько типов задач декомпозиции:
- В покрытие задач, цель состоит в том, чтобы найти наименьший набор единиц (квадратов или прямоугольников), объединение которых равно многоугольнику. Единицы могут перекрываться. Видеть Полигональное покрытие.
- В упаковка Задача состоит в том, чтобы найти наибольший набор неперекрывающихся единиц, объединение которых содержится в многоугольнике. Объединение может быть меньше многоугольника.
- В разделение Задача состоит в том, чтобы найти наименьший набор непересекающихся единиц, объединение которых в точности равно многоугольнику.
Рекомендации
- Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer. 1-е издание: ISBN 0-387-96131-3; 2-е издание, исправленное и расширенное, 1988 г .: ISBN 3-540-96131-3., глава 8: «Геометрия прямоугольников»
- ^ а б c d Bar-Yehuda, R .; Бен-Ханох, Э. (1996). «Алгоритм линейного времени для покрытия простых многоугольников подобными прямоугольниками». Международный журнал вычислительной геометрии и приложений. 06: 79. Дои:10.1142 / S021819599600006X.
- ^ «Подсчет пар бит». Обмен стеком. 17 ноября 2013 г.
- ^ Albertson, M.O .; о'Киф, К. Дж. (1981). «Покрытие областей квадратами». Журнал SIAM по алгебраическим и дискретным методам. 2 (3): 240. Дои:10.1137/0602026.