Στην παρούσα εργασία, παρουσιάσαμε ένα νέο τρόπο υπολογισμού της Τριγωνοποίησης Delaunay με τη χρήση Γενετικού αλγορίθμου. Κωδικοποιήσαμε τα χρωμοσώματα του πληθυσμού ως γράφους με κορυφές και ακμές. Οι κορυφές αντιστοιχούν στα σημεία του επιπέδου τα οποία δίνουμε ως είσοδο και οι ακμές ενώνουν μεταξύ τους τα σημεία αυτά. Πρώτα μελετήσαμε τη βιβλιογραφία για γνωστούς αλγόριθμους εύρεσης Τριγωνοποίησης Delaunay καθώς και για το δυϊκό της πρόβλημα που είναι τα Διαγράμματα Voronoi. Κατόπιν μελετήσαμε υπάρχουσες εφαρμογές οι οποίες επιλύουν γεωμετρικά προβλήματα με τη χρήση των Γενετικών Αλγορίθμων. Ως αποτέλεσμα της προηγούμενης μελέτης δημιουργήσαμε εφαρμογή, τη Delaunay_Genetic, σε γλώσσα προγραμματισμού C++ η οποία παίρνει ως είσοδο αρχείο με συντεταγμένες σημείων του επιπέδου και τα αποθηκεύει σε μια δομή στη μνήμη. Κατόπιν με βάση τα σημεία αυτά η Delaunay_Genetic δημιουργεί αρχικό πληθυσμό ατόμων δηλαδή αρχική γενιά, και αναπαράγει από τον αρχικό πληθυσμό (γενιά) νέες γενιές ατόμων σε κάθε επανάληψη της Γενετικής Διαδικασίας της Αναπαραγωγής. Κάθε νέα γενιά είναι πιο εύρωστη από την προηγούμενη δηλαδή περιέχει πιο αξιόλογα άτομα δηλαδή άτομα που αναπαριστούν καλύτερες Τριγωνοποιήσεις όσον αφορά τα κριτήρια της Τριγωνοποίησης Delaunay. Στην τελευταία γενιά επιλέγουμε το καλύτερο άτομο της γενιάς αυτής ως έξοδο της Delaunay_Genetic. Από διάφορες εκτελέσεις της Delaunay_Genetic που έχουμε κάνει βλέπουμε ότι η Τριγωνοποίηση που καταλήγει προσεγγίζει σε πολύ μεγάλο βαθμό (συνήθως πάνω από 98% έως 100%) τη ζητούμενη Τριγωνοποίηση Delaunay. Μελλοντικά θα βελτιώσουμε διάφορα τμήματα της εφαρμογής με διάφορους τρόπους προκειμένου να βελτιωθεί και ο χρόνος εκτέλεσης, ο οποίος στην παρούσα της έκδοση απέχει αρκετά από το χρόνο των παραδοσιακών αλγορίθμων Τριγωνοποίησης.
In this work, we introduce a new way of computing Delaunay Triangulations using Genetic Algorithms. We decode a given set of points in the plane as vertices and connect these points together by edges. Every such decoding is a chromosome of population. At first we studied the literature on well-known Delaunay Triangulation Finding Algorithms as well as its binary problem called Voronoi Diagrams. Then we studied existing applications that solve geometric problems using Genetic Algorithms. As a result of the previous study, we created an application, called Delaunay_Genetic, in C++ programming language that takes a file with input coordinates in the plane and stores them in memory in a data structure. Then, based on these points, Delaunay_Genetic creates an initial population of individuals (chromosomes), an initial generation, and reproduces from the original population (generation) new generations of individuals in each repetition of the Genetic Process of Reproduction. Each new generation is more robust than the previous one, it contains more robust atoms of population, i.e. atoms that represent better Triangulations in terms of Delaunay Triangulation criteria. In the latest generation, we choose the best atom of this generation as the output of Delaunay_Genetic. From various executions of Delaunay_Genetic we have observed that the Triangulation yielded by Delaunay_Genetic, approaches to a very large extent (usually over 98% to 100%) the requested Delaunay Triangulation. In the future, we will focus towards improving several aspects of our approach, especially the execution time, utilizing various software and hardware improvement capabilities.
Υπολογισμός Τριγωνοποίησης Delaunay με χρήση Γενετικών Αλγορίθμων