Разделение многоугольника - Polygon partition

А раздел из многоугольник представляет собой набор примитивных единиц (например, квадратов), которые не перекрываются и объединение которых равно многоугольнику. А задача разбиения многоугольника - это проблема поиска минимального в некотором смысле раздела, например раздела с наименьшим числом элементов или с элементами с наименьшей общей длиной стороны.

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

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

Приложения

Разложение по полигонам применяется в нескольких областях:^[1]

• Распознавание образов методы извлекают информацию из объекта, чтобы описать, идентифицировать или классифицировать его. Установленная стратегия распознавания общего многоугольного объекта состоит в том, чтобы разложить его на более простые компоненты, затем идентифицировать компоненты и их взаимосвязи и использовать эту информацию для определения формы объекта.
• В СБИС Обработка данных произведений искусства, макеты представлены в виде многоугольников, и один из подходов к подготовке к электронно-лучевой литографии состоит в том, чтобы разложить эти области многоугольника на фундаментальные фигуры. Разложение по полигонам также используется в процессе разделения области маршрутизации на каналы.
• В вычислительная геометрия, алгоритмы решения проблем с общими многоугольниками часто бывают более сложными, чем алгоритмы для ограниченных типов многоугольников, таких как выпуклые или звездообразные. В проблема включения точки это один из примеров. Стратегия решения некоторых из этих типов проблем на общих многоугольниках состоит в том, чтобы разбить многоугольник на простые составные части, решить проблему для каждого компонента с помощью специального алгоритма, а затем объединить частичные решения.
• Другие приложения включают Сжатие данных, системы баз данных, обработка изображений и компьютерная графика.

Разбиение многоугольника на треугольники

Основные статьи: Триангуляция многоугольника и Триангуляция минимального веса

Наиболее изученная проблема разбиения многоугольника - это разбиение на наименьшее количество треугольников, также называемое триангуляция. Для многоугольника без отверстий с ${\displaystyle n}$ вершины, триангуляция может быть рассчитана во времени ${\displaystyle \Theta (n)}$. Для многоугольника с отверстиями существует нижняя граница ${\displaystyle \Omega (n\log n)}$.

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

Разбиение многоугольника на псевдотреугольники

Основная статья: Псевдотреугольник § Псевдотриангуляции

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

Разбиение прямолинейного многоугольника на прямоугольники

Особое подсемейство проблем разбиения многоугольника возникает, когда большой многоугольник является прямолинейный многоугольник (также называется ортогональным многоугольником). В этом случае наиболее важной формой компонента, которую следует учитывать, является прямоугольник.^[1]

Прямоугольные перегородки имеют множество применений. В СБИС дизайн, необходимо разложить маски на более простые формы, доступные в генераторах литографических узоров, и аналогичные проблемы декомпозиции масок также возникают в ДНК дизайн микрочипов. Прямоугольные перегородки позволяют упростить свертка операции в обработка изображений и может использоваться для сжатия растровые изображения. Близкие задачи разложения матриц были применены к радиационная терапия планирование, и прямоугольные перегородки также использовались для проектирования роботов самосборка последовательности.^[2]

Известно несколько алгоритмов с полиномиальным временем решения этой проблемы; видеть ^[1]:10–13 и ^[2]:3–5 для обзора.

Задача разбиения прямолинейного многоугольника на наименьшее количество квадраты (в отличие от произвольных прямоугольников) NP-жесткий.^[3]

Разбиение многоугольника на трапеции

В системах обработки графических объектов СБИС часто требуется разделить многоугольную область на минимальное количество трапеции, с двумя горизонтальными сторонами. Треугольник с горизонтальной стороной считается трапецией с двумя горизонтальными сторонами, одна из которых вырождена. Для многоугольника без отверстий с ${\displaystyle n}$ стороны, наименьшую такую ​​перегородку можно найти за время ${\displaystyle O(n^{3})}$.^[4]

