19 

 

 

Ο  αλγόριθμος  R2  περιγράφτηκε  και  πάλι  από  τους  Franklin  κ.ά.  [22],  με  στόχο  να 

μειώσει  την  πολυπλοκότητα  του  αλγορίθμου  R3.  Για  να  πετύχει  καλύτερη  απόδοση  ο  R2 

μειώνει τις επαναλήψεις των υπολογισμών που συμβαίνουν στον R3. Για τον υπολογισμό της 

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

της  εικόνας.

 

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

πολλαπλοί υπολογισμοί για την ορατότητα των ίδιων κελιών για τα κελιά που βρίσκονται κοντά 

στον  παρατηρητή.  Ο  R2  έχει  καλή  ακρίβεια  και  είναι  πιο  γρήγορος  από  τον  R3,  αλλά  δεν 

πετυχαίνει μεγάλη βελτίωση στην ταχύτητα εκτέλεσης. 

 

Ο αλγόριθμος XDraw σχεδιάστηκε από τους Franklin κ.ά. [22] και αποτελεί έναν πιο 

αποδοτικό  αλγόριθμο  ανάλυσης  οπτικού  πεδίου.  Ο  αλγόριθμος  αυτός  υπολογίζει  τα  κελιά 

περιμετρικά από τον παρατηρητή σε τετράγωνα δαχτυλίδια. Για τον υπολογισμό των κελιών 

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

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

τους, υπολογίζονται από το μέσο όρο των υψών των πλησιέστερων κελιών. Το πρόβλημα που 

παρουσιάζεται στον XDraw αφορά σε πιθανά λάθη που δημιουργούνται κατά τον υπολογισμό 

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

εξωτερικού  δαχτυλιδιού,  προκαλώντας  απώλεια  ακρίβειας  στον  υπολογισμό  ορατότητας.  Ο 

αλγόριθμος αυτός είναι πιο γρήγορος από τον R2, αφού οι μετρήσεις του ύψους για κάθε κελί 

αποθηκεύονται  και  ξαναχρησιμοποιούνται  για  το  επόμενο  δαχτυλίδι,  αποφεύγοντας  τις 

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

 

O  αλγόριθμος  που  περιγράφηκε  από  τον  Van  Kreveld  παρέχει  γρήγορη  ταχύτητα 

εκτέλεσης με ευστοχία παρόμοια με αυτή του R3 [1]. Στον αλγόριθμο αυτό, όπως και για τον 

R3,  εξετάζεται  η  γραμμή  ορατότητας  για  κάθε  στοιχείο  της  εικόνας.  Ο  αλγόριθμος  αυτός 

διαφέρει  από  τον  R3,  αφού  εκμεταλλεύεται  την  σειρά  εκτέλεσης  των  γεγονότων,  ώστε  να 

αποφύγει τους περιττούς υπολογισμούς που γίνονται στους αλγορίθμους  R2 και R3. Για να  

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

υπολογιστούν  όλες  οι  γραμμές  ορατότητας  που  τα  περιέχουν.  Όταν  ολοκληρωθεί  ο 

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

αφαιρείται από τη δομή. Η δομή αυτή διατηρείται με εισαγωγές, όταν μια γραμμή ορατότητας 

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

παραλείπονται οι περιττοί υπολογισμοί που γίνονται στον αλγόριθμο R2, πετυχαίνοντας έτσι 

καλή απόδοση και υψηλή ακρίβεια, καθιστώντας τον αλγόριθμο του Van Kreveld έναν από 

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