background image

 

34 

 

Όπως  απεικονίζεται  και  παραπάνω,  η  ημιευθεία  κινείται  αντίστροφα  από  τους  δείκτες  του 

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

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

αποθηκεύονται  σε  ένα  ισορροπημένο  δυαδικό  δέντρο  με  κριτήριο  την  απόσταση  του  κάθε 

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

περιέχονται στα αριστερά φύλλα. Επιπλέον, για κάθε υποδέντρο αποθηκεύεται στο κόμβο του 

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

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

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

κόμβος, όπως φαίνεται και στο παρακάτω 

Σχήμα 13

. 

 

Σχήμα 13 Παράδειγμα εισαγωγής των σημείων της γραμμής ορατότητας σε δυαδικό δέντρο με βάση την 

απόσταση από τον παρατηρητή

12

 Στο δέντρο γίνονται εισαγωγές και εξαγωγές όταν συμβαίνει κάποιο γεγονός για το κελί που 

εξετάζεται. Για κάθε κελί υπάρχουν τριών ειδών γεγονότα: 

 

Τα γεγονότα εισόδου που συμβαίνουν όταν η ημιευθεία συναντάει για πρώτη φορά ένα 

κελί: τότε προστίθεται στο δέντρο το κελί με την τιμή της κλίσης του.  

 

Τα γεγονότα εξόδου που συμβαίνουν όταν η ημιευθεία δεν τέμνει πλέον ένα κελί: τότε 

αφαιρείται το κελί από το δέντρο. 

 

Τα  γεγονότα  κέντρου  που  συμβαίνουν  όταν  η  ημιευθεία  περνά  από  το  κέντρο  ενός 

κελιού. Σε αυτή την περίπτωση, πραγματοποιείται δυαδική αναζήτηση για το κελί στο 

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

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

υπάρχει ορατότητα στο κελί. 

                                                 

 

12

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