Прямолинейный многоугольник

Прямолинейный многоугольник – это многоугольник , все стороны которого сходятся под прямым углом . Таким образом, внутренний угол в каждой вершине равен либо 90°, либо 270°. Прямолинейные многоугольники являются частным случаем изотетичных многоугольников .

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

Прямолинейные многоугольники также известны как ортогональные многоугольники . Другими используемыми терминами являются изо-ориентированные , выровненные по оси и ориентированные по оси полигоны . Эти прилагательные менее сбивают с толку, когда многоугольники этого типа являются прямоугольниками , и предпочтительным является термин «прямоугольник, выровненный по оси» , хотя ортогональный прямоугольник и прямолинейный прямоугольник также используются .

Важность класса прямолинейных многоугольников обусловлена следующим.

Они удобны для представления форм в интегральных схем макетах благодаря простоте проектирования и изготовления. Многие изготовленные объекты имеют ортогональные многоугольники.
Проблемы вычислительной геометрии, сформулированные в терминах многоугольников, часто позволяют использовать более эффективные алгоритмы, если они ограничены ортогональными многоугольниками. Примером может служить теорема художественной галереи для ортогональных многоугольников, которая приводит к более эффективному защитному покрытию, чем это возможно для произвольных многоугольников.

Края

Прямолинейный многоугольник имеет ребра двух типов: горизонтальные и вертикальные .

Лемма : количество горизонтальных ребер равно количеству вертикальных ребер (поскольку за каждым горизонтальным ребром следует вертикальное ребро и наоборот).
- Следствие: ортогональные многоугольники имеют четное количество ребер.

Прямолинейный многоугольник имеет углы двух типов: углы, у которых меньший угол (90°) является внутренним по отношению к многоугольнику, называются выпуклыми , а углы, у которых больший угол (270°) является внутренним, называются вогнутыми . ^[1]

Ручка . — это ребро, две конечные точки которого являются выпуклыми углами Антиручка . — это ребро, две конечные точки которого являются вогнутыми углами ^[1]

Простой прямолинейный многоугольник

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

Число выпуклых углов на четыре больше, чем количество вогнутых. Чтобы понять почему, представьте, что вы пересекаете границу многоугольника по часовой стрелке (правая рука внутри многоугольника, а левая рука снаружи). В выпуклом углу вы поворачиваетесь на 90° вправо; в любом вогнутом углу вы поворачиваете на 90 ° влево. Наконец, вы должны сделать поворот на 360° и вернуться в исходную точку; следовательно, количество правых поворотов должно быть на 4 больше, чем количество левых.
- Следствие: каждый прямолинейный многоугольник имеет как минимум 4 выпуклых угла.
Количество выступов (сторон, соединяющих два выпуклых угла) на четыре больше, чем количество противовыступов (сторон, соединяющих два вогнутых угла). Чтобы понять, почему, пусть X — количество выпуклых углов, а Y — количество вогнутых углов. По предыдущему факту X=Y+4 . Пусть XX - количество выпуклых углов, за которыми следует выпуклый угол, XY - количество выпуклых углов, за которыми следует вогнутый угол, YX и YY определяются аналогично. Тогда очевидно X=XX+XY=XX+YX и Y=XY+YY=YX+YY . Следовательно XX=X-XY=X-(Y-YY)=YY+(XY)=YY+4 . ^[2]
- Следствие: каждый прямолинейный многоугольник имеет как минимум 4 выступа.

Квадраты и прямоугольники в прямолинейном многоугольнике

Прямолинейный многоугольник можно покрыть конечным числом квадратов или прямоугольников с краями, параллельными краям многоугольника (см. Покрытие многоугольника ). Можно выделить несколько типов квадратов/прямоугольников, содержащихся в определенном прямолинейном многоугольнике P : ^[1]

Максимальный квадрат в многоугольнике P — это квадрат в P , который не содержится ни в одном другом квадрате в P . Аналогично, максимальный прямоугольник — это прямоугольник, не содержащийся ни в одном другом прямоугольнике P. из

Квадрат s является максимальным в P , если каждая пара смежных ребер s пересекает границу P . Доказательство обеих сторон основано на противоречии:

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

Первое направление справедливо и для прямоугольников, т.е.: если прямоугольник s максимальный, то каждая пара соседних ребер s пересекает границу P . Второе направление не обязательно верно: прямоугольник может пересекать границу P даже по 3-м соседним сторонам и при этом не быть максимальным, так как его можно растянуть по 4-й стороне.

Следствие: каждый максимальный квадрат/прямоугольник в P имеет по крайней мере две точки на двух противоположных краях, которые пересекают границу P .

Угловой квадрат — это максимальный квадрат s в многоугольнике P такой, что хотя бы один угол s перекрывает выпуклый угол P . Для каждого выпуклого угла существует ровно один максимальный (угловой) квадрат, покрывающий его, но один максимальный квадрат может покрывать более одного угла. Для каждого угла может существовать множество различных максимальных прямоугольников, покрывающих его.

