45 

 

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

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

(

 γωνία

γεγονότος

)  με  συντεταγμένες  (x1,y1)  σε  σχέση  με  το  κελί  του  παρατηρητή  με 

συντεταγμένες (x0,y0) υπολογίζεται από τον τύπο: 

 Γωνία

γεγονότος

= tan (

y1−y0
x1−x0

)  

(6) 

Στον  παραπάνω  τύπο  η  εξίσωση  της  εφαπτομένης  επιστρέφει  τιμές  από  π  έως  –π,  με 

αποτέλεσμα  να  απαιτείται  μετατροπή  για  γωνίες  μεγαλύτερες  των  π  rad,  αφού  τα  γεγονότα 

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

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

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

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

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

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

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

παρατηρητή.  Στην  περίπτωση  αυτή  εκτελούνται  πρώτα  τα  γεγονότα  που  βρίσκονται 

πλησιέστερα στον παρατηρητή και στη συνέχεια τα πιο απομακρυσμένα. 

 

3.4 Έλεγχος ορατότητας 

Για τον έλεγχο της ορατότητας των κελιών εφαρμόζεται η μεθοδολογία του αλγορίθμου 

του Van Kreveld με κάποιες παραλλαγές με στόχο να βελτιωθεί η ακρίβεια του αλγορίθμου. 

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

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

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

λίστα  ορατότητας.  Η  λίστα  ορατότητας  ενημερώνεται  με  εισαγωγές  και  εξαγωγές,  όταν 

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

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

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

τους αλγορίθμους που R2 και R3, καθώς οι μετρήσεις κάθε κελιού δεν επαναλαμβάνονται για 

κάθε LOS που το τέμνει. Κατά συνέπεια, οι μετρήσεις για του κελί παραμένουν διαθέσιμες στη 

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