48 

 

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

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

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

πρέπει να παραληφθεί από τη λίστα σάρωσης πριν αρχίσει η εκτέλεση των γεγονότων. Τέλος, 

αξίζει  να  σημειωθεί  ότι  για  λόγους  σαφήνειας  αντί  για  μια  δισδιάστατη  λίστα  ορατότητας 

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

(απόσταση, γωνία, υψόμετρο). Όλες οι λίστες ταξινομούνται με βάση την απόσταση από τον 

παρατηρητή. 

 

3.4.2 Δυαδική αναζήτηση 

 

Η  αναζήτηση  αποτελεί  αναπόσπαστο  κομμάτι  της  ανάλυσης  οπτικού  πεδίου,  καθώς 

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

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

σημαντικά  τη  σειριακή  αναζήτηση.  Η  απόδοση  της  δυαδικής  αναζήτησης  είναι  σαφώς 

καλύτερη,  αφού  παρουσιάζει  πολυπλοκότητα  O(logn)  σε  σχέση  με  τη  σειριακή  που 

παρουσιάζει  O(n).  Ακόμα  και  στη  χειρότερη  περίπτωση  της,  για  μια  λίστα  n  στοιχείων  η 

δυαδική αναζήτηση χρειάζεται n/2+1 επαναλήψεις, όταν στην ανάλογη περίπτωση η σειριακή 

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

Σημαντική  προϋπόθεση  για  την  εφαρμογή  της  δυαδικής  αναζήτησης  είναι  να  είναι 

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

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

στοιχείου  στη  λίστα.  Αρχικά,  συγκρίνεται  το  στοιχείο  που  βρίσκεται  στη  μεσαία  θέση  της 

λίστας με το στοιχείο που αναζητείται και στη συνέχεια: 



 

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

επιστρέφει την θέση στην οποία βρίσκεται το στοιχείο. 



 

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

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

κομματιού της λίστας.  



 

Αν  το  στοιχείο  είναι  μεγαλύτερο  από  αυτό  που  αναζητείται,  τότε  ο  αλγόριθμος 

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

κομματιού της λίστας.