oryginal-geometria-obliczeniowa-wprowadzenie_geobli.pdf
(
18213 KB
)
Pobierz
666131005 UNPDF
IDZ DO
PRZYK£ADOW
Y ROZDZIA£
Geometria obliczeniowa.
SPIS TRECI
Wprowadzenie
KATALOG KSI¥¯EK
Autorzy: Franco P. Preparata, Michael Ian Shamos
T³umaczenie: Tomasz ¯mijewski
ISBN: 83-7361-098-7
Tytu³ orygina³
u:
Computational Geometry. An Introduction
Format: B5, stron: 386
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
W ostatniej dekadzie systematyczne badania algorytmów geometrycznych
spowodowa³y utworzenie nowej dziedziny badawczej -- geometrii obliczeniowej.
Jej osi¹gniêcia maj¹ szerokie zastosowanie w prze¿ywaj¹cej ostatnio b³yskawiczny
rozwój trójwymiarowej grafice komputerowej, a tak¿e w automatyce, robotyce
i w statystyce. Ksi¹¿ka niniejsza to obszerny, systematyczny i jednolity wyk³ad
na ten temat. Stanowi ona klasyczn¹ pozycjê w tym zakresie informatyki.
Najwa¿niejszym zadaniem geometrii obliczeniowej jest wskazanie pojêæ, w³aciwoci
i technik, które bêd¹ pomocne przy tworzeniu sprawnych algorytmów rozwi¹zuj¹cych
problemy z dziedziny geometrii.
Tematy poruszane w tej ksi¹¿ce, to miêdzy innymi:
• podstawy geometrii i historia geometrii obliczeniowej
• wyszukiwanie geometryczne
• uzyskiwanie informacji o obiektach
• tworzenie otoczki wypuk³ej wraz z szeregiem problemów z tym zagadnieniem
zwi¹zanych,
• s¹siedztwo, przeciêcia oraz geometria prostok¹tów
W ksi¹¿ce metody geometrii obliczeniowej prezentowane s¹ przez szczegó³owe
omówienie konkretnych przypadków. Pocz¹tkowo ksi¹¿ka ta mia³a byæ podrêcznikiem
dla studentów, ale w jej obecnym kszta³cie bêdzie przydatna tak¿e dla badaczy i dla
osób zawodowo zajmuj¹cych siê projektowaniem wspomaganym komputerowo, grafik¹
komputerow¹ i robotyk¹.
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treci
Wstp do wydania drugiego...............................................................................9
Wstp ....................................................................................................................11
1
Wprowadzenie ....................................................................................................13
1.1. Rys historyczny..........................................................................................................................13
1.1.1. Złoono geometrii klasycznej........................................................................................14
1.1.2. Teoria zbiorów wypukłych, geometria metryczna i kombinatoryczna............................16
1.1.3. Wczeniejsze prace ...........................................................................................................16
1.1.4. Ku geometrii obliczeniowej ..............................................................................................17
1.2. Wprowadzenie do algorytmów .................................................................................................17
1.2.1. Algorytmy: zapis i okrelanie wydajnoci........................................................................18
1.2.2. Nieco o technikach tworzenia algorytmów ......................................................................21
1.2.3. Struktury danych..............................................................................................................22
1.3. Podstawy geometrii....................................................................................................................28
1.3.1. Definicje ogólne, przyj2te konwencje................................................................................28
1.3.2. Niezmienniki grup przekształce3 liniowych....................................................................30
1.3.3. Dualno geometryczna. Biegunowo ............................................................................35
1.4. Modele obliczeniowe..................................................................................................................37
Przeszukiwanie geometryczne..........................................................................47
2.1. Wprowadzenie do przeszukiwania geometrycznego................................................................47
2.2. Problemy lokalizacji punktu ......................................................................................................51
2.2.1. Rozwaania ogólne. Najprostsze przypadki ....................................................................51
2.2.2. Lokalizacja punktu w obszarze płaszczyzny....................................................................55
2.3. Problemy zwi9zane z przeszukiwaniem zakresu......................................................................78
2.3.1. Rozwaania ogólne...........................................................................................................78
2.3.2. Metoda wielowymiarowego drzewa binarnego (k-D drzewa).........................................83
2.3.3. Metoda bezporedniego dost2pu i jej odmiany................................................................87
2.3.4. Metoda drzew zakresu i jej odmiany................................................................................91
6
SPIS TRECI
2.4. Szukanie iterowane i kaskadowanie ułamkowe........................................................................96
2.5. Uwagi i komentarze...................................................................................................................99
2.6. ?wiczenia.................................................................................................................................101
Otoczki wypukłe: algorytmy podstawowe...................................................103
3.1. Informacje wst2pne..................................................................................................................103
3.2. Sformułowanie problemu i ograniczenia dolne.......................................................................107
3.3. Algorytmy otoczki wypukłej na płaszczyAnie .........................................................................111
3.3.1. Pierwsze dokonania w dziedzinie algorytmów otoczki wypukłej.................................111
3.3.2. Skan Grahama.................................................................................................................114
3.3.3. Marsz Jarvisa ..................................................................................................................117
3.3.4. Techniki QUICKHULL ...................................................................................................119
3.3.5. Algorytmy typu „dziel i rz9dA”......................................................................................121
3.3.6. Dynamiczne algorytmy otoczki wypukłej......................................................................124
3.3.7. Uogólnienie: zachowanie otoczki wypukłej ...................................................................130
3.4. Otoczki wypukłe w wi2kszej liczbie wymiarów ni dwa........................................................136
3.4.1. Metoda opakowywania prezentu...................................................................................137
3.4.2. Metoda „pod-poza”........................................................................................................142
3.4.3. Trójwymiarowe otoczki wypukłe...................................................................................145
3.5. Uwagi i komentarze.................................................................................................................150
3.6. ?wiczenia.................................................................................................................................152
Otoczki wypukłe: rozszerzenia i zastosowanie ...........................................155
4.1. Rozszerzenia i odmiany ...........................................................................................................155
4.1.1. Analiza przypadku redniego ........................................................................................155
4.1.2. Algorytmy przyblienia otoczki wypukłej.....................................................................159
4.1.3. Problem maksimów zbioru punktów.............................................................................162
4.1.4. Otoczka wypukła wielok9ta prostego............................................................................170
4.2. Zastosowania statystyczne.......................................................................................................174
4.2.1. Solidne oszacowania.......................................................................................................175
4.2.2. Regresja izotoniczna .......................................................................................................177
4.2.3. Klastrowanie (rednica zbioru punktów).......................................................................179
4.3. Uwagi i komentarze.................................................................................................................185
4.4. ?wiczenia.................................................................................................................................186
Blisko$%: algorytmy podstawowe...................................................................187
5.1. Zbiór problemów .....................................................................................................................188
5.2. Prototyp obliczeniowy: niepowtarzalno elementu ...............................................................193
5.3. Ograniczenia dolne...................................................................................................................194
5.4. Problem najbliszej pary: metoda „dziel i rz9dA”......................................................................196
5.5. Rozwi9zywanie lokalne problemów bliskoci: diagram Voronoi............................................205
5.5.1. Właciwoci Voronoi ......................................................................................................206
5.5.2. Tworzenie diagramu Voronoi.........................................................................................212
SPIS TRECI
7
5.6. Rozwi9zywanie problemów s9siedztwa diagramem Voronoi.................................................219
5.7. Uwagi i komentarze.................................................................................................................222
5.8. ?wiczenia.................................................................................................................................223
Blisko$%: odmiany i uogólnienia.....................................................................225
6.1. Euklidesowe drzewa minimalne..............................................................................................225
6.1.1. Problem komiwojaera w przestrzeni euklidesowej......................................................228
6.2. Triangulacje płaskie..................................................................................................................232
6.2.1. Triangulacja zachłanna....................................................................................................233
6.2.2. Triangulacje ograniczone................................................................................................235
6.3. Uogólnienia diagramu Voronoi................................................................................................238
6.3.1. Diagramy Voronoi wyszego rz2du (na płaszczyAnie)..................................................239
6.3.2. Wielowymiarowe diagramy Voronoi punktu najbliszego i punktu najdalszego.........249
6.4. Przerwy i pokrycia...................................................................................................................252
6.5. Uwagi i komentarze.................................................................................................................258
6.6. ?wiczenia.................................................................................................................................260
Przecicia............................................................................................................263
7.1. Przykładowe zastosowania......................................................................................................264
7.1.1. Problemy ukrytych linii i ukrytych powierzchni............................................................264
7.1.2. Rozpoznawanie wzorca..................................................................................................265
7.1.3. Układ cieek i elementów.............................................................................................266
7.1.4. Programowanie liniowe i wspólne przeci2cie półprzestrzeni........................................267
7.2. Zastosowania na płaszczyAnie .................................................................................................268
7.2.1. Przeci2cie wielok9tów wypukłych..................................................................................268
7.2.2. Przeci2cie wielok9tów gwiazdokształtnych....................................................................273
7.2.3. Przeci2cie odcinków .......................................................................................................274
7.2.4. Przeci2cie półpłaszczyzn.................................................................................................283
7.2.5. Dwuzmienne programowanie liniowe...........................................................................285
7.2.6. J9dro wielok9ta płaskiego...............................................................................................294
7.3. Zastosowania trójwymiarowe..................................................................................................300
7.3.1. Przeci2cia wielocianów wypukłych ..............................................................................300
7.3.2. Przecinanie półprzestrzeni..............................................................................................308
7.4. Uwagi i komentarze.................................................................................................................313
7.5. ?wiczenia.................................................................................................................................315
Geometria prostok+tów....................................................................................317
8.1. Wybrane zastosowania geometrii prostok9tów.......................................................................317
8.1.1. Wspomaganie projektowania VLSI.................................................................................317
8.1.2. Wielodost2p w bazach danych .......................................................................................319
8.2. Dziedzina poprawnoci wyników............................................................................................321
8.3. Ogólne uwagi o algorytmach modelu statycznego..................................................................323
8
SPIS TRECI
8.4. Miara i obwód sumy prostok9tów...........................................................................................325
8.5. Kontur sumy prostok9tów.......................................................................................................332
8.6. Domkni2cie sumy prostok9tów ...............................................................................................339
8.7. Zewn2trzny kontur sumy prostok9tów...................................................................................343
8.8. Przeci2cia prostok9tów i podobne problemy...........................................................................348
8.8.1. Przeci2cia prostok9tów...................................................................................................348
8.8.2. Jeszcze raz problem przeci2cia prostok9tów..................................................................352
8.8.3. Zawieranie prostok9tów.................................................................................................355
8.9. Uwagi i komentarze.................................................................................................................360
8.10. ?wiczenia...............................................................................................................................361
Literatura ............................................................................................................363
Skorowidz...................... ....................................................................................375
Plik z chomika:
w_kas
Inne pliki z tego folderu:
full-version-aparaty-cyfrowe-praktyczny-przewodnik_cyfprz.pdf
(23760 KB)
full-version-abc-fotografii-cyfrowej-i-obrobki-zdjec_abcfob.pdf
(61050 KB)
oryginal-informatyka-europejczyka-informatyka-program-nauczania-dla-szkol-ponadgimnazjalnych_infopn.pdf
(2560 KB)
oryginal-informatyka-europejczyka-informatyka-podrecznik-dla-szkol-ponadgimnazjalnych-czesc-2_ponad2.pdf
(56799 KB)
oryginal-geometria-obliczeniowa-wprowadzenie_geobli.pdf
(18213 KB)
Inne foldery tego chomika:
Pliki dostępne do 21.01.2024
Pliki dostępne do 27.02.2021
__WLAD_FLOR
_Audiobook(123)
1_1aaaa
Zgłoś jeśli
naruszono regulamin