Полигональное разбиение
Набор базовых фигур, которые собираются в многоугольник

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

Минимизация количества компонентов

Задача минимизации числа составляющих прямоугольников является полиномиальной: известно несколько алгоритмов с полиномиальным временем. См. [1] : 10–13  и [2] : 3–5  для обзоров.

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

Минимизация общей длины ребра

В некоторых приложениях важнее минимизировать общую длину разрезов (например, чтобы минимизировать стоимость выполнения разбиения или минимизировать количество пыли). Эта задача называется прямоугольным разбиением с минимальной длиной ребра . Впервые она была изучена Лингасом, Пинтером, Ривестом и Шамиром в 1982 году. [4] [5] Сложность выполнения этой задачи в решающей степени зависит от того, разрешено ли иметь отверстия в необработанном многоугольнике.

Если исходный полигон не имеет отверстий , то оптимальное разбиение может быть найдено за время , где n — число вершин полигона. В особом случае «полигона гистограммы» сложность улучшается до . [4] Алгоритм использует динамическое программирование и опирается на следующий факт: если полигон не имеет отверстий, то он имеет разбиение минимальной длины, в котором каждый максимальный отрезок линии содержит вершину границы. Причина в том, что в любом разбиении минимальной длины каждый максимальный отрезок линии может быть «протолкнут» до тех пор, пока он не попадет в одну из вершин границы, не изменяя общую длину. Следовательно, в оптимальном разбиении есть только кандидаты на отрезок линии, и их можно эффективно проверить с помощью динамического программирования. [5] : 166–167  О ( н 4 ) {\displaystyle O(n^{4})} О ( н 3 ) {\displaystyle O(n^{3})} О ( н 2 ) {\displaystyle O(n^{2})}

Если необработанный полигон может иметь отверстия , даже если это вырожденные отверстия (т.е. отдельные точки), задача является NP-трудной. Это можно доказать сведением из Planar SAT . [4] [6] Для случая, когда все отверстия являются отдельными точками, было разработано несколько приближений с постоянным множителем:

  • Приближение (3+sqrt(3)) по времени ; [6] О ( н 2 ) {\displaystyle O(n^{2})}
  • (3+sqrt(3)) приближение по времени ; [7] О ( н бревно ⁡ н ) {\displaystyle O(n\log {n})}
  • 4-е приближение по времени (в более общем смысле, в d -измерениях это приближение по времени ), [8] О ( н бревно ⁡ н ) {\displaystyle O(n\log {n})} 2 г {\displaystyle 2d} О ( г н бревно ⁡ н ) {\displaystyle O(dn\log {n})}
  • 3 приближение по времени ; О ( н 4 ) {\displaystyle O(n^{4})}
  • Приближение по времени 1,75 (в более общем смысле, в d -измерениях это приближение по времени ); [9] последнее приближение использует ограниченный вариант задачи, называемый гильотинным разбиением , в котором разрезы должны быть гильотинными разрезами (разрезами от края к краю). О ( н 5 ) {\displaystyle O(n^{5})} 2 г − 4 + 4 / г {\displaystyle 2d-4+4/d} О ( г н 2 г + 1 ) {\displaystyle O(dn^{2d+1})}
  • Несколько схем аппроксимации с полиномиальным временем, использующих сложные гильотинные разрезы. [10] [11] [5]

Минимизация количества пробелов

В этой настройке большой многоугольник уже содержит некоторые попарно непересекающиеся прямоугольники. Цель состоит в том, чтобы найти разбиение многоугольника на прямоугольники таким образом, чтобы каждый исходный прямоугольник содержался в одной из частей, и при этом количество «пустых мест» (частей, не содержащих исходный прямоугольник) было бы как можно меньше. Известны следующие результаты: [12]

  • Если большой многоугольник является прямоугольником, то в любой максимальной конфигурации из n прямоугольников все отверстия являются прямоугольниками, и их число не превышает , и это очень мало. н − ⌈ 2 н − 1 ⌉ {\displaystyle n-\lceil 2{\sqrt {n}}-1\rceil }
  • Если большой многоугольник является прямоугольным многоугольником с T- рефлексными вершинами, то в любой максимальной конфигурации из n прямоугольников отверстия можно разбить максимум на прямоугольники, и это плотно. Т + н − ⌈ 2 н − 1 ⌉ {\displaystyle T+n-\lceil 2{\sqrt {n}}-1\rceil }

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

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

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

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

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

