Прямолинейный многоугольник – это многоугольник , все стороны которого сходятся под прямым углом . Таким образом, внутренний угол в каждой вершине равен либо 90°, либо 270°. Прямолинейные многоугольники являются частным случаем изотетичных многоугольников .
Во многих случаях предпочтительнее другое определение: прямолинейный многоугольник — это многоугольник, стороны которого параллельны осям декартовых координат . Это различие становится решающим, когда речь идет о наборах многоугольников: последнее определение будет подразумевать, что стороны всех многоугольников в наборе выровнены по одним и тем же осям координат. В рамках второго определения естественно говорить о горизонтальных и вертикальных ребрах прямолинейного многоугольника.
Прямолинейные многоугольники также известны как ортогональные многоугольники . Другими используемыми терминами являются изо-ориентированные , выровненные по оси и ориентированные по оси полигоны . Эти прилагательные менее сбивают с толку, когда многоугольники этого типа являются прямоугольниками , и предпочтительным является термин « прямоугольник, выровненный по оси» , хотя также используются ортогональный прямоугольник и прямолинейный прямоугольник .
Важность класса прямолинейных многоугольников обусловлена следующим.
Прямолинейный многоугольник имеет ребра двух типов: горизонтальные и вертикальные .
Прямолинейный многоугольник имеет углы двух типов: углы, у которых меньший угол (90°) является внутренним по отношению к многоугольнику, называются выпуклыми , а углы, у которых больший угол (270°) является внутренним, называются вогнутыми . [1]
Ручка — это ребро , две конечные точки которого являются выпуклыми углами. Антиручка — это ребро, две конечные точки которого являются вогнутыми углами . [1]
Прямолинейный многоугольник, который также является простым , также называется бездырочным, потому что в нем нет дыр – только одна непрерывная граница. Он имеет несколько интересных свойств:
Прямолинейный многоугольник можно покрыть конечным числом квадратов или прямоугольников с краями, параллельными краям многоугольника (см. Покрытие многоугольника ). Можно выделить несколько типов квадратов/прямоугольников, содержащихся в определенном прямолинейном многоугольнике P : [1]
Максимальный квадрат в многоугольнике P — это квадрат в P , который не содержится ни в одном другом квадрате в P . Аналогично, максимальный прямоугольник — это прямоугольник, не содержащийся ни в одном другом прямоугольнике из P.
Квадрат s является максимальным в P , если каждая пара смежных ребер s пересекает границу P . Доказательство обеих сторон основано на противоречии:
Первое направление справедливо и для прямоугольников, т.е.: если прямоугольник s максимальный, то каждая пара соседних ребер s пересекает границу P . Второе направление не обязательно верно: прямоугольник может пересекать границу P даже по 3-м соседним сторонам и при этом не быть максимальным, так как его можно растянуть по 4-й стороне.
Следствие: каждый максимальный квадрат/прямоугольник в P имеет по крайней мере две точки на двух противоположных краях, которые пересекают границу P .
Угловой квадрат — это максимальный квадрат s в многоугольнике P такой, что хотя бы один угол s перекрывает выпуклый угол P . Для каждого выпуклого угла существует ровно один максимальный (угловой) квадрат, покрывающий его, но один максимальный квадрат может покрывать более одного угла. Для каждого угла может существовать множество различных максимальных прямоугольников, покрывающих его.
Квадрат -разделитель в многоугольнике P — это квадрат s в P такой, что P − s несвязен.
Квадрат- продолжитель — это квадрат s в многоугольнике P , у которого пересечение границы s и границы P непрерывно. Максимальный продолжатель всегда является угловым квадратом. Более того, максимальный продолжатель всегда содержит ручку. Следовательно, число продолжателей всегда конечно и ограничено количеством ручек.
Существует несколько различных типов продолжателей в зависимости от количества содержащихся в них ручек и их внутренней структуры (см. рисунок). Балконом продолжателя называется его точки, не покрытые никаким другим максимальным квадратом (см. рисунок).
Ни один квадрат не может быть одновременно продолжателем и разделителем. В обычных многоугольниках могут быть квадраты, которые не являются ни продолжателями, ни разделителями, но в простых многоугольниках этого быть не может: [1]
Существует интересная аналогия между максимальными квадратами простого многоугольника и узлами дерева: продолжатель аналогичен листовому узлу, а разделитель аналогичен внутреннему узлу.
Простейший прямолинейный многоугольник — это прямоугольник, выровненный по оси — прямоугольник, две стороны которого параллельны оси x, а две стороны — параллельно оси y. См. также: Минимальный ограничивающий прямоугольник .
Голигон — это прямолинейный многоугольник , длины сторон которого последовательно представляют собой последовательные целые числа.
Прямолинейный многоугольник, не являющийся прямоугольником, никогда не является выпуклым , но может быть ортогонально выпуклым. См. Ортогонально выпуклый прямолинейный многоугольник .
Монотонный прямолинейный многоугольник — это монотонный многоугольник , который также является прямолинейным.
Т -квадрат — это фрактал, созданный из последовательности прямолинейных многоугольников с интересными свойствами.
Большинство из них можно сформулировать и для обычных многоугольников, но ожидание более эффективных алгоритмов требует отдельного рассмотрения.
Особый интерес к прямолинейным многоугольникам представляют проблемы разложения данного прямолинейного многоугольника на простые единицы - обычно прямоугольники или квадраты. Существует несколько типов проблем разложения: