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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Деякі прості багатокутники

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

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

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

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

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

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

Слабко простий багатокутник[ред. | ред. код]

Weakly simple polygon.svg

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

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

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

Обчислювальні задачі[ред. | ред. код]

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

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Grünbaum, 2003
  2. Dumitrescu, Tóth, 2007, с. 177
  3. Chang, Erickson, Xu, 2015, с. 1655–1670
  4. comp.graphics.algorithms FAQ зі списком розв'язків математичних задач з 2D і 3D багатокутниками.

Література[ред. | ред. код]

  • 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.

Посилання[ред. | ред. код]