Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web servers, web development, networking and security services. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Qhull priručnik




Qhull je opšti dimenzijski kod za izračunavanje konveksnog omotača, Delonejeve triangulacije, poluprostornog preseka oko tačke, Voronojeve dijagrame, Delonejeve triangulacije najudaljenije tačke i Voronojeve dijagrame najudaljenije tačke. Ove strukture imaju primenu u nauci, inženjeringu, statistici i matematici. Pogledaj Fukudin uvod za konveksne omotače, Delonejevu triangulaciju, Voronojeve dijagrame i linearno programiranje. Za detaljno upoznavanje pogledajte O'Rurkovu ['94], Računsku geometriju u C.

Postoji šest programa. Osim rbox-a, svi koriste isti kod. Qhull uvodi Quickhull algoritam za izračunavanje konveksnih omotača. Qhull obuhvata opcije za obim omotača, površinu aspekta, višestruke izlazne formate i grafički izlaz. U stanju je da približno odredi konveksni omotač.

Qhull upravlja greškama zaokruživanja od algoritma pokretnog zareza. Generiše konveksni omotač sa “debelim” aspektima. Spoljna ravan jedne strane je jasno iznad svih tačaka. Unutrašnja ravan je jasno ispod temena aspekta. Svaki tačan konveksni omotač mora ležati između unutrašnje i spoljašnje ravni.

Qhull koristi spojene strane. Spojni ulaz takođe garantuje simplicijalni izlaz, ali je manje precizan od spojenih aspekata. Za njih Qhull izračunava maksimalnu spoljnu i unutarnju ravan.

Kada koristiti Qhull

Qhull gradi konveksne omotače, Delonejeve triangulacije, poluprostorni presek, Voronojeve dijagrame, Delonejeve triangulacije najudaljenije tačke i Voronojeve dijagrame najudaljenije tačke.