Квадрат -разделитель в многоугольнике P — это квадрат s в P такой, что P − s несвязен.

Лемма : в простом прямолинейном многоугольнике максимальный квадрат, не содержащий ручки, является разделителем. ^[3] Квадрат с ручкой может быть разделителем, а может и не быть. Число различных квадратов-разделителей может быть бесконечным и даже несчетным. Например, в прямоугольнике каждый максимальный квадрат, не касающийся одной из более коротких сторон, является разделителем.

Квадрат -продолжитель — это квадрат s в многоугольнике P , у которого пересечение границы s и границы P непрерывно. Максимальный продолжатель всегда является угловым квадратом. Более того, максимальный продолжатель всегда содержит ручку. Следовательно, число продолжателей всегда конечно и ограничено количеством ручек.

Существует несколько различных типов продолжателей в зависимости от количества содержащихся в них ручек и их внутренней структуры (см. рисунок). Балконом . продолжателя называется его точки, не покрытые никаким другим максимальным квадратом (см. рисунок)

Ни один квадрат не может быть одновременно продолжателем и разделителем. В общих многоугольниках могут быть квадраты, не являющиеся ни продолжателями, ни разделителями, но в простых многоугольниках такого быть не может: ^[1]

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

Существует интересная аналогия между максимальными квадратами простого многоугольника и узлами дерева: продолжатель аналогичен листовому узлу, а разделитель аналогичен внутреннему узлу.

Особые случаи

Простейший прямолинейный многоугольник — это прямоугольник , выровненный по оси — прямоугольник, две стороны которого параллельны оси x, а две стороны — параллельно оси y. См. также: Минимальный ограничивающий прямоугольник .

Голигон . — это прямолинейный многоугольник, длины сторон которого последовательно представляют собой последовательные целые числа

Прямолинейный многоугольник, не являющийся прямоугольником, никогда не является выпуклым , но может быть ортогонально выпуклым. См. Ортогонально выпуклый прямолинейный многоугольник .

Монотонный прямолинейный многоугольник — это монотонный многоугольник , который также является прямолинейным.

Т -квадрат — это фрактал, созданный из последовательности прямолинейных многоугольников с интересными свойствами.

Алгоритмические задачи с прямолинейными многоугольниками

Большинство из них можно сформулировать и для обычных многоугольников, но ожидание более эффективных алгоритмов требует отдельного рассмотрения.

Поиск ортогонального диапазона
Ортогональная выпуклая конструкция корпуса
Булевы операции над многоугольниками для ортогональных многоугольников (например, пересечение и объединение )
Планирование движения / планирование пути / маршрутизация среди прямолинейных препятствий
Проблемы с видимостью ( Проблемы с освещением )
Максимальный пустой прямоугольник

Прямоугольное разложение

Особый интерес для прямолинейных многоугольников представляют проблемы разложения данного прямолинейного многоугольника на простые единицы - обычно прямоугольники или квадраты. Существует несколько типов проблем разложения:

При решении задач цель состоит в том, чтобы найти наименьший набор единиц (квадратов или прямоугольников), объединение которых равно многоугольнику. Единицы могут перекрываться. См. Покрытие полигоном .
В задачах упаковки цель состоит в том, чтобы найти наибольший набор непересекающихся единиц, объединение которых содержится в многоугольнике. Объединение может быть меньше многоугольника.
В задачах разделения цель состоит в том, чтобы найти наименьший набор непересекающихся единиц, объединение которых в точности равно многоугольнику. См. Раздел «Многоугольник» .

См. также

Ортогональные многогранники — естественное обобщение ортогональных многоугольников на 3D.

Ссылки

Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер . ISBN 0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г. , глава 8: «Геометрия прямоугольников».

^ Перейти обратно: ^а ^б ^с ^д Бар-Иегуда, Р.; Бен-Ханох, Э. (1996). «Алгоритм линейного времени для покрытия простых многоугольников подобными прямоугольниками». Международный журнал вычислительной геометрии и приложений . 06 :79–102. дои : 10.1142/S021819599600006X .
^ «Подсчет пар битов» . Обмен стеками . 17 ноября 2013 г.
^ Альбертсон, Миссури; о'Киф, CJ (1981). «Покрытие областей квадратами». SIAM Journal по алгебраическим и дискретным методам . 2 (3): 240. дои : 10.1137/0602026 .

[bybc96-1] Перейти обратно: ^а ^б ^с ^д Бар-Иегуда, Р.; Бен-Ханох, Э. (1996). «Алгоритм линейного времени для покрытия простых многоугольников подобными прямоугольниками». Международный журнал вычислительной геометрии и приложений . 06 :79–102. дои : 10.1142/S021819599600006X .

[2] «Подсчет пар битов» . Обмен стеками . 17 ноября 2013 г.

[ao81-3] Альбертсон, Миссури; о'Киф, CJ (1981). «Покрытие областей квадратами». SIAM Journal по алгебраическим и дискретным методам . 2 (3): 240. дои : 10.1137/0602026 .

[1]

[2]

[3]