33 

 

 

Σχήμα 11 Παράδειγμα υπολογισμού του ύψους για τον αλγόριθμο R2 με την χρήση crossings για τις γραμμές 

ορατότητας Α και Β

10

. 

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

πραγματοποιείται  όταν  συμβαίνει  x-crossing  ή  y-crossing  και  υπολογίζεται  με  βάση  την 

απόσταση από το κοντινότερο κελί. Όπως φαίνεται στο 

Σχήμα 11

, για την γραμμή ορατότητας 

Α το x-crossing στο σημείο που απέχει dA από το C το ύψος θα έχει to ύψος του σημείου C, 

επειδή είναι το πλησιέστερο σημείο στο crossing.

 

Αυτός ο τρόπος υπολογισμού βελτιώνει τη 

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

προσεγγιστικός.  Η ακρίβεια του αλγορίθμου  μπορεί να βελτιωθεί τροποποιώντας  τον τρόπο 

υπολογισμού των crossings. 

 

2.7.3 Αλγόριθμος Van Kreveld 

 

Ο  αλγόριθμος  ανάλυσης  οπτικού  πεδίου  που  προτάθηκε  από  τον  Van  Kreveld  [1], 

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

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

του DEM. Η ημιευθεία περιστρέφεται κατά 360 μοίρες, ώσπου να περάσει πάνω από τα κελιά 

που  εξετάζονται.  Όταν  η  ημιευθεία  περνά  πάνω  από  το  κέντρο  του  κάθε  κελιού,  γίνεται  ο 

υπολογισμός της ορατότητας του κελιού.  

 

Σχήμα 12 Απεικόνιση της γραμμής ορατότητας που περιστρέφεται γύρω από τον παρατηρητή και πραγματοποιεί 

τη σάρωση των κελιών στον αλγόριθμο του Van Kreveld

11

. 

                                                 

10

 Πηγή του σχήματος  είναι η δημοσίευση [43] 

11

 Πηγή του σχήματος είναι η δημοσίευση [1]