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

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

– комбінаторна обчислювальна геометрія, чи також названа алгоритмічна геометрія, яка розглядає геометричні об'єкти як дискретні сутності;

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

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

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

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

– Опукла оболонка: Маючи набір точок, знайти найменший опуклий многокутник що містить всі точки.

– Перетин відрізків: знайти всі перетини в наборі відрізків.

– Тріангуляція Делона

– Діаграма Вороного: Маючи набір точок, розділити простір на сектори, кожна точка з яких ближча до своєї з набору, ніж до інших.

– Задача найближчої пари точок: Маючи набір точок знайти дві відстань між якими найменша.

– Евклідів найкоротший шлях: З'єднати дві точки Евклідового простору (з полігональними перешкодами) найкоротшим чином.

– Тріангуляція многокутника: Маючи многокутник, розбити його внутрішність на трикутники

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

– Регіональний пошук. Обробити набір точок, з метою ефективного пошуку набору точок що міститься в запитаному регіоні.

– Локалізація точки. Маючи розбиття простору на регіони, створити структуру даних що дозволить ефективно визначити в якому регіоні знаходиться дана точка.

– Пошук найближчого сусіда: Обробити набір точок щоб мати змогу ефективно знайти які точки найближче до запитаної.

– Трасування променів: Для заданого набору об'єктів в просторі створюється структура даних, яка дозволяє ефективно визначати об'єкти, які пересікають запитаний промінь.

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

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

– ресурсами необхідними для побудови й структури даних для пошуку,

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

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

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

Інші методи

CAD/CAM

Дискретна геометрія

Аналітична геометрія

Онтологія даної прикладної області має вигляд.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Онтологія – обчислювальна геометрія	\|	Комбінаторна обчислювальна геометрія

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.