Простой многоугольник

Форма, ограниченная непересекающимися отрезками линий

Два простых многоугольника (зеленый и синий) и самопересекающийся многоугольник (красный, справа внизу, не простой)

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

Сумма внешних углов простого многоугольника равна . Каждый простой многоугольник со сторонами можно триангулировать по его диагоналям, и по теореме художественной галереи его внутренняя часть видна из некоторых его вершин. ${\displaystyle 2\pi }$ ${\displaystyle n}$ ${\displaystyle n-3}$ ${\displaystyle \lfloor n/3\rfloor }$

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

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

Определения

Части простого многоугольника

Простой многоугольник — это замкнутая кривая на евклидовой плоскости, состоящая из отрезков прямых , соединяющихся друг с другом, образующих многоугольную цепь . ^[1] Два отрезка линии встречаются в каждой конечной точке, и между отрезками линии нет других точек пересечения. Никакое подходящее подмножество отрезков прямой не имеет таких свойств. ^[2] Квалификатор simple иногда опускается, при этом слово « полигон» подразумевает простой многоугольник. ^[3]

Отрезки линий, образующие многоугольник, называются его краями или сторонами . Конечная точка сегмента называется вершиной (множественное число: вершины) ^[2] или углом . Ребра и вершины более формальны, но могут быть неоднозначными в контекстах, которые также включают ребра и вершины графа ; Чтобы избежать этой двусмысленности, можно использовать более разговорные термины стороны и углы . ^[4] Количество ребер всегда равно количеству вершин. ^[2] Некоторые источники позволяют двум отрезкам линии образовывать прямой угол (180°), ^[5] в то время как другие запрещают это, вместо этого требуя, чтобы коллинеарные сегменты замкнутой многоугольной цепи были объединены в одну более длинную сторону. ^[6] Две вершины являются соседями , если они являются двумя конечными точками одной из сторон многоугольника. ^[7]

Простые многоугольники иногда называют жордановыми многоугольниками , потому что они являются жордановыми кривыми ; Теорему Жордана о кривой можно использовать, чтобы доказать, что такой многоугольник делит плоскость на две области. ^[8] Действительно, первоначальное доказательство этой теоремы Камиллы Жордана взяло в качестве отправной точки частный случай простых многоугольников (указанный без доказательства). ^[9] Область внутри многоугольника (его внутренняя часть ) образует ограниченное множество ^[2], топологически эквивалентное открытому диску по теореме Жордана–Шенфлиса , ^[10] с конечной, но ненулевой площадью . ^[11] Сам многоугольник топологически эквивалентен кругу , [ ^12] а область снаружи ( внешняя часть ) представляет собой неограниченное связное открытое множество с бесконечной площадью. ^[11] Хотя формальное определение простого многоугольника обычно представляет собой систему отрезков прямых, также возможно (и это часто встречается в неформальном использовании) определить простой многоугольник как замкнутое множество на плоскости, объединение этих отрезков прямой. с внутренней частью многоугольника. ^[2]

Диагональю простого многоугольника является любой отрезок линии, конечные точки которого имеют две вершины многоугольника, а в остальном он полностью находится внутри многоугольника. ^[13]

Характеристики

Внутренний угол простого многоугольника в одной из его вершин — это угол, охватываемый внутренней частью многоугольника в этой вершине. Вершина является выпуклой , если ее внутренний угол меньше (прямой угол 180°), и вогнутой, если внутренний угол больше . Если внутренний угол равен , то внешний угол при той же вершине определяется как его дополнение , угол поворота от одной направленной стороны к другой. Внешний угол положителен в выпуклой вершине или отрицателен в вогнутой вершине. Для каждого простого многоугольника сумма внешних углов равна (один полный оборот, 360°). Таким образом, сумма внутренних углов простого многоугольника со сторонами равна . ^[14] ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle \theta }$ ${\displaystyle \pi -\theta }$ ${\displaystyle 2\pi }$ ${\displaystyle n}$ ${\displaystyle (n-2)\pi }$

