Κατασκευή περιβαλλουσών καμπυλών : για κυρτά πολυγωνικά αντικείμενα με τη βοήθεια διαγραμμάτων 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)
