Η παρούσα διπλωματική εργασία εστιάζει σε αλγόριθμους εύρεσης της τομής ευθειών και διερευνά τη δυνατότητα βελτίωσης τους μέσω εξελικτικών διαδικασιών, εστιάζοντας στους γενετικούς αλγορίθμους (Γ.Α.). Οι αλγόριθμοι εύρεσης της τομής ευθειών αποτελούν αναπόσπαστο κομμάτι της υπολογιστική γεωμετρίας και έχουν σημαντική εφαρμογή σε Συστήματα Γεωγραφικών Πληροφοριών (GIS) κατά την υλοποίηση διαφόρων εργαλείων ανάλυσης γεω-χωρικών δεδομένων. Η υπέρθεση πολλαπλών χαρτών είναι μια από τις σημαντικότερες λειτουργίες ενός GIS και βασίζεται στην εύρεση της τομής διανυσματικών αντικειμένων. Αν και υπάρχουν αρκετά αποδοτικοί αλγόριθμοι, η απόδοση τους για μεγάλο όγκο δεδομένων είναι χαμηλή και κρίνεται αναγκαία η αναζήτηση εναλλακτικών προσεγγίσεων βασισμένες σε νέες μεθοδολογίες.
Αρχικά μελετήθηκε εκτενώς η βιβλιογραφία σχετικά με τους υπάρχοντες αλγόριθμους εύρεσης τομής ευθειών καθώς και τους εξελικτικούς αλγορίθμους και επιλέχθηκαν οι γενετικοί αλγόριθμοι ως οι καταλληλότεροι για την αποδοτική επίλυση του συγκεκριμένου προβλήματος. Οι γενετικοί αλγόριθμοι, βασιζόμενοι στις διαδικασίες της φυσικής εξέλιξης (επιλογή, διασταύρωση, μετάλλαξη) καταφέρνουν να προσεγγίσουν τη βέλτιστη λύση σε πολύπλοκα προβλήματα για τα οποία μια απόλυτη λύση δεν είναι εφικτή σε λογικό χρόνο, καθιστώντας τους ιδανικούς για την επίλυση του προβλήματος εύρεσης τομών ευθυγράμμων τμημάτων.
Κατόπιν υλοποιήθηκε ο προτεινόμενος Γ.Α., σε γλώσσα προγραμματισμού Python, βασιζόμενος σε μια αντικειμενική συνάρτηση η οποία προσπαθεί να ελαττώσει τις αποστάσεις ανάμεσα σε ζεύγη ευθύγραμμων τμημάτων τα οποία δύνανται να είναι τεμνόμενα. Μέσω των διαδικασιών της επιλογής και μετάλλαξης, που επαναλαμβάνονται, ο αλγόριθμος καταφέρνει να υπολογίσει τις τομές με επιτυχία.
Ο γενετικός αλγόριθμος συγκρίθηκε με έναν παραδοσιακό αλγόριθμο σάρωσης ευθείας για πλήθος διαφορετικών περιπτώσεων. Η απόδοση του Γ.Α. φαίνεται να είναι 1-2 τάξεις μεγέθους χειρότερη από τον παραδοσιακό αλγόριθμο, αλλά ο Γ.Α. φαίνεται να είναι ταχύτερος όταν ο αριθμός των τομών είναι ιδιαίτερα μεγάλος.
This Master Thesis focuses on linear segment intersection algorithms and investigates the possibility of improving them, through evolutionary algorithms, in particular using genetic algorithms. Line segment intersection algorithms are an essential part of Computational Geometry and play a key role in Geographic information Systems (GIS) operations (e.g., vector layer overlay). Existing algorithms are well optimized, but when there is a need to analyze big datasets their performance is moderately low, and as a result the design of new, improved algorithms, based on A.I. techniques, is an important task.
Firstly, we examined in depth the current literature regarding line segment intersection algorithms, in addition to evolutionary algorithms. Genetic algorithms were selected to solve this problem, based on the fact that they can calculate, an almost optimal solution, for a large variety of problems, in relatively low time.
The genetic algorithm was implemented in Python, and uses a fitness function, at its core, that minimizes distances between pairs of line segments, that have the possibility of intersection. Through a repetitive application of selection and mutation operations, the genetic algorithm identifies successfully all the intersections, for a given set of line segments.
Finally, we compare the genetic algorithm with a traditional sweep line algorithm for a variety of different scenarios. The genetic algorithm seems to be 1-2 orders of magnitude slower in most cases, but when the number of intersections are very high, and we only need an approximate solution, the genetic algorithm seems to outperform the sweep line algorithm quite significantly.
Εξελικτικοί Αλγόριθμοι Υπολογισμού Τεμνόμενων Ευθειών σε Συστήματα Γεωγραφικών Πληροφοριών (G.I.S)