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

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

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

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

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

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

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

Содержание

  • 1 Элементы
  • 2 Простой прямолинейный многоугольник
  • 3 Квадраты и прямоугольники в прямолинейном многоугольнике
  • 4 Особые случаи
  • 5 Обобщения
  • 6 Алгоритмические проблемы, связанные с прямолинейными многоугольниками
  • 7 Прямоугольное разложение
  • 8 Ссылки

Элементы

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

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

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

Выступ - это ребро, две конечные точки которого являются выпуклыми углами. Антикорпус - это ребро, две конечные точки которого являются вогнутыми углами.

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

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

  1. Количество выпуклых углов на четыре больше, чем количество вогнутых углов. Чтобы понять, почему, представьте, что вы пересекаете границу многоугольника по часовой стрелке (правая рука находится внутри многоугольника, а левая - снаружи). В выпуклом углу поворачиваешься на 90 ° вправо; в любом вогнутом углу вы поворачиваете на 90 ° влево. Наконец, вы должны сделать полный поворот на 360 ° и вернуться в исходную точку; следовательно, количество поворотов вправо должно быть на 4 больше, чем количество поворотов влево.
    • Следствие: каждый прямолинейный многоугольник имеет не менее 4 выпуклых углов.
  2. Количество выступов (сторон, соединяющих два выпуклых угла) на четыре больше, чем количество анти-выступов (сторон, соединяющих два вогнутых угла). почему, пусть 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.
    • Следствие: каждый прямолинейный многоугольник имеет как минимум 4 выступа.

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

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

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

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

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

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

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

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

продолжитель и разделитель типы продолжения

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

Прямоугольная декомпозиция

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

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

Ссылки

  • Franco P. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Спрингер. 1-е издание: ISBN 0-387-96131-3 ; 2-е издание, исправленное и расширенное, 1988: ISBN 3-540-96131-3., глава 8: «Геометрия прямоугольников»
  1. ^ Бар-Иегуда, Р..; Бен-Ханох, Э. (1996). «Алгоритм линейного времени для покрытия простых многоугольников подобными прямоугольниками». Международный журнал вычислительной геометрии и приложений. 06 : 79. doi : 10.1142 / S021819599600006X.
  2. ^«Подсчет пар битов». Обмен стеками. 17 ноября 2013 г.
  3. ^Альбертсон, М.О.; о'Киф, К. Дж. (1981). «Покрытие областей квадратами». Журнал SIAM по алгебраическим и дискретным методам. 2 (3): 240. doi :10.1137/0602026.
Последняя правка сделана 2021-06-03 10:31:32
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте