Construction of Surrounding Curves

Στην εργασία αυτή παρουσιάζεται η κατασκευή μίας καμπύλης, η οποία περιβάλλει ξένα ανά δύο κυρτά πολύγωνα στο επίπεδο. Το βασικό εργαλείο με το οποίο δημιουργείται αυτή η καμπύλη, είναι το διάγραμμα Voronoi των κορυφών των πολυγώνων. Η κατασκευή αυτή εξυπηρετεί την επίλυση του προβλήματος ανακατασκευής επιφανειών που παρεμβάλλουν οπές σε παράλληλα επίπεδα. Παρουσιάζονται δύο αλγόριθμοι που υλοποιήθηκαν για την κατασκευή της καμπύλης αυτής, οι οποίοι ξεκινώντας από την κυρτή θήκη των πολυγώνων, αναζητούν πολύγωνα στο εσωτερικό της και τα προσθέτουν στην ακολουθία των πολυγώνων που ορίζουν την τρέχουσα περιβάλλουσα καμπύλη. Ο ένας αλγόριθμος κάνει αναζήτηση περιφερειακά, μιμούμενος την Breadth First αναζήτηση που χρησιμοποιείται σε γραφήματα, ενώ ο δεύτερος κάνει αναζήτηση πρώτα εις βάθος, μιμούμενος την Depth First αναζήτηση. Στη συνέχεια παρατίθενται παραδείγματα εφαρμογής των αλγορίθμων μας, καθώς και το public interface των κλάσεων C++ του κώδικα της υλοποιήσης μας. Τέλος καταγράφονται κάποιες ιδέες για μελλοντικές βελτιώσεις της εργασίας αυτής.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