background image

 

69 

 

4.2 Προβλήματα που αντιμετωπίστηκαν κατά την υλοποίηση 

 

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

υπήρξαν  προβλήματα  που  δυσκόλεψαν  την  πρόοδο  της  εργασίας.  Καθώς  η  εργασία 

αποτελείται  μόνο  από  λογισμικό  τα  προβλήματα  που  προέκυψαν  δεν  αποτελούσαν  εμπόδια 

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

Παρακάτω αναλύονται τα προβλήματα και ο τρόπος που αντιμετωπίστηκαν. 

 

Ένα  από  τα  πρώτα  προβλήματα  που  προέκυψε  αφορούσε  την  περιστροφή  της 

ημιευθείας που περιγράφεται από τον αλγόριθμο του Van Kreveld. Η ημιευθεία περιστρέφεται 

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

γεγονότα του κελιού. Στην αρχική μορφή του κώδικα η περιστροφή πραγματοποιούνταν από 

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

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

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

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

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

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

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

να καλύψει τα πιο απομακρυσμένα κελιά. 

 

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

στον παρατηρητή τέμνονται πολλαπλές φόρες ενώ τα πιο απομακρυσμένα μόνο μια φορά. 

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

Σχήμα 47

, το κελί B, επειδή είναι πιο κοντά στον παρατηρητή, τέμνεται 

από την ημιευθεία και στα τέσσερα βήματα του βρόχου ενώ το κελί Α τέμνεται μόνο από τα 

βήματα 2-4. Κατά συνέπεια, αυξάνονται οι επαναλήψεις του βρόχου, ενώ ταυτόχρονα για τα 

κελιά κοντά στο παρατηρητή επαναλαμβάνονται περιττές μετρήσεις.  Η λύση στο πρόβλημα 

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

κεφάλαιο  3.3.  Στον  παρών  αλγόριθμο  υπολογίζονται  η  γωνία,  στην  οποία  συμβαίνουν  τα 

γεγονότα για το κάθε κελί και στη συνέχεια τα γεγονότα ταξινομούνται κατά γωνία, ώστε να 

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