Треугольный многоугольник с 11 вершинами: 11 сторон и 8 диагоналей образуют 9 треугольников.

Любой простой многоугольник можно разбить на непересекающиеся треугольники с помощью подмножества его диагоналей. Когда у многоугольника есть стороны, образуются треугольники, разделенные диагоналями. Полученное разбиение называется триангуляцией многоугольника . ^[8] Форма треугольного простого многоугольника может быть однозначно определена внутренними углами многоугольника и перекрестными отношениями четырехугольников, образованных парами треугольников, имеющих общую диагональ. ^[15] ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle n-3}$

Согласно теореме о двух ушках , каждый простой многоугольник, не являющийся треугольником, имеет как минимум два уха — вершины, два соседа которых являются конечными точками диагонали. ^[8] Соответствующая теорема гласит, что каждый простой многоугольник, который не является выпуклым многоугольником, имеет рот , вершину, два соседа которой являются конечными точками отрезка линии, который в противном случае полностью находится вне многоугольника. Многоугольники, у которых ровно два уха и один рот, называются антропоморфными многоугольниками . ^[16]

Эта полигональная художественная галерея с 42 вершинами полностью видна с камер, расположенных в 4 отмеченных вершинах.

Согласно теореме художественной галереи , в простом многоугольнике с вершинами всегда можно найти подмножество из не более большинства вершин со свойством, что каждая точка многоугольника видна из одной из выбранных вершин. Это означает, что для каждой точки многоугольника существует отрезок линии, соединяющий выбранную вершину и проходящий только через внутренние точки многоугольника. Один из способов доказать это — использовать раскраску графа при триангуляции многоугольника: всегда можно раскрасить вершины в три цвета так, чтобы каждая сторона или диагональ в триангуляции имела две конечные точки разных цветов. Каждая точка многоугольника видна вершине каждого цвета, например, одной из трех вершин треугольника, содержащего эту точку в выбранной триангуляции. Один из цветов используется большинством вершин, что доказывает теорему. ^[17] ${\displaystyle n}$ ${\displaystyle \lfloor n/3\rfloor }$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \lfloor n/3\rfloor }$

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

Каждый выпуклый многоугольник является простым многоугольником. Другой важный класс простых многоугольников — это звездообразные многоугольники , многоугольники, у которых есть точка (внутренняя или на границе), из которой видна каждая точка. ^[2]

Монотонный многоугольник по отношению к прямой — это многоугольник, у которого каждая линия, перпендикулярная к, пересекает внутреннюю часть многоугольника в связном множестве. Эквивалентно, это многоугольник, граница которого может быть разделена на две монотонные многоугольные цепи, подпоследовательности ребер, вершины которых, проецируемые перпендикулярно на , имеют тот же порядок вдоль, что и в цепочке. ^[18] ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$

Вычислительные проблемы

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

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

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