Четырехугольник или четырехугольник — это разбиение на четырехугольники .

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

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

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

Обобщением предыдущих задач является разбиение на многоугольники, которые имеют ровно m сторон или максимум m сторон. Здесь цель состоит в минимизации общей длины ребра. Эту задачу можно решить за время, полиномиальное по n и m . [17] [18]

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

При разбиении общего многоугольника на выпуклые многоугольники изучалось несколько целей.

Минимизация количества компонентов

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

Минимизация количества пробелов

Исходный многоугольник уже содержит некоторые попарно непересекающиеся выпуклые фигуры, и цель состоит в том, чтобы разбить его на выпуклые многоугольники таким образом, чтобы каждая исходная фигура содержалась в одной из частей, и при этом количество «пустых мест» (частей, не содержащих исходную фигуру) было как можно меньше. Если большой многоугольник выпуклый, то в любой максимальной компоновке из n выпуклых фигур все отверстия являются выпуклыми, и их количество не превышает , и это плотно. [12] 2 n − 5 {\displaystyle 2n-5}

Уравнивание площади и периметра

Задача о разбиении на справедливые многоугольники [20] заключается в разбиении (выпуклого) многоугольника на (выпуклые) части с равным периметром и равной площадью (это частный случай справедливого разрезания торта ). Любой выпуклый многоугольник можно легко разрезать на любое количество n выпуклых частей с площадью ровно 1/ n . Однако обеспечение того, чтобы части имели как равную площадь, так и равный периметр, является более сложной задачей. Существуют алгоритмы для решения этой задачи, когда количество частей является степенью 2. [21]

Обобщением этой задачи является замена мер площади и периметра мерой на теле и на границе многоугольника соответственно. Эта задача была изучена для 2 и 3 произведений. [22]

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

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

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

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

