Algoritmi per chiusura convessa in alte dimensionalità : analisi, sviluppo, visualizzazione ed approssimazioni

Madonna, Lorenzo (2017) Algoritmi per chiusura convessa in alte dimensionalità : analisi, sviluppo, visualizzazione ed approssimazioni. Bachelor thesis, Scuola Universitaria professionale della Svizzera italiana (SUPSI).

Full text not available from this repository.

Abstract

Versione italiana. La chiusura convessa di un insieme di punti in un piano è il più piccolo poligono convesso che li racchiude tutti. Questa definizione si generalizza facilmente al caso di punti in uno spazio di dimensionalità generica. Le applicazioni di questo tipo di algoritmi spaziano dalla robotica alla computer vision fino alla data science. È possibile trovare la chiusura convessa utilizzando la programmazione lineare partendo dalla sua definizione in uno spazio di dimensionalità generica. Nel caso particolare di spazi bidimensionali esistono molti algoritmi da usare per trovare la chiusura convessa in modo efficace. Uno tra questi è l’algoritmo di Jarvis, noto per la sua semplicità anche a livello di implementazione, ma che non può essere esteso a dimensionalità generiche. Fra le altre tecniche note, l'algoritmo più efficiente è denominato QuickHull. Originariamente ideato per il caso bidimensionale, QuickHull è stato generalizzato al caso tridimensionale e, in linea di principio, può essere ulteriormente esteso a spazi di dimensione generica. Il contributo di questo progetto è l’implementazione di quest’ultima versione, che permetta quindi di calcolare chiusure convesse di insiemi di punti in spazi di dimensionalità generica (e tipicamente maggiore di tre) in maniera più rapida di quanto non si avrebbe con la programmazione lineare. Per avere una verifica di tipo intuitivo del funzionamento dell’algoritmo è stata inoltre implementata un’interfaccia di visualizzazione per il caso 2D e 3D e sono stati testati in maniera empirica gli effetti di un arrotondamento nelle coordinate dei punti. Versione inglese. The convex hull of a set of N points in two dimensions is the smallest convex polygon enclosing the points. This definition can be easily generalized when the points are in a space of general dimensionality. Typical application domains for this task include robotics, computer vision, data clustering, and others. By definition the convex hull can be found using linear programming techniques in general dimension. Lots of more efficient algorithms have been developed specifically for the two-dimensional case. Among them, Jarvis algorithm is known for its simplicity wich makes the implementation particulary simple, but it cannot be extended to general dimensions. The most efficient convex hull algorithm is called Quickhull. Originally created for the two-dimensional case. Quickhull was also generalized to the three-dimensional case and can be extended to general dimension. The purpose of this project is the implementation of general Quickhull able to compute of convex hulls of sets of points in generic dimension more efficiently than linear programming. Besides the implementation of the algorithm a graphical interface for 2D and 3D cases was developed in order to have an intuitive check of the algorithm. The approximations of points coordinates were also tested in an empirical way.

Item Type: Thesis (Bachelor)
Supervisors: Gambardella, Luca Maria and Antonucci, Alessandro
Subjects: Informatica
Divisions: Dipartimento tecnologie innovative > Ingegneria informatica
URI: http://tesi.supsi.ch/id/eprint/1736

Actions (login required)

View Item View Item