background image

 

20 

 

 

Στους  παραπάνω  αλγόριθμους,  ο  υπολογισμός  του  ύψους  των  κελιών,  που  δεν 

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

ακρίβεια, όσο και την ταχύτητα τους.  Αυτό συμβαίνει καθώς το ύψος του κάθε  κελιού που 

παρέχει το υψομετρικό μοντέλο αφορά το κέντρο του κελιού. Ως αποτέλεσμα, όταν μια γραμμή 

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

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

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

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

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

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

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

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

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

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

 

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

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

βασίζεται  στην  χρήση  της  κάρτας  γραφικών  για  τους  υπολογισμούς  ορατότητας,  με 

αποτέλεσμα την επιτάχυνση της απόδοσης [23]. Μια άλλη παραλλαγή εφαρμόζει παράλληλη 

επεξεργασία χρησιμοποιώντας πολλούς επεξεργαστές, ώστε να αυξηθεί η επεξεργαστική ισχύς 

και  να  βελτιωθεί  η  ταχύτητα  του  αλγορίθμου  [24].  Οι  τεχνικές  αυτές  έχουν  ποικίλους 

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

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

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

Αντιθέτως, ο αλγόριθμος του Van Kreveld, λόγω της δομής του, είναι κατάλληλος μόνο για 

παραλληλοποίηση  με  την  χρήση  επεξεργαστών,  αφού  τα  γεγονότα  του  εξαρτώνται  από  την 

σειρά εκτέλεσης τους [25]. 

 

Υπάρχουν  αρκετές  διαφορετικές  προσεγγίσεις,  που  χρησιμοποιούν  τους  παραπάνω 

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

από  τις  προσεγγίσεις  αυτές,  και  διευκρινίζονται  οι  διαφορές  που  παρουσιάζουν.  Οι 

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

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

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