Если количество трапеций не должно быть минимальным, трапеция может быть найдена вовремя ${\displaystyle O(n)}$, как побочный продукт триангуляция многоугольника алгоритм.^[5]

Если многоугольник действительно содержит дыры, проблема NP-полная, но можно найти 3-аппроксимацию во времени. ${\displaystyle O(n\log n)}$.^[4]

Разбиение многоугольника на выпуклые четырехугольники

А четырехугольник или четырехугольник это раздел на четырехугольники.

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

Существуют алгоритмы линейного времени для четырехугольников многоугольников без дырок с точками Штейнера, но они не гарантируют нахождение наименьшего разбиения.^[6][7]

Разбить многоугольник на м-угольники

Обобщением предыдущих проблем является проблема разбиения на многоугольники, которые имеют ровно м стороны, или самое большее м стороны. Здесь цель - минимизировать общую длину ребра. Эта задача может быть решена за полиномиальное время от п и м.^[8][9]

Более общие формы компонентов

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

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

• Полигональное покрытие - связанная проблема, в которой части могут перекрываться.
• Проблема с упаковкой - связанная проблема, при которой части должны помещаться внутри всего большого объекта, но не должны покрывать его полностью.
• Евклидовы мозаики выпуклыми правильными многоугольниками - проблема разбиения всей плоскости на простые многоугольники, такие как прямоугольники.
• Квадрат квадрата - проблема разбиения целого квадрата с использованием только других целых квадратов.
• Разделение пространства
• Головоломка плитки - головоломка упаковки нескольких заданных частей в заданный более крупный многоугольник.

Рекомендации

1. Марк Кейл, Дж. (2000). «Разложение многоугольника». Справочник по вычислительной геометрии. С. 491–518. Дои:10.1016 / B978-044482537-7 / 50012-7. ISBN  9780444825377.
2. Эпштейн, Дэвид (2010). "Теоретико-графические решения задач вычислительной геометрии". Теоретико-графические концепции в компьютерных науках. Конспект лекций по информатике. 5911. С. 1–16. CiteSeerX  10.1.1.249.5965. Дои:10.1007/978-3-642-11409-0_1. ISBN  978-3-642-11408-3.
3. Realz Slaw. «Замощение прямоугольного многоугольника квадратами». Обмен стеками CS. Получено 19 октября 2015.
4. Асано, Такао; Асано, Тецуо; Имаи, Хироши (1986). «Разбиение многоугольной области на трапеции». Журнал ACM. 33 (2): 290. Дои:10.1145/5383.5387. HDL:2433/98478.
5. Шазель, Бернар (2007). «Триангуляция простого многоугольника за линейное время». Дискретная и вычислительная геометрия. 6 (3): 485–524. Дои:10.1007 / bf02574703.
6. Х. Эверетт; В. Ленхарт; М. Овермарс; Т. Шермер; J. Urrutia. (1992). «Строго выпуклые четырехугольники многоугольников». Proc. 4-я канадская. Конф. Comput. Geom. С. 77–83.
7. Рамасвами, Сунита; Рамос, Педро; Туссен, Годфрид (1998). «Преобразование триангуляции в четырехугольник». Вычислительная геометрия. 9 (4): 257. Дои:10.1016 / s0925-7721 (97) 00019-9.
8. Лингас, Анджей; Левкопулос, Христос; Мешок, Йорг (1987). «Алгоритмы разбиения полигонов минимальной длины». КУСОЧЕК. 27 (4): 474. Дои:10.1007 / bf01937272.
9. Левкопулос, Христос; Лингас, Анджей; Мешок, Йорг-Р. (1989). «Эвристика для оптимальных деревьев двоичного поиска и задач триангуляции минимального веса». Теоретическая информатика. 66 (2): 181. Дои:10.1016/0304-3975(89)90134-5.
10. Лингас, Анджей (1982). «Сила непрямолинейных отверстий». Автоматы, языки и программирование. Конспект лекций по информатике. 140. С. 369–383. Дои:10.1007 / bfb0012784. ISBN  978-3-540-11576-2.