La geometria computazionale è una braca dell'informatica che studia gli algoritmi per la risoluzione di problemi di natura geometrica, che trova spazio in molti ambiti dell'ingegneria e non solo tra cui la grafica computerizzata, la robotica, CAD/CAM e molti altri. Uno dei problemi più noti della geometria computazionale è quello dell'inviluppo convesso di un insieme di punti, ossia determinare il più piccolo poligono convesso tale per cui tutti i punti sono all'interno del poligono o sul suo perimetro. Gli algoritmi sviluppati utilizzeranno paradigmi di programmazione sia studiati durante gli anni come ad esempio Divide & Conquer o il metodo prune and search, oppure altri come il metodo incrementale. Il seguente lavoro ha lo scopo di sviluppare, analizzare e confrontare, sotto differenti condizioni, diversi algoritmi per l' inviluppo convesso dapprima in 2D e successivamente sviluppare e analizzare l'algoritmo quickhull per trovare l'inviluppo convesso di un insieme di punti in un generico spazio d-dimensionale, utilizzando come linguaggio di programmazione Phyton. Tramite l'ausilio di specifiche librerie tali algoritmi permetteranno sia la visualizzazione che il confronto delle prestazioni in diversi dataset.
Analisi, implementazione e confronto di algoritmi per l’inviluppo convesso
PASTÒ, CHRISTIAN
2021/2022
Abstract
La geometria computazionale è una braca dell'informatica che studia gli algoritmi per la risoluzione di problemi di natura geometrica, che trova spazio in molti ambiti dell'ingegneria e non solo tra cui la grafica computerizzata, la robotica, CAD/CAM e molti altri. Uno dei problemi più noti della geometria computazionale è quello dell'inviluppo convesso di un insieme di punti, ossia determinare il più piccolo poligono convesso tale per cui tutti i punti sono all'interno del poligono o sul suo perimetro. Gli algoritmi sviluppati utilizzeranno paradigmi di programmazione sia studiati durante gli anni come ad esempio Divide & Conquer o il metodo prune and search, oppure altri come il metodo incrementale. Il seguente lavoro ha lo scopo di sviluppare, analizzare e confrontare, sotto differenti condizioni, diversi algoritmi per l' inviluppo convesso dapprima in 2D e successivamente sviluppare e analizzare l'algoritmo quickhull per trovare l'inviluppo convesso di un insieme di punti in un generico spazio d-dimensionale, utilizzando come linguaggio di programmazione Phyton. Tramite l'ausilio di specifiche librerie tali algoritmi permetteranno sia la visualizzazione che il confronto delle prestazioni in diversi dataset.File | Dimensione | Formato | |
---|---|---|---|
Pastò_Christian.pdf
accesso aperto
Dimensione
3.18 MB
Formato
Adobe PDF
|
3.18 MB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/33546