• Точка при тестировании полигона включает в себя определение для простого многоугольника и точки запроса того, находится ли он внутри . Ее можно решить за линейное время ; в качестве альтернативы можно преобразовать данный многоугольник в структуру данных за линейное время, так что последующие проверки точек в многоугольнике могут выполняться за логарифмическое время. ^[20] ${\displaystyle P}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle P}$
• Известны простые формулы для вычисления площади внутренней части многоугольника. К ним относятся формула шнурков для произвольных многоугольников ^[21] и теорема Пика для многоугольников с целыми координатами вершин. ^{[12] [22]}
• Выпуклую оболочку простого многоугольника также можно найти за линейное время, быстрее, чем алгоритмы поиска выпуклых оболочек точек, не соединенных в многоугольник. ^[6]
• Построение триангуляции простого многоугольника также можно выполнить за линейное время, хотя алгоритм сложен. Модификацию того же алгоритма можно также использовать для проверки того, образует ли замкнутая ломаная цепь простой многоугольник (то есть, избегает ли она самопересечений) за линейное время. ^[23] Это также приводит к алгоритму с линейным временем для решения проблемы художественной галереи с использованием большинства точек, хотя и не обязательно с использованием оптимального количества точек для данного многоугольника. ^[24] Хотя можно преобразовать любые две триангуляции одного и того же многоугольника друг в друга с помощью переворотов , которые заменяют одну диагональ за раз, определение того, можно ли это сделать, используя только ограниченное количество переворотов, является NP-полным . ^[25] ${\displaystyle \lfloor n/3\rfloor }$
• Геодезический путь, ^[26] кратчайший путь на плоскости, который соединяет две точки внутри многоугольника, не пересекая его снаружи, может быть найден за линейное время с помощью алгоритма, использующего триангуляцию в качестве подпрограммы . ^[27] То же самое относится и к геодезическому центру — точке многоугольника, которая минимизирует максимальную длину геодезических путей ко всем остальным точкам. ^[26]
• Многоугольник видимости внутренней точки простого многоугольника, то есть точек, которые непосредственно видны из данной точки по отрезкам линий, внутренними по отношению к многоугольнику, может быть построен за линейное время. ^[28] То же самое верно для подмножества, которое видно хотя бы из одной точки данного сегмента линии. ^[27]

Другие вычислительные проблемы, изучаемые для простых многоугольников, включают построение самой длинной диагонали или самого длинного отрезка внутренней части многоугольника, ^[13] выпуклого черепа (самого большого выпуклого многоугольника внутри данного простого многоугольника), ^{[29] [30]} и различные одномерные скелеты, аппроксимирующие его форму, включая медиальную ось ^[31] и прямой скелет . ^[32] Исследователи также изучали создание других многоугольников из простых многоугольников, используя их кривые смещения , ^[33] объединения и пересечения, ^[11] и суммы Минковского , ^[34] , но эти операции не всегда создают в результате простой многоугольник. Их можно определить таким образом, чтобы всегда создавать двумерную область, но это требует тщательного определения операций пересечения и разности, чтобы избежать создания одномерных объектов или изолированных точек. ^[11]

Связанные конструкции

Согласно теореме Римана об отображении , любое односвязное открытое подмножество плоскости можно конформно отобразить на диск. Отображение Шварца – Кристоффеля предоставляет метод явного построения карты диска в любой простой многоугольник с использованием заданных углов вершин и прообразов вершин многоугольника на границе диска. Эти предвершины обычно вычисляются численно. ^[35]

Черный многоугольник — это кратчайшая петля, соединяющая все красные точки, что является решением задачи коммивояжера.

Каждый конечный набор точек на плоскости, который не лежит на одной прямой, можно соединить, чтобы сформировать вершины простого многоугольника (с учетом углов 180 °); например, один из таких многоугольников является решением задачи коммивояжера . ^[36] Соединение точек для формирования многоугольника таким способом называется полигонализацией . ^[37]

Каждый простой многоугольник может быть представлен формулой конструктивной объемной геометрии , которая строит многоугольник (как замкнутое множество, включая внутреннюю часть) из объединений и пересечений полуплоскостей , при этом каждая сторона многоугольника появляется один раз как полуплоскость в формула. Преобразование одностороннего многоугольника в это представление можно выполнить за время . ^[38] ${\displaystyle n}$ ${\displaystyle O(n\log n)}$

Граф видимости простого многоугольника соединяет его вершины рёбрами, представляющими стороны и диагонали многоугольника. ^[3] Он всегда содержит гамильтонов цикл , образованный сторонами многоугольника. Вычислительная сложность реконструкции многоугольника, который имеет заданный граф в качестве графа видимости и заданный гамильтонов цикл в качестве цикла сторон, остается открытой проблемой. ^[39]

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

