35
Σε περίπτωση που δεν υπάρχει ορατότητα σε ένα κελί, είναι εφικτό να υπολογιστεί το ελάχιστο
ύψος του παρατηρητή, ώστε να έχει ορατότητα στο κελί που εξετάζεται. Τέλος, αξίζει να
σημειωθεί, ότι ο αλγόριθμος του Van Kreveld χρησιμοποιεί για τον υπολογισμό του ύψους των
κελιών, το ύψος από το κέντρο κάθε κελιού, ακόμα και όταν η LOS δεν περνά ακριβώς από το
κέντρο του κελιού [1]. Επομένως, μπορεί να επηρεαστεί η ακρίβεια του αλγορίθμου, ειδικά
όταν μελετάται raster με μεγάλα κελιά. Για να αντιμετωπιστεί ο περιορισμός αυτός, χρειάζεται
να τροποποιηθεί η μέθοδος που υπολογίζεται το ύψος του κάθε κελιού, ώστε να
διαφοροποιείται ανάλογα με το σημείο που τέμνεται το κάθε κελί, χρησιμοποιώντας την
τεχνική της παρεμβολής.
2.7.4 Αλγόριθμος XDraw
Ο Αλγόριθμος ΧDraw σχεδιάστηκε από τους Franklin κ.ά. [22], και πετυχαίνει
καλύτερη απόδοση από τους αλγορίθμους R2 και R3. Ο αλγόριθμος αυτός υπολογίζει την
ορατότητα των κελιών σε τετράγωνα δαχτυλίδια γύρω από τον παρατηρητή, αρχίζοντας από
πλησιέστερο δαχτυλίδι καταλήγοντας στα άκρα του DEM, και όπως φαίνεται στο παρακάτω
σχήμα (
).
13
Σχήμα 14 Απεικόνιση του αλγορίθμου XDraw για τον υπολογισμό του σημείου (5, 2) με την χρήση crossing
μεταξύ των σημείων (2, 1) και (3, 1).
Τα κελιά κάθε δαχτυλιδιού διατηρούν το μέγιστο ύψος της γραμμής ορατότητας που καταλήγει
σε αυτά. Επομένως, ο υπολογισμός της ορατότητας των κελιών κάθε νέου δαχτυλιδιού απαιτεί
την σύγκριση του ύψους του μόνο με το ύψος των κελιών του προηγούμενου δαχτυλιδιού. Με
την μέθοδο αυτή απαιτείται μόνο μια σύγκριση για κάθε κελί, ενώ ταυτόχρονα, αποφεύγονται
οι διπλότυποι υπολογισμοί που προκύπτουν στους αλγορίθμους R2 και R3. Στην περίπτωση
που η γραμμή ορατότητας ενός κελιού δεν περνά από το κέντρο του κελιού του προηγούμενου
13
Πηγή του σχήματος είναι η δημοσίευση [43]