background image

 

32 

 

 

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

crossings και δεξιά τα και y crossings

9

Όπως  φαίνεται  και  στο 

Σχήμα  10

,  αν  το  κελί  τέμνεται  στις  περιοχές  I,  IV,  V  ή  VIII  τότε 

χρησιμοποιείται η τιμή του x-crossing, όπως φαίνεται δεξιά στο 

Σχήμα 10

, ενώ για τις υπόλοιπες 

περιοχές η τιμή του y-crossing. Η τιμή για το x-crossing ή y-crossing προσεγγίζεται από το 

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

Επομένως, ο R3 είναι ο μοναδικός αλγόριθμος που δίνει αποτελέσματα ακριβείας, οι υπόλοιποι 

αλγόριθμοι που ακολουθούν είναι προσεγγιστικοί. 

 

2.7.2 Αλγόριθμος R2 

 

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

μειώσει την πολυπλοκότητα του αλγορίθμου R3. Ο R2 δεν υπολογίζει την γραμμή ορατότητας 

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

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

Σχήμα 

11

για  τις  γραμμές  ορατότητας  που  τελειώνουν  στα  σημεία  Α  και  Β.  Με  αυτό  τον  τρόπο,  ο 

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

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

                                                 

9

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