39 

 

Κεφάλαιο 3 

Υλοποίηση του λογισμικού μέρους 

 

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

υλοποίηση του αλγορίθμου και αναλύεται κάθε κομμάτι του λογισμικού. 

 

3.1 Γενική επισκόπηση του λογισμικού 

 

Ο αλγόριθμος που χρησιμοποιείται έχει ως βάση τον αλγόριθμο του Van Kreveld [1], ο 

οποίος αποτελείται από δυο βασικά στάδια. Στο πρώτο στάδιο πραγματοποιείται η σάρωση του 

DEM [31], που δίνεται σαν αρχείο εισόδου του αλγορίθμου. Για την υλοποίηση της σάρωσης 

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

άκρα  του  DEM.  Η  ημιευθεία  ακολουθεί  φορά  αντίστροφη  από  αυτή  του  ρολογιού  και 

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

αφετηρίας της.

 

Κατά την σάρωση καταγράφονται οι μετρήσεις των τριών ειδών γεγονότων που 

συμβαίνουν  για  το  κάθε  κελί.  Τα  είδη  των  γεγονότων  του  κάθε  κελιού  είναι  τα  γεγονότα 

εισόδου, κέντρου, και εξόδου, που συμβαίνουν αντίστοιχα στο σημείο που τέμνει για πρώτη 

φορά η ημιευθεία το κελί, στο κέντρο του κελιού, και όταν η ημιευθεία σταματά να τέμνει το 

κελί. Οι μετρήσεις που καταγράφονται για το κάθε γεγονός είναι η απόσταση του σημείου που 

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

στο σημείο  που συμβαίνει το γεγονός και η  κλίση του ύψους από τον παρατηρητή προς το 

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

του  γεγονότος  με  τις  αντίστοιχες  μετρήσεις  του.  Η  λίστα  ονομάζεται  λίστα  σάρωσης  και 

ταξινομείται  με  βάση  την  γωνία,  κατά  την  οποία  συμβαίνει  το  κάθε  γεγονός.  Η  σάρωση 

προηγείται του υπολογισμού ορατότητας, αφού απαιτείται ταξινόμηση της λίστας, σύμφωνα 

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

 

 

Στο δεύτερο στάδιο γίνεται ο υπολογισμός της ορατότητας για το κάθε κελί. Κατά τον 

υπολογισμό της ορατότητας

 

χρησιμοποιείται η λίστα σάρωσης,

 

από την οποία διαβάζονται με 

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

συναντάται. Με τον τρόπο  αυτό δημιουργείται μια νέα λίστα,  η λίστα ορατότητας. Η λίστα 

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

βρίσκονται  στην  ημιευθεία  για  κάθε  γωνία  της  περιστροφής  της.  Εισαγωγές  και  εξαγωγές 

γίνονται όταν συμβαίνει γεγονός εισόδου και εξόδου,  αντίστοιχα.  Η ορατότητα για το κάθε