71 

 

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

μεγαλύτερο αυτού του κελιού που εξετάζεται. Για τους παραπάνω λόγους, το δυαδικό δέντρο 

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

εύρεση του κελιού. 

 

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

παράλληλο, καθώς τα γεγονότα του αλγόριθμου του  Van Kreveld εξαρτώνται από τη σειρά 

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

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

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

στις διεργασίες γινόταν σε δύο σημεία. Πριν την σάρωση χωριζόταν το DEM σε ίσα κομμάτια 

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

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

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

μεταξύ των διεργασιών σε δύο σημεία. Για να αντιμετωπιστεί αυτό το ζήτημα, δημιουργήθηκε 

η συνάρτηση που περιγράφεται στο κεφάλαιο 3.5.1. Η συνάρτηση αυτή διαχωρίζει τα κομμάτια 

της σάρωσης με βάση τις γωνίες τους, ώστε να μην χρειάζεται επικοινωνία των διεργασιών 

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

κομμάτια. 

 

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

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

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

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

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

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

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

εξόδου δεν θα βρεθεί το κελί στη λίστα ορατότητας και ο αλγόριθμος θα διακόψει τη λειτουργία 

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

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

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

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

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

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

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

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