70 

 

 

Ένα ακόμα πρόβλημα που δημιουργήθηκε αφορά το δυαδικό δέντρο που περιγράφει ο 

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

χρησιμοποιείται  ευρέως  για  την  δημιουργία  δέντρων.  Επομένως,  δημιουργήθηκε  για  τον 

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

έχει υλοποιηθεί και σε άλλες εργασίες [42] και κατάλληλες συναρτήσεις για τις περιστροφές 

που απαιτούνται μετά τις εισαγωγές και τις εξαγωγές κόμβων. Αποτέλεσμα ήταν, όχι μόνο να 

είναι  πιο  δύσχρηστη  η  χρήση  της  δομής  δεδομένων,  αφού  οποιαδήποτε  επεξεργασία  της 

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

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

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

εφαρμόστηκαν  στον  βασικό  αλγόριθμο  του  Van  Kreveld.  Ο  ρόλος  του  δέντρου  ήταν  να 

οργανωθούν  τα  ύψη  των  κελιών,  ώστε  με  μία  αναζήτηση  του  δέντρου  για  την  εύρεση  του 

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

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

σύγκριση  του  ύψους  του  κελιού  με  το  μέγιστο  ύψος  επέστρεφε  το  αποτέλεσμα  για  την 

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

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

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

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

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

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

αφού πραγματοποιηθεί λεπτομερής μέτρηση.

 

 

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

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

Όπως  φαίνεται  παραπάνω,  τα  κελιά  με  πορτοκαλί  χρώμα  έχουν  μέγιστο  ύψος  δυο,  ενώ  το 

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

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

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

ένα και όχι στο τρία, και επομένως δεν είναι ορατό. Άρα, για κάθε γραμμή ορατότητας είναι