• Задача правила Карпентера о непрерывном движении простого многоугольника в выпуклый многоугольник.
• Теорема Эрдеша – Надя , процесс отражения карманов невыпуклого простого многоугольника, чтобы сделать его выпуклым.
• Сеть (многогранник) — простой многоугольник, который можно сложить и склеить, чтобы образовать заданный многогранник.
• Сферический многоугольник , аналогичная концепция на поверхности сферы.
• Слабо простой многоугольник — обобщение простых многоугольников, позволяющее краям соприкасаться ограниченным количеством способов.

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

1. Милнор, Джон В. (1950). «О полной кривизне узлов». Анналы математики . 2-я серия. 52 : 248–257. дои : 10.2307/1969467.
2. Препарата, Франко П .; Шамос, Майкл Ян (1985). Вычислительная геометрия: Введение. Тексты и монографии по информатике. Спрингер-Верлаг. п. 18. дои : 10.1007/978-1-4612-1098-6. ISBN 978-1-4612-1098-6.
3. Эверетт, Хейзел; Корнейл, Дерек (1995). «Отрицательные результаты по характеристике графиков видимости». Вычислительная геометрия: теория и приложения . 5 (2): 51–63. дои : 10.1016/0925-7721(95)00021-Z. МР  1353288.
4. Аронов, Борис ; Зейдель, Раймунд ; Сувен, Дайан (1993). «О согласованных триангуляциях простых многоугольников». Вычислительная геометрия: теория и приложения . 3 (1): 27–35. дои : 10.1016/0925-7721(93)90028-5 . МР  1222755.
5. Малкевич, Джозеф (2016). «Являются ли точные определения хорошей идеей?». Столбец функций AMS . Американское математическое общество.
6. МакКаллум, Дункан; Авис, Дэвид (1979). «Линейный алгоритм поиска выпуклой оболочки простого многоугольника». Письма об обработке информации . 9 (5): 201–206. дои : 10.1016/0020-0190(79)90069-3. МР  0552534.
7. де Берг, М .; ван Кревелд, М .; Овермарс, Марк ; Шварцкопф, О. (2008). Вычислительная геометрия: алгоритмы и приложения (3-е изд.). Спрингер. п. 58. дои : 10.1007/978-3-540-77974-2.
8. Мейстерс, GH (1975). «У многоугольников есть уши». Американский математический ежемесячник . 82 (6): 648–651. дои : 10.2307/2319703. JSTOR  2319703. МР  0367792.
9. Хейлз, Томас К. (2007). «Доказательство Джордана теоремы о кривой Жордана» (PDF) . От понимания к доказательству: Фестиваль в честь Анджея Трибулца. Исследования по логике, грамматике и риторике . Белостокский университет. 10 (23).
10. Томассен, Карстен (1992). «Теорема Джордана-Шенфлиса и классификация поверхностей». Американский математический ежемесячник . 99 (2): 116–130. дои : 10.1080/00029890.1992.11995820. JSTOR  2324180. MR  1144352.
11. Маргалит, Авраам; Нотт, Гэри Д. (1989). «Алгоритм вычисления объединения, пересечения или разности двух многоугольников». Компьютеры и графика . 13 (2): 167–183. дои : 10.1016/0097-8493(89)90059-9.
12. Нивен, Иван ; Цукерман, HS (1967). «Точки решетки и многоугольная площадь». Американский математический ежемесячник . 74 (10): 1195–1200. дои : 10.1080/00029890.1967.12000095. JSTOR  2315660. МР  0225216.
13. Аггарвал, Алок; Сури, Субхаш (1990). «Вычисление наибольшей диагонали простого многоугольника». Письма об обработке информации . 35 (1): 13–18. дои : 10.1016/0020-0190(90)90167-В. МР  1069001.
14. Ричмонд, Беттина ; Ричмонд, Томас (2023). Дискретный переход к высшей математике. Чистые и прикладные тексты для студентов. Том. 63 (2-е изд.). Американское математическое общество. п. 421. ИСБН 9781470472047.
15. Снойинк, Джек (1999). «Перекрестные отношения и углы определяют многоугольник». Дискретная и вычислительная геометрия . 22 (4): 619–631. дои : 10.1007/PL00009481 . МР  1721028.
16. Туссен, Годфрид (1991). «Антропоморфные многоугольники». Американский математический ежемесячник . 98 (1): 31–35. дои : 10.2307/2324033. JSTOR  2324033. MR  1083611.
17. Фиск, С. (1978). «Краткое доказательство теоремы сторожа Хваталя». Журнал комбинаторной теории, серия B. 24 (3): 374. doi : 10.1016/0095-8956(78)90059-X .
18. Препарата, Франко П .; Суповит, Кеннет Дж. (1981). «Проверка простого многоугольника на монотонность». Письма об обработке информации . 12 (4): 161–164. дои : 10.1016/0020-0190(81)90091-0.
19. Ширра, Стефан (2008). «Насколько надежны практические стратегии «точка в полигоне»?» (PDF) . В Гальперине, Дэн; Мельхорн, Курт (ред.). Алгоритмы – ESA 2008, 16-й ежегодный европейский симпозиум, Карлсруэ, Германия, 15–17 сентября 2008 г. Материалы . Конспекты лекций по информатике. Том. 5193. Спрингер. стр. 744–755. дои : 10.1007/978-3-540-87744-8_62.
20. Снойинк, Джек (2017). «Расположение точки» (PDF) . В Тоте, Чаба Д.; О'Рурк, Джозеф; Гудман, Джейкоб Э. (ред.). Справочник по дискретной и вычислительной геометрии (3-е изд.). Чепмен и Холл/CRC. стр. 1005–1023.
21. Брейден, Барт (1986). «Формула площади геодезиста» (PDF) . Математический журнал колледжа . 17 (4): 326–337. дои : 10.2307/2686282. JSTOR  2686282. Архивировано из оригинала (PDF) 7 ноября 2012 г.
22. Грюнбаум, Бранко ; Шепард, GC (февраль 1993 г.). «Теорема Пика». Американский математический ежемесячник . 100 (2): 150–161. дои : 10.2307/2323771. JSTOR  2323771. MR  1212401.
23. Шазель, Бернар (1991). «Триангуляция простого многоугольника за линейное время». Дискретная и вычислительная геометрия . 6 (5): 485–524. дои : 10.1007/BF02574703 . МР  1115104.
24. Уррутия, Хорхе (2000). «Картинная галерея и проблемы освещения». В Саке, Йорг-Рюдигер ; Уррутия, Хорхе (ред.). Справочник по вычислительной геометрии . Амстердам: Северная Голландия. стр. 973–1027. дои : 10.1016/B978-044482537-7/50023-1. ISBN 0-444-82537-1. МР  1746693.
25. Айххольцер, Освин; Мюльцер, Вольфганг; Пильц, Александр (2015). «Расстояние переворота между триангуляциями простого многоугольника NP-полное». Дискретная и вычислительная геометрия . 54 (2): 368–389. arXiv : 1209.0579 . дои : 10.1007/s00454-015-9709-7. МР  3372115.
26. Ан, Хи-Кап; Барба, Луис; Бозе, Просенджит ; Де Каруфель, Жан-Лу; Корман, Матиас; О, Ынджин (2016). «Алгоритм линейного времени для геодезического центра простого многоугольника». Дискретная и вычислительная геометрия . 56 (4): 836–859. arXiv : 1501.00561 . дои : 10.1007/s00454-016-9796-0. МР  3561791.
27. Гибас, Леонид ; Хершбергер, Джон ; Левен, Дэниел; Шарир, Миша ; Тарьян, Роберт Э. (1987). «Алгоритмы линейного времени для решения задач видимости и кратчайшего пути внутри триангулированных простых многоугольников». Алгоритмика . 2 (2): 209–233. дои : 10.1007/BF01840360. МР  0895445.
28. Эль Джинди, Хосам; Авис, Дэвид (1981). «Линейный алгоритм расчета многоугольника видимости из точки». Журнал алгоритмов . 2 (2): 186–197. дои : 10.1016/0196-6774(81)90019-5.
29. Чанг, Дж. С.; Яп, К.-К. (1986). «Полиномиальное решение задачи чистки картофеля». Дискретная и вычислительная геометрия . 1 (2): 155–182. дои : 10.1007/BF02187692 . МР  0834056.
30. Кабельо, Серджио; Цибулка, Йозеф; Кынчл, Ян; Сомелл, Мария; Валтр, Павел (2017). «Очистка картофеля почти оптимально за почти линейное время». SIAM Journal по вычислительной технике . 46 (5): 1574–1602. arXiv : 1406.1368 . дои : 10.1137/16M1079695. МР  3708542.
31. Чин, Фрэнсис YL ; Снойинк, Джек; Ван, Цао Ань (1999). «Нахождение средней оси простого многоугольника за линейное время». Дискретная и вычислительная геометрия . 21 (3): 405–420. дои : 10.1007/PL00009429 . МР  1672988.
32. Ченг, Сиу-Винг; Менсель, Лиам; Виньерон, Антуан (2016). «Более быстрый алгоритм расчета прямых скелетов». Транзакции ACM на алгоритмах . 12 (3): 44:1–44:21. arXiv : 1405.4691 . дои : 10.1145/2898961.
33. Палфрадер, Питер; Хелд, Мартин (февраль 2015 г.). «Расчет кривых смещения под углом на основе прямых каркасов». Компьютерное проектирование и приложения . 12 (4): 414–424. дои : 10.1080/16864360.2014.997637 .
34. Окс, Эдуард; Шарир, Миша (2006). «Суммы Минковского монотонных и общих простых многоугольников». Дискретная и вычислительная геометрия . 35 (2): 223–240. дои : 10.1007/s00454-005-1206-y . МР  2195052.
35. Трефетен, Ллойд Н .; Дрисколл, Тобин А. (1998). «Картирование Шварца – Кристоффеля в компьютерную эпоху». Труды Международного конгресса математиков, Vol. III (Берлин, 1998 г.) . Документа Математика. стр. 533–542. МР  1648186.
36. Кинтас, Л.В.; Супник, Фред (1965). «О некоторых свойствах кратчайших гамильтоновых цепей». Американский математический ежемесячник . 72 (9): 977–980. дои : 10.2307/2313333. JSTOR  2313333. МР  0188872.
37. Демейн, Эрик Д .; Фекете, Шандор П.; Кельденич, Филипп; Крупке, Доминик; Митчелл, Джозеф С.Б. (2022). «Простые полигонализации, оптимальные по площади: задача компьютерной графики 2019». Журнал экспериментальной алгоритмики ACM . 27 : А2.4:1–12. дои : 10.1145/3504000. hdl : 1721.1/146480 . МР  4390039.
38. Добкин, Дэвид ; Гибас, Леонидас ; Хершбергер, Джон ; Снойинк, Джек (1993). «Эффективный алгоритм поиска CSG-представления простого многоугольника». Алгоритмика . 10 (1): 1–23. дои : 10.1007/BF01908629. МР  1230699.
39. Гош, Субир Кумар; Госвами, Партха П. (2013). «Нерешенные проблемы графов видимости точек, отрезков и многоугольников». Обзоры вычислительной техники ACM . 46 (2): 22:1–22:29. arXiv : 1012.5187 . дои : 10.1145/2543581.2543589.

Внешние ссылки

• Вайсштейн, Эрик В. «Простой многоугольник». Математический мир .