Construction of Surrounding Curves

RDF 

 
Το τεκμήριο παρέχεται από τον φορέα :
Πανεπιστήμιο Κρήτης
Αποθετήριο :
E-Locus Ιδρυματικό Καταθετήριο
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



Σημασιολογικός εμπλουτισμός/ομογενοποίηση από το EKT
2009 (EL)
Κατασκευή περιβαλλουσών καμπυλών : για κυρτά πολυγωνικά αντικείμενα με τη βοήθεια διαγραμμάτων Voronoi
Construction of Surrounding Curves

Κουτάκη-Παντερμάκη, Ειρήνη Αριστείδη

Καραβέλας Μενέλαος

Στην εργασία αυτή παρουσιάζεται η κατασκευή μίας καμπύλης, η οποία περιβάλλει ξένα ανά δύο κυρτά πολύγωνα στο επίπεδο. Το βασικό εργαλείο με το οποίο δημιουργείται αυτή η καμπύλη, είναι το διάγραμμα Voronoi των κορυφών των πολυγώνων. Η κατασκευή αυτή εξυπηρετεί την επίλυση του προβλήματος ανακατασκευής επιφανειών που παρεμβάλλουν οπές σε παράλληλα επίπεδα. Παρουσιάζονται δύο αλγόριθμοι που υλοποιήθηκαν για την κατασκευή της καμπύλης αυτής, οι οποίοι ξεκινώντας από την κυρτή θήκη των πολυγώνων, αναζητούν πολύγωνα στο εσωτερικό της και τα προσθέτουν στην ακολουθία των πολυγώνων που ορίζουν την τρέχουσα περιβάλλουσα καμπύλη. Ο ένας αλγόριθμος κάνει αναζήτηση περιφερειακά, μιμούμενος την Breadth First αναζήτηση που χρησιμοποιείται σε γραφήματα, ενώ ο δεύτερος κάνει αναζήτηση πρώτα εις βάθος, μιμούμενος την Depth First αναζήτηση. Στη συνέχεια παρατίθενται παραδείγματα εφαρμογής των αλγορίθμων μας, καθώς και το public interface των κλάσεων C++ του κώδικα της υλοποιήσης μας. Τέλος καταγράφονται κάποιες ιδέες για μελλοντικές βελτιώσεις της εργασίας αυτής. (EL)
In this thesis, we present the construction of a curve that surrounds disjoint convex polygons on a plane. The basic tool that we use is the Voronoi diagram of the polygon vertices. The solution to this problem serves as an intermediate step in the construction of surfaces that interpolate contours on parallel cross sections. We present two algorithms that we have developed, which output the surrounding curve. These algorithms, start from the convex hull, and then search for polygons in its interior and insert them in the sequence of polygons currently comprising the surrounding curve. The first algorithm searches in a breadth first search manner, while the second searches in a depth first search tactic. We demostrate the applicability of our algorithms via examples, and present the public interface of the implemented C++ classes of our implementation. Finally, we discuss some ideas for further reasearch and improvements. (EN)

text

Delaunay triangulation
τριγωνοποίηση Delaunay

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

2009-07-09




*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.