• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Geometria obliczeniowa

    Przeczytaj także...
    Drzewo przedziałowe (interval tree, range tree, drzewo zakresowe), struktura danych przechowująca punkty, oraz związane z tymi punktami wszystkie możliwe przedziały. Drzewo przedziałowe, jeśli jest skonstruowane tak, aby było zrównoważone, pozwala odpowiadać na zapytania o dowolny przedział w czasie logarytmicznym.Otoczka wypukła, powłoka wypukła a. uwypuklenie podzbioru przestrzeni liniowej – najmniejszy (w sensie inkluzji) zbiór wypukły zawierający ten podzbiór. Otoczkę wypukłą podzbioru A {displaystyle A} oznacza się zwykle jako conv ⁡ A . {displaystyle operatorname {conv} A.}
    Robotyka – interdyscyplinarna dziedzina wiedzy działająca na styku mechaniki, automatyki, elektroniki, sensoryki, cybernetyki oraz informatyki. Domeną robotyki są również rozważania nad sztuczną inteligencją – w niektórych środowiskach robotyka jest wręcz z nią utożsamiana.

    Geometria obliczeniowa - dział algorytmiki, który wyodrębnił się w latach 70. XX wieku, zajmujący się algorytmami i strukturami danych pozwalającymi efektywnie wykonywać działania na obiektach geometrycznych, takich jak zbiory punktów, odcinków, wielokątów, okręgów.

    Wyniki geometrii obliczeniowej mają istotne znaczenie w wielu dziedzinach informatyki i inżynierii, takich jak grafika komputerowa, robotyka, symulacje komputerowe, bazy danych, projektowanie wspomagane komputerowo.

    Wykrywanie kolizji — nazwa grupy algorytmów stosowanych w grafice komputerowej i symulacjach komputerowych służących znajdowaniu ograniczeń ruchu w scenach dwu- i trójwymiarowych. Najogólniej, algorytm wykrywający kolizję odpowiada na pytanie, czy przemieszczenie jakiegoś obiektu w danym kierunku jest możliwe, czy może na drodze ruchu znajdują się przeszkody, tj. inne obiekty ruchome lub nieruchome. W symulacjach ciał odkształcających się (np. tkanin) należy również wykrywać kolizje pomiędzy różnymi fragmentami tego samego obiektu.Algorytmika to nauka o algorytmach. Jest działem informatyki, cybernetyki, a także, dla większości nauk matematyczno-przyrodniczych, ekonomii i techniki. Algorytmika zajmuje się badaniem algorytmów. Częścią algorytmiki jest algorytmizacja, czyli proces budowy konkretnego algorytmu.

    Przykładowe problemy rozważane w tej dziedzinie:

  • wyznaczanie pary najbliższych lub najdalszych punktów;
  • wyznaczanie wszystkich przecięć zbioru odcinków, okręgów itp. (wykrywanie kolizji);
  • wyznaczanie otoczki wypukłej;
  • triangulacja wielokątów;
  • przecięcia wielokątów, wieloboków, prostokątów, prostych (w tym stwierdzenie faktu przecięcia, wyznaczenie punktów przecięć, realizacja operacji boolowskich);
  • wyszukiwanie geometryczne - które obiekty, np. punkty, odcinki, leżą wewnątrz prostokąta, okręgu itp.;
  • okienkowanie;
  • planowanie ruchu robota;
  • odtwarzanie powierzchni z chmury punktów.
  • Przykładowe algorytmy i struktury danych:

    Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.Badania operacyjne - dyscyplina naukowa związana z teorią decyzji pozwalająca wyznaczyć metodę i rozwiązanie określonych problemów związanych z podjęciem optymalnych decyzji. Badania operacyjne to zbiór metod matematycznych i statystycznych, obejmujących m. in.:
  • triangulacja Delone,
  • algorytm Cohena-Sutherlanda,
  • algorytm Sutherlanda-Hodgmana,
  • algorytm Jarvisa,
  • Quickhull,
  • drzewo kd,
  • drzewo przedziałowe,
  • drzewo czwórkowe.
  • Zobacz też[]

  • metody numeryczne
  • badania operacyjne
  • optymalizacja
  • Bibliografia[]

  • Mark de Berg: Geometria obliczeniowa : algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007. ISBN 978-83-204-3244-2.
  • Franco P. Preparata, Michael Ian Shamos: Geometria obliczeniowa : wprowadzenie. Gliwice: Helion, 2003. ISBN 83-7361-098-7.
  • (window.RLQ=window.RLQ||).push(function(){mw.log.warn("Gadget \"edit-summary-warning\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");mw.log.warn("Gadget \"wikibugs\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");mw.log.warn("Gadget \"ReferenceTooltips\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");mw.log.warn("Gadget \"main-page\" styles loaded twice. Migrate to type=general. See \u003Chttps://phabricator.wikimedia.org/T42284\u003E.");});
    Projektowanie wspomagane komputerowo, CAD (ang. Computer Aided Design) – zastosowanie sprzętu i oprogramowania komputerowego w projektowaniu technicznym. Metodologia CAD znajduje zastosowanie między innymi w inżynierii mechanicznej, elektrycznej, budowlanej. Znamienne dla CAD jest cyfrowe modelowanie geometryczne mające na celu opracowanie zapisu konstrukcji wyrobu (jednego obiektu technicznego lub ich układu). Definiowaną postać konstrukcyjną wyrobu tworzą jego cechy:Algorytm Jarvisa, marsz Jarvisa lub owijanie prezentów (ang. gift wrapping algorithm) – metoda wyznaczania otoczki wypukłej zbioru punktów umieszczonych na płaszczyźnie lub przestrzeni o większej liczbie wymiarów.



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    Drzewo kd (skrót od drzewa k-wymiarowego) – struktura danych używana do dzielenia przestrzeni. Drzewa kd są przydatne w tworzeniu struktur w niektórych zastosowaniach takich jak wyszukiwanie najbliższych sąsiadów lub znajdywanie punktów w prostokątnych obszarach (w czasie O ( n + k ) {displaystyle O({sqrt {n}}+k)} , gdzie n {displaystyle n} to całkowita liczba punktów, k {displaystyle k} - liczba znalezionych punktów).
    Quickhull - algorytm dziel i zwyciężaj z dziedziny geometrii obliczeniowej, który wyznacza otoczkę wypukłą zbioru punktów umieszczonych w przestrzeni o dowolnej liczbie wymiarów (dwa, trzy i więcej). Algorytm jest wzorowany na metodzie sortowania szybkiego (ang. quicksort) i podobnie charakteryzuje go średnia złożoność O ( n log ⁡ n ) {displaystyle O(nlog n)} , natomiast pesymistyczna O ( n 2 ) {displaystyle O(n^{2})} .
    Triangulacja to podział figury geometrycznej na sympleksy (trójkąty lub czworościany) w taki sposób, że część wspólna dowolnych dwu różnych sympleksów jest ich wspólną ścianą, wspólnym wierzchołkiem, wspólnym bokiem lub wspólnym trójkątem albo zbiorem pustym. Od sympleksów tworzących triangulację wymaga się ponadto, by dowolny obszar ograniczony przecinał tylko skończoną ich liczbę. Można dokonać triangulacji każdego wielokąta i każdego wielościanu.
    Metody numeryczne – metody rozwiązywania problemów matematycznych za pomocą operacji na liczbach. Otrzymywane tą drogą wyniki są na ogół przybliżone, jednak dokładność obliczeń może być z góry określona i dobiera się ją zależnie od potrzeb.
    Triangulacja Delone (w powszechnym użyciu jest pisownia nazwiska Delaunay) to triangulacja T przestrzeni R zdefiniowana następująco:
    Algorytm Sutherlanda-Hodgmana jest analitycznym algorytmem obcinania, który znajduje część wspólną dwóch wielokątów, przy czym wielokąt obcinający musi być wypukły (wielokąt obcinany może być wypukły lub niewypukły); wielokąty są dane jako ciągi wierzchołków.
    Baza danych – zbiór danych zapisanych zgodnie z określonymi regułami. W węższym znaczeniu obejmuje dane cyfrowe gromadzone zgodnie z zasadami przyjętymi dla danego programu komputerowego specjalizowanego do gromadzenia i przetwarzania tych danych. Program taki (często pakiet programów) nazywany jest „systemem zarządzania bazą danych” (ang. database management system, DBMS).

    Reklama