Ссылки

  1. ^ abcde Mark Keil, J. (2000). «Разложение многоугольника». Справочник по вычислительной геометрии . С. 491–518. doi :10.1016/B978-044482537-7/50012-7. ISBN 9780444825377.
  2. ^ ab Эппштейн, Дэвид (2010). «Решения задач вычислительной геометрии на основе теории графов». Концепции теории графов в информатике . Конспект лекций по информатике. Том 5911. С. 1–16. CiteSeerX 10.1.1.249.5965 . doi :10.1007/978-3-642-11409-0_1. ISBN  978-3-642-11408-3. S2CID  16353114.
  3. ^ Realz Slaw. "Tiling an orthogonal polygon with squares". CS stack exchange . Получено 19 октября 2015 г.
  4. ^ abc Анджей Лингас и Рон Y Пинтер и Рон L Ривест и Ади Шамир (1982). "Минимальная длина ребра разбиения прямолинейных многоугольников" (PDF) . Proc. 20th Allerton Conf. Commun. Control Comput : 53–63.
  5. ^ abc Du, Ding-Zhu; Ko, Ker-I.; Hu, Xiaodong (2012). Разработка и анализ алгоритмов аппроксимации. Springer Optimization and Its Applications. Нью-Йорк: Springer-Verlag. С. 165–209, глава 5 «guillotine cut». ISBN 978-1-4614-1700-2.
  6. ^ ab Gonzalez, Teofilo; Zheng, Si-Qing (1985-06-01). "Bounds for partitioning rectilinear polygons". Труды первого ежегодного симпозиума по вычислительной геометрии - SCG '85 . Балтимор, Мэриленд, США: Association for Computing Machinery. стр. 281–287. doi :10.1145/323233.323269. ISBN 978-0-89791-163-4. S2CID  12588297.
  7. ^ Levcopoulos, C (1986-08-01). "Быстрые эвристики для прямоугольных разбиений полигонов минимальной длины". Труды второго ежегодного симпозиума по вычислительной геометрии - SCG '86 . Yorktown Heights, Нью-Йорк, США: Association for Computing Machinery. стр. 100–108. doi : 10.1145/10515.10526 . ISBN 978-0-89791-194-8. S2CID  16106423.
  8. ^ Гонсалес, Теофило Ф.; Раззази, Мохаммадреза; Чжэн, Си-Цин (1993-12-01). «Эффективный алгоритм аппроксимации «разделяй и властвуй» для разбиения на d-боксы». Международный журнал вычислительной геометрии и приложений . 03 (4): 417–428. doi :10.1142/S0218195993000269. ISSN  0218-1959.
  9. ^ Гонсалес, Теофило; Чжэн, Си-Цин (1989-06-01). «Улучшенные границы для прямоугольных и гильотинных разбиений». Журнал символических вычислений . 7 (6): 591–610. doi : 10.1016/S0747-7171(89)80042-2 . ISSN  0747-7171.
  10. ^ Арора, С. (октябрь 1996 г.). «Схемы полиномиального времени аппроксимации для евклидовых задач коммивояжера и других геометрических задач». Труды 37-й конференции по основам компьютерных наук . стр. 2–11. doi :10.1109/SFCS.1996.548458. ISBN 0-8186-7594-2. S2CID  1499391.
  11. ^ Митчелл, Джозеф СБ (1999-01-01). «Подразделения гильотины приближают многоугольные подразделения: простая схема аппроксимации за полиномиальное время для геометрических задач коммивояжера, k-MST и связанных с ними задач». Журнал SIAM по вычислениям . 28 (4): 1298–1309. doi :10.1137/S0097539796309764. ISSN  0097-5397.
  12. ^ аб Акопян, Арсений; Сегал-Халеви, Эрель (01 января 2018 г.). «Подсчет пробелов в многоугольных композициях». SIAM Journal по дискретной математике . 32 (3): 2242–2257. arXiv : 1604.00960 . дои : 10.1137/16M110407X. ISSN  0895-4801. S2CID  123397485.
  13. ^ ab Асано, Такао; Асано, Тетсуо; Имаи, Хироши (1986). «Разбиение многоугольной области на трапеции». Журнал ACM . 33 (2): 290. doi :10.1145/5383.5387. hdl : 2433/98478 . S2CID  15296037.
  14. ^ Шазелл, Бернар (2007). «Триангуляция простого многоугольника за линейное время». Дискретная и вычислительная геометрия . 6 (3): 485–524. doi : 10.1007/bf02574703 .
  15. ^ H. Everett; W. Lenhart; M. Overmars; T. Shermer; J. Urrutia. (1992). "Строго выпуклые четырехсторонние разложения многоугольников". Proc. 4th Canad. Conf. Comput. Geom . pp. 77–83.
  16. ^ Рамасвами, Сунита; Рамос, Педро; Туссен, Годфрид (1998). «Преобразование триангуляций в квадрангуляции». Computational Geometry . 9 (4): 257. doi : 10.1016/s0925-7721(97)00019-9 .
  17. ^ Лингас, Анджей; Левкопулос, Христос; Сак, Йорг (1987). «Алгоритмы для разбиения полигонов минимальной длины». BIT . 27 (4): 474. doi :10.1007/bf01937272. S2CID  30936524.
  18. ^ Левкопулос, Христос; Лингас, Анджей; Сак, Йорг-Р. (1989). "Эвристики для оптимальных двоичных деревьев поиска и задач триангуляции минимального веса". Теоретическая информатика . 66 (2): 181. doi : 10.1016/0304-3975(89)90134-5 .
  19. ^ Hertel, Stefan; Mehlhorn, Kurt (1983). "Быстрая триангуляция простых многоугольников". В Karpinski, Marek (ред.). Основы теории вычислений. Lecture Notes in Computer Science. Том 158. Берлин, Гейдельберг: Springer. стр. 207–218. doi :10.1007/3-540-12689-9_105. ISBN 978-3-540-38682-7.
  20. ^ Нандакумар, Р.; Рао, Н. Рамана (август 2012 г.). "«Справедливые» разбиения многоугольников — введение». Труды — Математические науки . 122 (3): 459–467. arXiv : 0812.2241 . doi : 10.1007/s12044-012-0076-5. ISSN  0253-4142. S2CID  189909962.
  21. ^ Армаселу, Богдан; Даеску, Овидиу (2015-11-23). ​​«Алгоритмы справедливого разбиения выпуклых многоугольников». Теоретическая информатика . 607 : 351–362. doi : 10.1016/j.tcs.2015.08.003 . ISSN  0304-3975.
  22. ^ Беспамятных, Сергей (2003). "О разделении торта". В Акияма, Джин; Кано, Микио (ред.). Дискретная и вычислительная геометрия: Японская конференция, JCDCG 2002, Токио, Япония, 6-9 декабря 2002 г., пересмотренные статьи . Конспект лекций по информатике. Том 2866. Берлин, Гейдельберг: Springer. стр. 60–71. doi :10.1007/978-3-540-44400-8_7. ISBN 978-3-540-44400-8.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Polygon_partition&oldid=1235979022"