Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Изчислителна геометрия

) - отрасль компьютерных наук посвящена изучению алгоритмов что описуюються в терминах геометрии. Изчислителната геометрия ( изчислителната геометрия ) е клон на компютърните науки, посветен на изучаването на алгоритми, които са описани от гледна точка на геометрията.

Основният стимул за развитието на изчислителната геометрия като дисциплина е напредъкът в компютърната графика и компютърното проектиране и компютърните системи за технологична подготовка на производството, но много проблеми на компютърната геометрия са класически по характер и могат да се появят по време на математическа визуализация.

Друго важно приложение на изчислителната геометрия е роботиката (планиране на движението и задачите за разпознаване на образи), географските информационни системи (геометрично търсене, планиране на маршрута), проектирането на чипове и програмирането на машини за числено управление.

Основните раздели на изчислителната геометрия са:

  • Комбинаторна изчислителна геометрия , или наричана още алгоритмична геометрия , която третира геометричните обекти като дискретни единици. Основополагащата книга по тази тема е книгата „Подготовка“ и „Шеймос“, в която за първи път през 1975 г. е използван терминът „компютърна геометрия“.
  • Числена изчислителна геометрия , наричана още геометрична машина или геометрично моделиране , която се занимава главно с представянето на обекти от реалния свят във форма, подходяща за по-нататъшна компютърна обработка. Този раздел може да се разглежда като по-нататъшно развитие на описателната геометрия и често се разглежда като част от компютърната графика. Терминът "изчислителна геометрия" в този смисъл се използва от 1971 г. насам.

Комбинаторна изчислителна геометрия

Основната цел на изследванията в комбинаторната изчислителна геометрия е разработването на ефективни алгоритми и структури от данни за решаване на задачи, които са дадени от гледна точка на основни геометрични обекти: точки, сегменти, полигони, полиедри и др.

Някои от тези задачи изглеждат толкова просто, че не са били разглеждани като задачи до изобретяването на компютри. Да вземем за пример задачата да намерим най-близката двойка точки:

  • Наличието на n точки на една равнина, намери две разстояния, между които е най-малката

Можете да изчислите разстоянията между всяка двойка точки (има n (n-1) / 2 ), след което изберете двойката с най-кратко разстояние. Такова пълно изброяване има сложност O ( n 2), времето на изпълнение е пропорционално на квадрата на броя точки. Класическият резултат в изчислителната геометрия е алгоритъм с сложност O ( N Log N ). Също така отворени рандомизирани алгоритми, работещи в O ( n ) стъпки, и детерминистични алгоритми, работещи в O ( N Log Log N ).

Изчислителната геометрия се фокусира главно върху сложността на изчисленията, тъй като алгоритмите са проектирани да работят на много големи масиви от данни от десетки или стотици милиони точки. При големи набори от данни разликата между O ( n 2) и O ( N Log N ) може да бъде същата като разликата между дните и секундите.

Класове задачи

Основните задачи на изчислителната геометрия могат да бъдат класифицирани по различни начини и с различни критерии. Има следните класове:

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

При проблемите от тази категория, някои данни се въвеждат във входа и алгоритъмът трябва да изчисли съответните резултати след тях. Примери за такива основни задачи са:

  • Изпъкнал корпус: Като набор от точки, намерете най-малкия изпъкнал многоъгълник, съдържащ всички точки.
  • Пресечни сегменти: намерете всички раздели в набор от сегменти.
  • Триангулация на Делоне
  • Диаграма на Вороной: Като набор от точки, разделете пространството на сектори, всяка точка от които е по-близо до своята от множеството, отколкото към другата.
  • Линейно програмиране
  • Задачата на най-близката двойка точки: Да имаш набор от точки, за да намериш две разстояния, между които е най-малката.
  • Евклидов кратък път: Свържете двете точки на евклидовото пространство (с многоъгълни препятствия) по възможно най-краткия начин.
  • Полигон триангулация: Като полигон, разделят вътрешността му на триъгълници
  • Генерация Mesh English Мрежово поколение

Изчислителната сложност за този тип задачи се определя от времето и пространството (размер на паметта), които са необходими за решаване на конкретен проблем.

Задачи за геометрично търсене (заявка)

При задачите за геометрично търсене входните данни се състоят от две части: пространство за търсене и пространство за запитване, които се различават в различните типове задачи. Обикновено пространството за търсене изисква предварителна обработка, за да се изпълняват ефективно няколко заявки.

Примери за проблеми с геометричното търсене:

  • Регионално търсене (en: Търсене на диапазон): Обработва набор от точки, за да намери ефективно набора от точки, съдържащи се в заявения регион.
  • Локализация на точка (en: Точка местоположение): Като дял от пространството в региони, създайте структура на данните, която ще ви позволи да определите ефективно в кой регион се намира тази точка.
  • Намиране на най-близкия съсед: Обработете набор от точки за достъп до всички възможности, за да намерите ефективно кои точки са по-близо до заявените.
  • Проследяване на лъчи: Като набор от обекти в пространството, създайте структура от данни, която ще ви позволи да определите ефективно кои обекти на прасковата лъч е търсена.

Ако пространството за търсене е фиксирано, обикновено се определя изчислителната сложност на задачите

  • време и място, необходими за предварителна обработка (изграждане на ефективна структура от данни)
  • време (вероятно рядко място), необходимо за получаване на отговор на всяко искане.

В случаите, когато пространството за търсене може да е различно, вижте раздела Динамични задачи.

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

Динамичните задачи са типът задачи, към които постепенно се променят входящите данни (например се добавят или изтриват обекти). Алгоритмите за решаване на такива проблеми включват поддръжка на динамични структури от данни. Всеки проблем на компютърната геометрия може да бъде решен динамично, но за сметка на допълнителни изчислителни ресурси. Регионалното търсене или конструирането на черупката opukolo може да се извърши на набор от точки, които се променят.

Изчислителната сложност за този клас задачи се определя от следните параметри:

  • ресурси, необходими за изграждане на структура от данни за търсене
  • ресурси, необходими за промяна на изградената структура
  • и ресурси, необходими за отговор на исканията

Някои задачи могат да се разглеждат като принадлежащи към няколко категории в зависимост от контекста.

Например разгледайте следните задачи:
Принадлежност на точка към многоъгълник: Определете точката, разположена извън или вътре в дадения полигон.


вариации

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





Вижте също:

Обратна матрица свойства

Определителят на матрицата | Детерминанта на матрицата

Линейна матрична алгебра. решение

Дискретна математика

Теория на категорията

Връщане към съдържанието: Висша математика

2019 @ ailback.ru