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

Простий многокутник — це многокутник без перетинів та дірок. Тобто, це пласка фігура, що складається з відрізків, які не перетинаються або «сторін», які з'єднані попарно й утворюють замкнений шлях. Якщо сторони перетинаються, многокутник не є простим. Часто слово «простий» опускають з наведеного визначення.

Наведене визначення забезпечує такі властивості фігури:

Многокутник оточує область (звану внутрішністю), яка завжди має вимірну площу.
Відрізки, що утворюють многокутник (звані сторонами, рідше — ребрами), перетинаються тільки в їхніх кінцевих точках, які називають вершинами (або, менш формально, «кутами»).
В кожній вершині сходяться рівно дві сторони.
Число сторін завжди дорівнює числу вершин.

Зазвичай вимагається, щоб дві сторони, що сходяться у вершині, не утворювали розгорнутого (180°) кута. В іншому випадку сторони, що лежать на одній прямій, вважаються частинами однієї сторони.

Математики зазвичай використовують термін «многокутник» тільки для фігур, утворених відрізками, не включаючи внутрішню область. Однак деякі використовують термін «многокутник» для позначення плоскої фігури, обмеженої замкнутим шляхом, що складається зі скінченної послідовності відрізків (тобто замкнутою ламаною). Залежно від використовуваного визначення межа може бути чи не бути частиною многокутника^[1].

Прості многокутники називають також жордановими многокутниками, оскільки може бути використана теорема Жордана для доведення того, що такі многокутники розбивають площину на дві області, внутрішню і зовнішню. Многокутник на площині є простим тоді і тільки тоді, коли він топологічно еквівалентний колу. Його внутрішність топологічно еквівалентна кругу.

Слабко простий многокутник

Якщо набір відрізків, що не перетинаються, утворює межу області на площині, топологічно еквівалентну колу, то ця межа називається слабко простим многокутником^[2]. На малюнку ABCDEFGHJKLM є слабко простим многокутником згідно з визначенням. Синім кольором показано область, для якої слабко простий многокутник є межею.

Цей тип слабко простих многокутників може виникнути в комп'ютерній графіці і в системах CAD в якості комп'ютерного подання багатокутних областей з порожнинами — для кожної порожнини створюється «розріз» для з'єднання з зовнішньою межею. Згідно з малюнком ABCM є зовнішньою межею плоскої області з порожниною FGHJ. Розріз ED з'єднує порожнину з зовнішнім контуром і проходиться двічі в поданні слабко простого многокутника.

Альтернативне і більш загальне визначення слабко простих многокутників — границя послідовності простих многокутників одного й того ж комбінаторного типу, які сходяться за відстанню Фреше^[3]. Це формалізує ідею, що елементам многокутника дозволено дотик, але не перетин. Проте цей тип слабко простих многокутників не обов'язково утворює межу області, оскільки «внутрішність» може бути порожньою. Наприклад, на малюнку ланцюжок ABCBA є слабко простим многокутником — його можна розглядати як границю «витискання» многокутника ABCFGHA.

Обчислювальні задачі

В обчислювальній геометрії деякі важливі обчислювальні задачі використовують вхід у вигляді простого многокутника. У кожній з цих задач відмінність між внутрішністю і зовнішністю є ключовим моментом^[4].

Задача про належність точки многокутнику вимагає визначити, чи знаходиться точка q у внутрішній області многокутника P^[5].
Прості формули відомі для обчислення площі многокутника, тобто внутрішньої області^[6].
Розбиття многокутника^[en] — це множина елементарних одиниць (наприклад, квадратів), які не перетинаються і об'єднання яких дає многокутник. Завдання розбиття многокутника полягає в знаходженні розбиття, мінімального в деякому сенсі. Наприклад, розбиття з мінімальним числом одиниць або з мінімальною сумарною довжиною сторін^[7].
- Частковим випадком розбиття многокутника є задача про тріангуляцію многокутника — розбиття простого многокутника на трикутники. Хоча опуклі многокутники легко розбити на трикутники, тріангуляція простих многокутників загального вигляду є складнішим завданням, оскільки потрібно уникати додавання ребер, що перетинаються поза многокутником. Проте, Бернхард Чазелле в 1991 році показав, що будь-який простий многокутник з n вершинами можна розбити на трикутники за оптимальний час Θ(n). Той самий алгоритм може бути використаний для з'ясування, чи утворює замкнена ламана простий многокутник.
- Інший особливий випадок — проблема галереї мистецтв, яку можна переформулювати як розбиття на мінімальну кількість зіркоподібних многокутників^[7].
Булеві операції над многокутниками — різні булеві операції на множині точок, визначених внутрішніми областями многокутників.
Опукла оболонка простого многокутника може бути обчислена більш ефективно, ніж опукла оболонка для інших видів вхідних даних, таких як множина точок.
Діаграма Вороного простого многокутника
Серединна вісь/топологічний кістяк/прямолінійний кістяк простого многокутника
Паралельна крива простого многокутника
Сума Мінковського для простих многокутників

