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.
2021
Analysis, implementation, and comparison of algorithms for the convex hull
Inviluppo convesso
Involucro convesso
Convex Hull
quickhull
File in questo prodotto:
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/33546