Обчислювальна геометрія

Обчислювальна геометрія (англ. computational geometry) — галузь комп'ютерних наук присвячена вивченню алгоритмів, які описуються в термінах геометрії. Деякі чисто геометричні проблеми виникають при вивченні обчислювальних геометричних алгоритмів, і вони також вважаються частиною обчислювальної геометрії. Хоча сучасна обчислювальна геометрія була розвинута здебільшого в новітній час, вона є однією з найдавніших областей обчислень, історія яких сягає античності.

Основним стимулом розвитку обчислювальної геометрії як дисципліни був прогрес у комп'ютерній графіці та системах автоматизованого проектування та автоматизованих систем технологічної підготовки виробництва, проте багато задач обчислювальної геометрії є класичними за своєю природою, і можуть з'являтись при математичній візуалізації.

Іншим важливим застосуванням обчислювальної геометрії є робототехніка (планування руху та задачі розпізнавання образів), геоінформаційні системи (геометричний пошук, планування маршруту), дизайн мікросхем, програмування верстатів з числовим програмним керуванням, комп'ютерний зір (об'ємна відбудова).

Основними розділами обчислювальної геометрії є:

• Комбінаторна обчислювальна геометрія, чи також названа алгоритмічна геометрія, яка розглядає геометричні об'єкти як дискретні сутності. Основоположною книгою по цій темі є книга Препарати та Шеймоса, в якій вперше в 1975 був використаний термін «обчислювальна геометрія».^[1]
• Чисельна обчислювальна геометрія, також названа машинна геометрія чи геометричне моделювання, яка має справу в основному з представленням об'єктів реального світу в формі придатній для подальшої комп'ютерної обробки. Цей розділ можна розглядати як подальший розвиток нарисної геометрії та часто розглядається як розділ комп'ютерної графіки. Термін «обчислювальна геометрія» в такому сенсі вживався з 1971.^[2]

Комбінаторна обчислювальна геометрія

Основною метою досліджень в комбінаторній обчислювальній геометрії є розробка ефективних алгоритмів та структур даних для розв'язання задач, які задані в термінах базових геометричних об'єктів: точок, відрізків, многокутників, багатогранників, та інших.

Деякі з цих задач виглядають такими простими, що вони взагалі не розглядались як задачі до моменту винайдення комп'ютерів. Розглянемо, наприклад, задачу пошуку найближчої пари точок:

• Для множини з n точок на площині, знайти пару точок, відстань між якими найменша

Можна обчислити відстані між кожною парою точок, (їх є n(n-1)/2), потім вибрати пару з найменшою відстанню. Такий повний перебір має складність O(n²) тобто час його виконання пропорційний квадрату кількості точок. Класичним результатом в обчислювальній геометрії був алгоритм зі складністю O(n log n). Також відкриті рандомізовані алгоритми, що працюють за O(n) кроків, і детерміновані алгоритми що працюють за O(n log log n).^{[джерело?]}

Обчислювальна геометрія головним чином зосереджується на обчислювальній складності, так як алгоритми призначені для роботи над дуже великими наборами даних, з десятків чи сотень мільйонів точок. Для великих наборів даних різниця між O(n²) та O(n log n) може бути такою ж, як різниця між днями та секундами.

Класи задач

Основні задачі обчислювальної геометрії можна класифікувати різними способами, і з різними критеріями. Розрізняють такі класи:

Статичні задачі

В задачах цієї категорії на вхід подаються певні дані, і за ними алгоритм має обчислити відповідні результати. Прикладами фундаментальних задач такого роду є:

• Опукла оболонка: Маючи набір точок, знайти найменший опуклий многокутник що містить всі точки.
• Перетин відрізків: знайти всі перетини в наборі відрізків.
• Тріангуляція Делоне
• Діаграма Вороного: Маючи набір точок, розділити простір на сектори, кожна точка з яких ближча до своєї з набору, ніж до інших.
• Лінійне програмування
• Задача найближчої пари точок або найвіддаленішої (діаметра): Маючи набір точок знайти дві відстань між якими найменша або найбільша.
• Евклідів найкоротший шлях^[en]: З'єднати дві точки Евклідового простору (з полігональними перешкодами) найкоротшим чином.
• Тріангуляція пларного графа або многокутника: заданий планарний граф або многокутник, розбити його внутрішність на трикутники
• Генерація меша

Обчислювальна складність для цього типу задач оцінюється відносно часу та об'єму використаної пам'яті, які необхідні для розв'язання задачі.

Задачі геометричного пошуку (запиту)

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

Приклади задач геометричного пошуку:

• Регіональний пошук^[en]: Обробити набір точок, з метою ефективного пошуку набору точок що міститься в запитаному регіоні.
• Локалізація точки: Маючи розбиття простору на регіони, створити структуру даних що дозволить ефективно визначити в якому регіоні знаходиться дана точка.
• Пошук найближчого сусіда: Обробити набір точок щоб мати змогу ефективно знайти які точки найближче до запитаної.
• Трасування променів: Маючи набір об'єктів в просторі, створити структуру даних, яка дозволить ефективно визначати які об'єкти перетинає запитаний промінь.

Якщо простір пошуку фіксований, обчислювальна складність задач зазвичай визначається

• часом та місцем що потрібні для попередньої обробки (побудови ефективної структури даних)
• часом (можливо рідко місцем) потрібними для отримання відповіді на кожен запит.

У випадках коли простір пошуку може змінюватись дивіться розділ «Динамічні задачі».

Динамічні задачі

Динамічні задачі — це тип задач вхідні дані до яких поступово змінюються (наприклад, додаються чи видаляються об'єкти). Алгоритми розв'язання таких задач містять в собі підтримку динамічних структур даних. Будь-яку задачу обчислювальної геометрії можна розв'язувати динамічно, якщо вважати, що дані додаються поступово, але це потребує додаткових обчислювальних ресурсів. Регіональний пошук, чи побудову опуклої оболонки можна проводити над множиною точок, які частково змінюються.

Обчислювальна складність для цього класу задач задається такими параметрами:

• ресурсами необхідними для побудови структури даних для пошуку
• ресурсами необхідними для модифікації побудованої структури
• ресурсами потрібними для відповіді на запити

Деякі задачі можуть розглядатись як такі, що належать кільком категоріям залежно від контексту.

Наприклад,

• Задача динамічної підтримки опуклої оболонки полягає в тому, що масив точок, для яких будується опукла оболонка змінюється з часом — додаються та видаляються точки.

Варіації

У багатьох програмах ця задача розглядається як задача першого класу. Тим не менш, в багатьох випадках потрібно визначити чи курсор миші лежить всередині даного многокутника. Курсор постійно переміщується, а многокутник не змінюється. Аналогічно можна перевіряти чи певний літальний апарат який зображений на екрані радара не перетнув кордон країни. Такі задачі можна вважати задачами геометричного запиту. А в CAD-системах сам многокутник може змінюватись, тому задача може вважатись динамічною.

Див. також

• CAD/CAM
• Дискретна геометрія
• Аналітична геометрія

Примітки

1. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. — М. : Мир, 1989. — 478 с. — ISBN 5-03-001041-6.
2. A.R. Forrest, «Computational geometry», Proc. Royal Society London, 321, series 4, 187—195 (1971)

Посилання

• Навчально-методичний посібник з курсу «Обчислювальна геометрія та комп'ютерна графіка» [Архівовано 10 грудня 2008 у Wayback Machine.] від факультету Кібернетики КНУ імені Тараса Шевченка.
• Computational Geometry [Архівовано 9 травня 2011 у Wayback Machine.]
• Computational Geometry Pages
• Geometry In Action [Архівовано 12 квітня 2011 у Wayback Machine.]
• «Strategic Directions in Computational Geometry—Working Group Report» (1996) [Архівовано 24 лютого 2011 у Wayback Machine.]
• Journal of Computational Geometry [Архівовано 9 квітня 2011 у Wayback Machine.]

Література

• Препарата Ф., Шеймос М. Вычислительная геометрия: Введение Computational Geometry An introduction Мир М. 1989 478
• Ласло М. Вычислительная геометрия и компьютерная графика на C++ БИНОМ М. 1997 304
• Скворцов А.В. Триангуляция Делоне и её применение Издательство Томского университета Томск 2002 128
• Глава 33. Вычислительная геометрия Алгоритмы: построение и анализ Introduction to Algorithms Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. 2-e издание 5-8459-0857-4 1047 — 1084 2005 М. «Вильямс»
• Computational Geometry: Algorithms and Applications Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. 368 2000 Springer
• Computional Geometry David M. Mount. 122 2002 University of Maryland
• Geometric Data Structures for Computer Graphics Elmar Langetepe, Gabriel Zachmann. 1568812353 362 2006 A K Peters
• Computational Geometry with the Rotating Calipers Hormoz Pirzadeh. 118 1999 McGill University
• Handbook of Discrete and Computational Geometry Jacob E. Goodman, Joseph O'Rourke. 956 1997 CRC Press LLC
• Computational Geometry: Methods and Applications Jianer Chen. 228 1996 Texas A&M University
• Computational Geometry in C Joseph O'Rourke. 362 1998 Cambridge University Press
• Computational Geometry A.R. Forrest. series 4 321 1971 Proc. Royal Society London