Za konveksne omotače i poluprostorni presek, Qhull se može koristiti za 2-d do 8-d. Za Voronojeve dijagrame i Delonejeve triangulacije Qhull se može koristiti za 2-d do 7-d. U višim dimenzijama, veličina izlaza ubrzano raste i Qhull ne funkcioniše dobro uz virtuelnu memoriju. Ako je n veličina ulaza, a d je dimenzija (d>=3), veličina izlaza i vreme izvršenja rastu za n^(floor(d/2) [vidi Izvedba ]. Na primer, ne pokušavajte da izgradite 16-d konveksni omotač od 100 tačaka. Imaće red 1,000,000,000,000,000,000,000,000 aspekata.

Na Pentiumu 3 od 600 MHz, Qhull izračunava 2-d konveksni omotač od 300.000 ko-cirkularnih tačaka za 11 sekundi. Izračunava 2-d Delonejevu triangulaciju i 3-d konveksni omotač od 120.000 tačaka za 12 sekundi. Izračunava 3-d Delonejevu triangulaciju i 4-d konveksni omotač od 40.000 tačaka za 18 sekundi. Izračunava 4-d Delonejevu triangulaciju i 5-d konveksni omotač od 6,000 tačaka za12 sekundi. Izračunava 5-d Delonejevu triangulaciju i 6-d konveksni omotač od 1,000 tačaka za 12 sekundi. Izračunava 6-d Delonejevu triangulaciju i 7-d konveksni omotač od 300 tačaka za 15 sekundi. Izračunava 7-d Delonejevu triangulaciju i 8-d konveksni omotač od 120 tačaka za 15 sekundi. Izračunava 8-d Delonejevu triangulaciju i 9-d konveksni omotač od 70 tačaka za 15 sekundi. Izračunava 9-d Delonejevu triangulaciju i 10-d konveksni omotač od 50 tačaka za 17 sekundi. 10-d konveksni omotač od 50 tačaka ima oko 90,000 maksimalnih strana.

Qhull ne podržava ograničenu Delonejevu triangulaciju, triangulaciju nekonveksnih površina, mrežno generianje nekonveksnih objekata, ni ulaza srednje veličine u 9-D i više.

To je veliki paket sa mnogo opcija. Jedan je od najbržih dostupnih. To je jedinstveni 3-d kod koji upravlja problemima preciznosti, s obzirom na aritmetički pokretni zarez. Na primer, uvodi funckiju identiteta za ekstremne tačke (vidi Nepreciznostu u Qhullu ).

Ako vam je potreban kratki kod za konveksni omotač, Delonejevu triangulaciju ili Voronojev obim razmislite o Klarksobovom programu za omotač . Ako vam je potrebna 2-d Delonejeva triangulacija razmislite o Ševčakovom programu trouglova . Mnogo je brži od Qhulla i omogućava ograničenja. Oba programa koriste egzaktnu aritmetiku. Nalaze se u http://www.netlib.org/voronoi/ . Qhull verzija 1.0 vam takođe može koristiti. Otkriva probleme preciznosti, ali ih ne rešava.

Leda je biblioteka za pisanje programa računske geometrije i drugih kombinatornih algoritama. Obuhvata rutinu za izračunavanje 3-d konveksnih omotača, 2-d Delonejeve triangulacije i 3-d Delonejeve triangulacije. Daje racionalni aritmetički i grafički izlaz. Funkcioniše na većini platformi.

Ako je vaš problem u visokim dimenzijama sa nekoliko nesimplicijalnih strana, isprobajte Fukudin cdd . Prilično je brži od Qhulla za ovu distribuciju.

Namenski softver za 2-d i 3-d konveksne omotače može biti brži od Qhulla. Namenski softver bi trebalo da koristi manje memorije. Qhull koristi strukturu podataka i kod opšte dimenzije. Struktura podataka podržava nesimplicijalni aspekt.

Qhull nije pogodan za mrežno generisanje ili triangulaciju arbitrarnih površina. Možete koristiti Qhull ako je površina konveksna ili potpuno vidljiva iz unutrašnje tačke (npr. zvezdasti poliedar). Kao prvo, projektujte svaku poziciju na sferu koja je centrirana na unutrašnju tačku. Zatim izračunajte konveksni omotač projektovane pozicije. Maksimalne strane konveksnog omotača odgovaraju triangulaciji površine. Za mrežno generisanje arbitrarne površine pogledajte Šnajderovo konačno mrežno generisanje elemenata.

Qhull nije pogodan za ograničene Delonejeve triangulacije. Uz mnogo rada možete napisati program koji koristi Qhull za dodavanje ograničenja tako što dodaje još tačaka triangulaciji.

Qhull nije pogodan za deobu arbitrarnih objekata. Koristite qdeloneja za deobu konveksnih objekata.

» Opis Qhulla » Оpcije za korišćenje Qhulla »Interni Qhull » Štа raditi ako nešto krene kako ne treba » E-mail » Autori

   C. Bradford Barber                    Hannu Huhdanpaa
   bradb@shore.net                       hannu@qhull.org

Priznanja Reference

Aurenhammer, F., "Voronoi diagrams -- A survey of a fundamental geometric data structure," ACM Computing Surveys, 1991, 23:345-405.

Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM Transactions on Mathematical Software, 22(4):469-483, Dec 1996, www.qhull.org [http://portal.acm.org; http://citeseerx.ist.psu.edu].

Clarkson, K.L. and P.W. Shor, "Applications of random sampling in computational geometry, II", Discrete Computational Geometry, 4:387-421, 1989

Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results on randomized incremental construction," Computational Geometry: Theory and Applications, vol. 3, p. 185-211, 1993.

Devillers, et. al., "Walking in a triangulation," ACM Symposium on Computational Geometry, June 3-5,2001, Medford MA.

Dobkin, D.P. and D.G. Kirkpatrick, "Determining the separation of preprocessed polyhedra--a unified approach," in Proc. 17th Inter. Colloq. Automata Lang. Program., in Lecture Notes in Computer Science, Springer-Verlag, 443:400-413, 1990.

Edelsbrunner, H, Geometry and Topology for Mesh Generation, Cambridge University Press, 2001.

Gartner, B., "Fast and robust smallest enclosing balls", Algorithms - ESA '99, LNCS 1643.

Fortune, S., "Computational geometry," in R. Martin, editor, Directions in Geometric Computation, Information Geometers, 47 Stockers Avenue, Winchester, SO22 5LB, UK, ISBN 1-874728-02-X, 1993.

Milenkovic, V., "Robust polygon modeling," Computer-Aided Design, vol. 25, p. 546-566, September 1993.

Mucke, E.P., I. Saias, B. Zhu, Fast randomized point location without preprocessing in Two- and Three-dimensional Delaunay Triangulations, ACM Symposium on Computational Geometry, p. 274-283, 1996 [GeomDir].

Mulmuley, K., Computational Geometry, An Introduction Through Randomized Algorithms, Prentice-Hall, NJ, 1994.

O'Rourke, J., Computational Geometry in C, Cambridge University Press, 1994.

Preparata, F. and M. Shamos, Computational Geometry, Springer-Verlag, New York, 1985.





Published (Last edited): 27-11-2012 , source: http://www.qhull.org/html/index.htm#TOC