33
Σχήμα 11 Παράδειγμα υπολογισμού του ύψους για τον αλγόριθμο R2 με την χρήση crossings για τις γραμμές
ορατότητας Α και Β
10
.
Ο υπολογισμός του ύψους, για κάθε κελί που η γραμμή ορατότητας δεν τέμνει στο κέντρο του,
πραγματοποιείται όταν συμβαίνει x-crossing ή y-crossing και υπολογίζεται με βάση την
απόσταση από το κοντινότερο κελί. Όπως φαίνεται στο
, για την γραμμή ορατότητας
Α το 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]