Простий багатокутник

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

Деякі прості багатокутники

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки
  1. Grünbaum, 2003.
  2. Dumitrescu, Tóth, 2007, с. 177.
  3. Chang, Erickson, Xu, 2015, с. 1655–1670.
  4. comp.graphics.algorithms FAQ зі списком розв'язків математичних задач з 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.
  6. Bart Braden (1986). The surveyor's area formula. The College Mathematics Journal 17 (4): 326–337. doi:10.2307/2686282. Архів оригіналу за 7 листопада 2012.
  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.

Література
  • 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.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.