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

Фигура, ограниченная непересекающимися отрезками прямых

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

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

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

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

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

Определения

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

Простой многоугольник — это замкнутая кривая на евклидовой плоскости, состоящая из отрезков прямых линий , которые сходятся встык, образуя многоугольную цепь . ^[1] Два отрезка линий встречаются в каждой конечной точке, и нет других точек пересечения между отрезками линий. Никакое собственное подмножество отрезков линий не имеет тех же свойств. ^[2] Квалификатор simple иногда опускается, при этом слово polygon подразумевает простой многоугольник. ^[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). «О полной кривизне узлов». Annals of Mathematics . 2-я серия. 52 : 248–257. doi :10.2307/1969467.
2. Preparata, Franco P. ; Shamos, Michael Ian (1985). Computational Geometry: An Introduction. Тексты и монографии по информатике. Springer-Verlag. стр. 18. doi :10.1007/978-1-4612-1098-6. ISBN 978-1-4612-1098-6.
3. Эверетт, Хейзел; Корнейл, Дерек (1995). «Отрицательные результаты по характеристике графов видимости». Computational Geometry: Theory & Applications . 5 (2): 51–63. doi :10.1016/0925-7721(95)00021-Z. MR  1353288.
4. Аронов, Борис ; Зайдель, Раймунд ; Сувен, Диана (1993). «О совместимых триангуляциях простых многоугольников». Computational Geometry: Theory & Applications . 3 (1): 27–35. doi : 10.1016/0925-7721(93)90028-5 . MR  1222755.
5. Малкевич, Джозеф (2016). «Являются ли точные определения хорошей идеей?». AMS Feature Column . Американское математическое общество.
6. McCallum, Duncan; Avis, David (1979). «Линейный алгоритм нахождения выпуклой оболочки простого многоугольника». Information Processing Letters . 9 (5): 201–206. doi :10.1016/0020-0190(79)90069-3. MR  0552534.
7. де Берг, М.; ван Кревельд, М .; Овермарс, Марк ; Шварцкопф, О. (2008). Вычислительная геометрия: алгоритмы и приложения (3-е изд.). Springer. стр. 58. doi :10.1007/978-3-540-77974-2.
8. Meisters, GH (1975). «У многоугольников есть уши». The American Mathematical Monthly . 82 (6): 648–651. doi :10.2307/2319703. JSTOR  2319703. MR  0367792.
9. Хейлз, Томас С. (2007). «Доказательство Джордана теоремы о кривой Жордана» (PDF) . От понимания к доказательству: юбилейный сборник в честь Анджея Трибулеца. Исследования по логике, грамматике и риторике . 10 (23). Университет Белостока.
10. Томассен, Карстен (1992). «Теорема Жордана-Шенфлиса и классификация поверхностей». The American Mathematical Monthly . 99 (2): 116–130. doi :10.1080/00029890.1992.11995820. JSTOR  2324180. MR  1144352.
11. Маргалит, Авраам; Нотт, Гэри Д. (1989). «Алгоритм вычисления объединения, пересечения или разности двух многоугольников». Компьютеры и графика . 13 (2): 167–183. doi :10.1016/0097-8493(89)90059-9.
12. Niven, Ivan ; Zuckerman, HS (1967). «Точки решетки и многоугольная площадь». The American Mathematical Monthly . 74 (10): 1195–1200. doi :10.1080/00029890.1967.12000095. JSTOR  2315660. MR  0225216.
13. Aggarwal, Alok; Suri, Subhash (1990). «Вычисление самой длинной диагонали простого многоугольника». Information Processing Letters . 35 (1): 13–18. doi :10.1016/0020-0190(90)90167-V. MR  1069001.
14. Ричмонд, Беттина ; Ричмонд, Томас (2023). Дискретный переход к высшей математике. Чистые и прикладные бакалаврские тексты. Т. 63 (2-е изд.). Американское математическое общество. стр. 421. ISBN 9781470472047.
15. Snoeyink, Jack (1999). «Перекрестные отношения и углы определяют многоугольник». Дискретная и вычислительная геометрия . 22 (4): 619–631. doi : 10.1007/PL00009481 . MR  1721028.
16. Туссен, Годфрид (1991). «Антропоморфные многоугольники». The American Mathematical Monthly . 98 (1): 31–35. doi :10.2307/2324033. JSTOR  2324033. MR  1083611.
17. Фиск, С. (1978). «Краткое доказательство теоремы Хватала о стороже». Журнал комбинаторной теории, Серия B. 24 ( 3): 374. doi : 10.1016/0095-8956(78)90059-X .
18. Preparata, Franco P. ; Supowit, Kenneth J. (1981). «Проверка простого многоугольника на монотонность». Information Processing Letters . 12 (4): 161–164. doi :10.1016/0020-0190(81)90091-0.
19. Ширра, Стефан (2008). «Насколько надежны практические стратегии «точка в многоугольнике»?» (PDF) . В Гальперин, Дэн; Мельхорн, Курт (ред.). Алгоритмы – ESA 2008, 16-й ежегодный европейский симпозиум, Карлсруэ, Германия, 15–17 сентября 2008 г. Труды . Заметки лекций по информатике. Том 5193. Springer. стр. 744–755. doi :10.1007/978-3-540-87744-8_62.
20. Snoeyink, Jack (2017). «Point Location» (PDF) . В Toth, Csaba D.; O'Rourke, Joseph; Goodman, Jacob E. (ред.). Handbook of Discrete and Computational Geometry (3-е изд.). Chapman and Hall/CRC. стр. 1005–1023.
21. Брейден, Барт (1986). «Формула площади геодезиста» (PDF) . The College Mathematics Journal . 17 (4): 326–337. doi :10.2307/2686282. JSTOR  2686282. Архивировано из оригинала (PDF) 2012-11-07.
22. Грюнбаум, Бранко ; Шепард, GC (февраль 1993). «Теорема Пика». The American Mathematical Monthly . 100 (2): 150–161. doi :10.2307/2323771. JSTOR  2323771. MR  1212401.
23. Шазелл, Бернар (1991). «Триангуляция простого многоугольника за линейное время». Дискретная и вычислительная геометрия . 6 (5): 485–524. doi : 10.1007/BF02574703 . MR  1115104.
24. Уррутия, Хорхе (2000). «Проблемы художественной галереи и освещения». В Sack, Jörg-Rüdiger ; Уррутия, Хорхе (ред.). Справочник по вычислительной геометрии . Амстердам: Северная Голландия. стр. 973–1027. doi :10.1016/B978-044482537-7/50023-1. ISBN 0-444-82537-1. МР  1746693.
25. Айххольцер, Освин; Мульцер, Вольфганг; Пильц, Александр (2015). «Расстояние переворота между триангуляциями простого многоугольника является NP-полным». Дискретная и вычислительная геометрия . 54 (2): 368–389. arXiv : 1209.0579 . doi : 10.1007/s00454-015-9709-7. MR  3372115.
26. Ahn, Hee-Kap; Barba, Luis; Bose, Prosenjit ; De Carufel, Jean-Lou; Korman, Matias; Oh, Eunjin (2016). «Линейный алгоритм для геодезического центра простого многоугольника». Discrete & Computational Geometry . 56 (4): 836–859. arXiv : 1501.00561 . doi : 10.1007/s00454-016-9796-0. MR  3561791.
27. Guibas, Leonidas ; Hershberger, John ; Leven, Daniel; Sharir, Micha ; Tarjan, Robert E. (1987). «Линейные алгоритмы для задач видимости и поиска кратчайшего пути внутри триангулированных простых многоугольников». Algorithmica . 2 (2): 209–233. doi :10.1007/BF01840360. MR  0895445.
28. Эль Джинди, Хоссам; Авис, Дэвид (1981). «Линейный алгоритм вычисления многоугольника видимости из точки». Журнал алгоритмов . 2 (2): 186–197. doi :10.1016/0196-6774(81)90019-5.
29. Чанг, Дж. С.; Яп, Ч.-К. (1986). «Полиномиальное решение задачи очистки картофеля». Дискретная и вычислительная геометрия . 1 (2): 155–182. doi : 10.1007/BF02187692 . MR  0834056.
30. Кабельо, Серхио; Цибулка, Йозеф; Кинчл, Ян; Саумелл, Мария; Вальтр, Павел (2017). «Очистка картофеля почти оптимально за почти линейное время». SIAM Journal on Computing . 46 (5): 1574–1602. arXiv : 1406.1368 . doi : 10.1137/16M1079695. MR  3708542.
31. Чин, Фрэнсис YL ; Снойинк, Джек; Ван, Цао Ань (1999). «Нахождение срединной оси простого многоугольника за линейное время». Дискретная и вычислительная геометрия . 21 (3): 405–420. doi : 10.1007/PL00009429 . MR  1672988.
32. Ченг, Сиу-Винг; Менсель, Лиам; Виньерон, Антуан (2016). «Быстрый алгоритм для вычисления прямых скелетонов». ACM Transactions on Algorithms . 12 (3): 44:1–44:21. arXiv : 1405.4691 . doi : 10.1145/2898961.
33. Палфрейдер, Питер; Хелд, Мартин (февраль 2015 г.). «Вычисление угловых офсетных кривых на основе прямых скелетов». Computer-Aided Design and Applications . 12 (4): 414–424. doi : 10.1080/16864360.2014.997637 .
34. Окс, Эдуард; Шарир, Миха (2006). «Суммы Минковского монотонных и общих простых многоугольников». Дискретная и вычислительная геометрия . 35 (2): 223–240. doi : 10.1007/s00454-005-1206-y . MR  2195052.
35. Трефетен, Ллойд Н .; Дрисколл, Тобин А. (1998). «Отображение Шварца–Кристоффеля в компьютерную эпоху». Труды Международного конгресса математиков, т. III (Берлин, 1998) . Documenta Mathematica. стр. 533–542. MR  1648186.
36. Quintas, LV; Supnick, Fred (1965). «О некоторых свойствах кратчайших гамильтоновых цепей». The American Mathematical Monthly . 72 (9): 977–980. doi :10.2307/2313333. JSTOR  2313333. MR  0188872.
37. Demaine, Erik D .; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph SB (2022). «Простые полигонализации с оптимальной площадью: задача CG 2019». ACM Journal of Experimental Algorithmics . 27 : A2.4:1–12. doi :10.1145/3504000. hdl : 1721.1/146480 . MR  4390039.
38. Добкин, Дэвид ; Гибас, Леонидас ; Хершбергер, Джон ; Сноейинк, Джек (1993). «Эффективный алгоритм для поиска представления CSG простого многоугольника». Algorithmica . 10 (1): 1–23. doi :10.1007/BF01908629. MR  1230699.
39. Гош, Субир Кумар; Госвами, Партха П. (2013). «Нерешенные проблемы в графах видимости точек, сегментов и полигонов». ACM Computing Surveys . 46 (2): 22:1–22:29. arXiv : 1012.5187 . doi : 10.1145/2543581.2543589.

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

• Вайсштейн, Эрик В. "Простой многоугольник". MathWorld .