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

Прямолинейный многоугольник — это многоугольник , все стороны которого пересекаются под прямым углом . Таким образом, внутренний угол в каждой вершине равен либо 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 смежным сторонам и все равно не быть максимальным, так как его можно растянуть по четвертой стороне.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

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