Azərbaycanca AzərbaycancaDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisItaliana ItalianaҚазақ ҚазақLietuvos LietuvosРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人
Підтримка
www.wikidata.uk-ua.nina.az

Обчислювальна геометрія англ computational geometry галузь комп ютерних наук присвячена вивченню алгоритмів які описують

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

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

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

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

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

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

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

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

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

  • Для множини з 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]: З'єднати дві точки Евклідового простору (з полігональними перешкодами) найкоротшим чином.
  • Тріангуляція пларного графа або многокутника: заданий планарний граф або многокутник, розбити його внутрішність на трикутники
  • Генерація меша

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

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

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

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

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

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

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

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

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

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

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

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

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

Наприклад,

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

Варіації

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

Див. також

Примітки

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

Посилання

Література

  • Препарата Ф., Шеймос М. Вычислительная геометрия: Введение 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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Дата публікації:
Obchislyuvalna geometriya angl computational geometry galuz komp yuternih nauk prisvyachena vivchennyu algoritmiv yaki opisuyutsya v terminah geometriyi Deyaki chisto geometrichni problemi vinikayut pri vivchenni obchislyuvalnih geometrichnih algoritmiv i voni takozh vvazhayutsya chastinoyu obchislyuvalnoyi geometriyi Hocha suchasna obchislyuvalna geometriya bula rozvinuta zdebilshogo v novitnij chas vona ye odniyeyu z najdavnishih oblastej obchislen istoriya yakih syagaye antichnosti Osnovnim stimulom rozvitku obchislyuvalnoyi geometriyi yak disciplini buv progres u komp yuternij grafici ta sistemah avtomatizovanogo proektuvannya ta avtomatizovanih sistem tehnologichnoyi pidgotovki virobnictva prote bagato zadach obchislyuvalnoyi geometriyi ye klasichnimi za svoyeyu prirodoyu i mozhut z yavlyatis pri matematichnij vizualizaciyi Inshim vazhlivim zastosuvannyam obchislyuvalnoyi geometriyi ye robototehnika planuvannya ruhu ta zadachi rozpiznavannya obraziv geoinformacijni sistemi geometrichnij poshuk planuvannya marshrutu dizajn mikroshem programuvannya verstativ z chislovim programnim keruvannyam komp yuternij zir ob yemna vidbudova Osnovnimi rozdilami obchislyuvalnoyi geometriyi ye Kombinatorna obchislyuvalna geometriya chi takozh nazvana algoritmichna geometriya yaka rozglyadaye geometrichni ob yekti yak diskretni sutnosti Osnovopolozhnoyu knigoyu po cij temi ye kniga Preparati ta Shejmosa v yakij vpershe v 1975 buv vikoristanij termin obchislyuvalna geometriya Chiselna obchislyuvalna geometriya takozh nazvana mashinna geometriya chi geometrichne modelyuvannya yaka maye spravu v osnovnomu z predstavlennyam ob yektiv realnogo svitu v formi pridatnij dlya podalshoyi komp yuternoyi obrobki Cej rozdil mozhna rozglyadati yak podalshij rozvitok narisnoyi geometriyi ta chasto rozglyadayetsya yak rozdil komp yuternoyi grafiki Termin obchislyuvalna geometriya v takomu sensi vzhivavsya z 1971 Kombinatorna obchislyuvalna geometriyaOsnovnoyu metoyu doslidzhen v kombinatornij obchislyuvalnij geometriyi ye rozrobka efektivnih algoritmiv ta struktur danih dlya rozv yazannya zadach yaki zadani v terminah bazovih geometrichnih ob yektiv tochok vidrizkiv mnogokutnikiv bagatogrannikiv ta inshih Deyaki z cih zadach viglyadayut takimi prostimi sho voni vzagali ne rozglyadalis yak zadachi do momentu vinajdennya komp yuteriv Rozglyanemo napriklad zadachu poshuku najblizhchoyi pari tochok Dlya mnozhini z n tochok na ploshini znajti paru tochok vidstan mizh yakimi najmensha Mozhna obchisliti vidstani mizh kozhnoyu paroyu tochok yih ye n n 1 2 potim vibrati paru z najmenshoyu vidstannyu Takij povnij perebir maye skladnist O n2 tobto chas jogo vikonannya proporcijnij kvadratu kilkosti tochok Klasichnim rezultatom v obchislyuvalnij geometriyi buv algoritm zi skladnistyu O n log n Takozh vidkriti randomizovani algoritmi sho pracyuyut za O n krokiv i determinovani algoritmi sho pracyuyut za O n log log n dzherelo Obchislyuvalna geometriya golovnim chinom zoseredzhuyetsya na obchislyuvalnij skladnosti tak yak algoritmi priznacheni dlya roboti nad duzhe velikimi naborami danih z desyatkiv chi soten miljoniv tochok Dlya velikih naboriv danih riznicya mizh O n2 ta O n log n mozhe buti takoyu zh yak riznicya mizh dnyami ta sekundami Klasi zadach Osnovni zadachi obchislyuvalnoyi geometriyi mozhna klasifikuvati riznimi sposobami i z riznimi kriteriyami Rozriznyayut taki klasi Statichni zadachi V zadachah ciyeyi kategoriyi na vhid podayutsya pevni dani i za nimi algoritm maye obchisliti vidpovidni rezultati Prikladami fundamentalnih zadach takogo rodu ye Opukla obolonka Mayuchi nabir tochok znajti najmenshij opuklij mnogokutnik sho mistit vsi tochki Peretin vidrizkiv znajti vsi peretini v nabori vidrizkiv Triangulyaciya Delone Diagrama Voronogo Mayuchi nabir tochok rozdiliti prostir na sektori kozhna tochka z yakih blizhcha do svoyeyi z naboru nizh do inshih Linijne programuvannya Zadacha najblizhchoyi pari tochok abo najviddalenishoyi diametra Mayuchi nabir tochok znajti dvi vidstan mizh yakimi najmensha abo najbilsha en Z yednati dvi tochki Evklidovogo prostoru z poligonalnimi pereshkodami najkorotshim chinom Triangulyaciya plarnogo grafa abo mnogokutnika zadanij planarnij graf abo mnogokutnik rozbiti jogo vnutrishnist na trikutniki Generaciya mesha Obchislyuvalna skladnist dlya cogo tipu zadach ocinyuyetsya vidnosno chasu ta ob yemu vikoristanoyi pam yati yaki neobhidni dlya rozv yazannya zadachi Zadachi geometrichnogo poshuku zapitu V zadachah geometrichnogo poshuku vhidni dani skladayutsya z dvoh chastin prostoru poshuku ta zapitu tip danih yakih zalezhit vid konkretnoyi zadachi Zazvichaj pripuskayut sho kilkist zapitiv bude nabagato bilshe kilkosti danih Tomu dlya zmenshennya zagalnoyi kilkosti operacij prostir poshuku potrebuye poperednoyi obrobki danih Prikladi zadach geometrichnogo poshuku en Obrobiti nabir tochok z metoyu efektivnogo poshuku naboru tochok sho mistitsya v zapitanomu regioni Lokalizaciya tochki Mayuchi rozbittya prostoru na regioni stvoriti strukturu danih sho dozvolit efektivno viznachiti v yakomu regioni znahoditsya dana tochka Poshuk najblizhchogo susida Obrobiti nabir tochok shob mati zmogu efektivno znajti yaki tochki najblizhche do zapitanoyi Trasuvannya promeniv Mayuchi nabir ob yektiv v prostori stvoriti strukturu danih yaka dozvolit efektivno viznachati yaki ob yekti peretinaye zapitanij promin Yaksho prostir poshuku fiksovanij obchislyuvalna skladnist zadach zazvichaj viznachayetsya chasom ta miscem sho potribni dlya poperednoyi obrobki pobudovi efektivnoyi strukturi danih chasom mozhlivo ridko miscem potribnimi dlya otrimannya vidpovidi na kozhen zapit U vipadkah koli prostir poshuku mozhe zminyuvatis divitsya rozdil Dinamichni zadachi Dinamichni zadachi Dinamichni zadachi ce tip zadach vhidni dani do yakih postupovo zminyuyutsya napriklad dodayutsya chi vidalyayutsya ob yekti Algoritmi rozv yazannya takih zadach mistyat v sobi pidtrimku dinamichnih struktur danih Bud yaku zadachu obchislyuvalnoyi geometriyi mozhna rozv yazuvati dinamichno yaksho vvazhati sho dani dodayutsya postupovo ale ce potrebuye dodatkovih obchislyuvalnih resursiv Regionalnij poshuk chi pobudovu opukloyi obolonki mozhna provoditi nad mnozhinoyu tochok yaki chastkovo zminyuyutsya Obchislyuvalna skladnist dlya cogo klasu zadach zadayetsya takimi parametrami resursami neobhidnimi dlya pobudovi strukturi danih dlya poshuku resursami neobhidnimi dlya modifikaciyi pobudovanoyi strukturi resursami potribnimi dlya vidpovidi na zapiti Deyaki zadachi mozhut rozglyadatis yak taki sho nalezhat kilkom kategoriyam zalezhno vid kontekstu Napriklad Zadacha dinamichnoyi pidtrimki opukloyi obolonki polyagaye v tomu sho masiv tochok dlya yakih buduyetsya opukla obolonka zminyuyetsya z chasom dodayutsya ta vidalyayutsya tochki Variaciyi U bagatoh programah cya zadacha rozglyadayetsya yak zadacha pershogo klasu Tim ne mensh v bagatoh vipadkah potribno viznachiti chi kursor mishi lezhit vseredini danogo mnogokutnika Kursor postijno peremishuyetsya a mnogokutnik ne zminyuyetsya Analogichno mozhna pereviryati chi pevnij litalnij aparat yakij zobrazhenij na ekrani radara ne peretnuv kordon krayini Taki zadachi mozhna vvazhati zadachami geometrichnogo zapitu A v CAD sistemah sam mnogokutnik mozhe zminyuvatis tomu zadacha mozhe vvazhatis dinamichnoyu Div takozhCAD CAM Diskretna geometriya Analitichna geometriyaPrimitkiPreparata F Shejmos M Vychislitelnaya geometriya Vvedenie M Mir 1989 478 s ISBN 5 03 001041 6 A R Forrest Computational geometry Proc Royal Society London 321 series 4 187 195 1971 PosilannyaNavchalno metodichnij posibnik z kursu Obchislyuvalna geometriya ta komp yuterna grafika 10 grudnya 2008 u Wayback Machine vid fakultetu Kibernetiki KNU imeni Tarasa Shevchenka Computational Geometry 9 travnya 2011 u Wayback Machine Geometry In Action 12 kvitnya 2011 u Wayback Machine Strategic Directions in Computational Geometry Working Group Report 1996 24 lyutogo 2011 u Wayback Machine Journal of Computational Geometry 9 kvitnya 2011 u Wayback Machine LiteraturaPreparata F Shejmos M Vychislitelnaya geometriya Vvedenie Computational Geometry An introduction Mir M 1989 478 Laslo M Vychislitelnaya geometriya i kompyuternaya grafika na C BINOM M 1997 304 Skvorcov A V Triangulyaciya Delone i eyo primenenie Izdatelstvo Tomskogo universiteta Tomsk 2002 128 Glava 33 Vychislitelnaya geometriya Algoritmy postroenie i analiz Introduction to Algorithms Kormen Tomas H Lejzerson Charlz I Rivest Ronald L Shtajn Kliford 2 e izdanie 5 8459 0857 4 1047 1084 2005 M Vilyams 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 amp 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
Топ