22 

 

είναι διαθέσιμη στον υπολογιστή, και διαχωρίζεται ο υπολογισμός ορατότητας σε κομμάτια 

που  μπορούν  να  χωρέσουν  στην  μνήμη  του.  Ο  αλγόριθμος  αυτός  αποτελεί  τη  βάση  του 

αλγόριθμου που εκτελείται στο Geographic Resources Analysis Support System (GRASS), το 

οποίο αποτελεί μια πλατφόρμα λογισμικού που αναλύει γεωχωρικά δεδομένα. Ο αλγόριθμος 

που είναι διαθέσιμος στο GRASS περιλαμβάνει, επιπλέον, πιο ακριβή υπολογισμό του ύψους 

των  κελιών  με  την  χρήση  της  τεχνικής  της  παρεμβολής.  Ο  αλγόριθμος  αυτός  είναι,  τόσο 

ακριβής,  όσο  και  γρήγορος,  αλλά  δεν  εφαρμόζει  τεχνικές  παραλληλοποίησης,  οι  οποίες  θα 

μπορούσαν να βελτιώσουν περαιτέρω το χρόνο εκτέλεσης του.

 

 

1.3 Κίνητρα και Στόχοι Υλοποίησης 

 

Η ανάλυση οπτικού πεδίου παρέχει απαραίτητες υπηρεσίες σε πολλές εφαρμογές που 

αφορούν  τόσο  στην  καθημερινότητα,  όσο  και  σε  έργα  κοινής  ωφέλειας.  Για  αυτό  τον  λόγο 

περιγράφονται  σε  αρκετές  δημοσιεύσεις  αλγόριθμοι  που  πραγματοποιούν  ανάλυση  οπτικού 

πεδίου. Ενώ όμως υπάρχουν πολλοί μέθοδοι υλοποίησης, δεν υπάρχει ανάλογη διαθεσιμότητα 

ελεύθερου  κώδικα,  ειδικά  για  αλγορίθμους  που  εφαρμόζουν  τεχνικές  παράλληλης 

επεξεργασίας.  Επομένως,  πρωταρχικό  κίνητρο  της  εργασίας  είναι  η  δημιουργία  ενός 

λογισμικού ανοιχτού κώδικα που θα διευκολύνει την περαιτέρω βελτίωση του αλγορίθμου, ενώ 

ταυτόχρονα θα επιτρέπει ελεύθερη χρήση του για οποιαδήποτε εφαρμογή. 

 

Ο στόχος του αλγόριθμου που δημιουργήθηκε είναι να συνδυάσει υψηλή ακρίβεια και 

γρήγορο  χρόνο  εκτέλεσης.  Για  την  επίτευξη  της  επιτάχυνσης  του  χρόνου  εκτέλεσης,  ο 

αλγόριθμος  εφαρμόζει  παραλληλοποίηση  με  την  χρήση  της  Διεπαφής  Μεταβίβασης 

Μηνυμάτων (Message Passing Interface - MPI) [28], η οποία ανήκει στην παραλληλοποίηση 

με  την  χρήση  πολλαπλών  επεξεργαστών.  Ο  αλγόριθμος  που  επιλέχτηκε  είναι  αυτός  που 

προτάθηκε από τον Van Kreveld, αφού παρέχει γρήγορο χρόνο εκτέλεσης και η δομή του είναι 

συμβατή  με  την  τεχνική  αυτή.  Επιπρόσθετα,  στον  αλγόριθμο  εφαρμόζεται  η  τεχνική  της 

παρεμβολής για τον υπολογισμό των κελιών όταν δεν τέμνονται από τη γραμμή ορατότητα στο 

κέντρο τους, βελτιώνοντας έτσι σημαντικά την ακρίβεια του αλγορίθμου. Για την εφαρμογή 

και των δυο τεχνικών απαιτούνται τροποποιήσεις στον αλγόριθμο του Van Kreveld, οι οποίες 

τον διαχωρίζουν από τα έργα που έχουν ήδη υλοποιηθεί.  Οι τροποποιήσεις αυτές  αλλάζουν 

δραστικά την δομή του αλγορίθμου, ώστε να γίνει εφικτή η εφαρμογή τον παραλλαγών αυτών. 

Ο  ακριβής  τρόπος  λειτουργίας  του  αλγορίθμου  και  των  παραλλαγών  του  περιγράφονται 

λεπτομερώς στο κεφάλαιο 3.