Див. також

Зірчата область

Примітки

↑ Grünbaum, 2003.
↑ Dumitrescu, Tóth, 2007, с. 177.
↑ Chang, Erickson, Xu, 2015, с. 1655–1670.
↑ comp.graphics.algorithms FAQ [Архівовано 13 лютого 2011 у Wayback Machine.] зі списком розв'язків математичних задач з 2D і 3D многокутниками.
↑ Haines, Eric (1994). Point in polygon strategies. У Heckbert, Paul S. (ред.). Graphics Gems IV. San Diego, CA, USA: Academic Press Professional, Inc. с. 24—46. ISBN 0-12-336155-9. Архів оригіналу за 9 липня 2021. Процитовано 15 грудня 2019.
↑ Bart Braden (1986). The surveyor's area formula (PDF). The College Mathematics Journal. 17 (4): 326—337. doi:10.2307/2686282. Архів оригіналу (PDF) за 7 листопада 2012.
↑ ^а ^б Lee, D. T. (1998). Chapter 19: Computational Geometry I. У Atallah, Mikhail J. (ред.). Algorithms and Theory of Computation Handbook. Chapman & Hall/CRC Applied Algorithms and Data Structures series. CRC Press. ISBN 9781420049503. See «Other decompositions», p. 19-25 [Архівовано 9 липня 2021 у Wayback Machine.].

Література

Branko Grünbaum. Convex polytopes / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2nd. — New York, London : Springer-Verlag, 2003. — ISBN 0-387-00424-6.
Adrian Dumitrescu, Csaba D. Tóth. STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings / Wolfgang Thomas, Pascal Weil. — illustrated. — Springer, 2007. — ISBN 3540709177.
Hsien-Chih Chang, Jeff Erickson, Chao Xu. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15). — 2015.

Посилання

Weisstein, Eric W. Simple polygon(англ.) на сайті Wolfram MathWorld.

[FOOTNOTEGrünbaum2003-1] Grünbaum, 2003.

[FOOTNOTEDumitrescu,_Tóth2007177-2] Dumitrescu, Tóth, 2007, с. 177.

[FOOTNOTEChang,_Erickson,_Xu20151655–1670-3] Chang, Erickson, Xu, 2015, с. 1655–1670.

[4] .graphics.algorithms FAQ [Архівовано 13 лютого 2011 у Wayback Machine.] зі списком розв'язків математичних задач з 2D і 3D многокутниками.

[5] Haines, Eric (1994). Point in polygon strategies. У Heckbert, Paul S. (ред.). Graphics Gems IV. San Diego, CA, USA: Academic Press Professional, Inc. с. 24—46. ISBN 0-12-336155-9. Архів оригіналу за 9 липня 2021. Процитовано 15 грудня 2019.

[6] Bart Braden (1986). The surveyor's area formula (PDF). The College Mathematics Journal. 17 (4): 326—337. doi:10.2307/2686282. Архів оригіналу (PDF) за 7 листопада 2012.

[dtlee-7] а ^б Lee, D. T. (1998). Chapter 19: Computational Geometry I. У Atallah, Mikhail J. (ред.). Algorithms and Theory of Computation Handbook. Chapman & Hall/CRC Applied Algorithms and Data Structures series. CRC Press. ISBN 9781420049503. See «Other decompositions», p. 19-25 [Архівовано 9 липня 2021 у Wayback Machine.].

[1]

[2]

[3]

[4]

[5]

[6]

[7]