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

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

Обчислювальна геометрія (англ. computational geometry) - галузь комп'ютерних наук присвячена вивченню алгоритмів що описуюються в термінах геометрії.

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

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

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


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

Комбінаторна обчислювальна геометрія[ред.ред. код]

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

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

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

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

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

Класи задач[ред.ред. код]

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

Статичні задачі[ред.ред. код]

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

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

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

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

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

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

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

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

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

Динамічні задачі[ред.ред. код]

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

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

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

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

Наприклад,

Варіації[ред.ред. код]

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


Дивіться також[ред.ред. код]

Зноски[ред.ред. код]

  1. Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3. 
  2. A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187-195 (1971)

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