Page 49

Σχήμα 31 Εφαρμογή δυαδικής αναζήτησης, με στόχο το γράμμα G

Η δυαδική αναζήτηση εφαρμόζεται στην λίστα ορατότητας που περιέχει την απόσταση από τον

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

αναζήτηση ιδανική για την περίπτωση.

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

πετυχαίνει το ίδιο αποτέλεσμα με την αναζήτηση σε ένα δυαδικό δέντρο τόσο στην

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

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

Kreveld.

3.4.3 Υπολογισμός γεγονότων

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

πραγματοποιούνται ενέργειες ανάλογα με τον τύπο του γεγονότος. Για τα γεγονότα εισόδου

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

χρησιμοποιώντας τη μέτρηση της απόστασης από τον παρατηρητή. Για να γίνει ο εντοπισμός

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

χρησιμοποιείται η αναζήτηση τερματίζεται όταν δεν υπάρχει στοιχειό που να την ικανοποιεί

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

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

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

αποτέλεσμα να τηρείται η ταξινόμηση της λίστας.

Για τα γεγονότα εξόδου εντοπίζεται η θέση στην οποία πρέπει να γίνει η εξαγωγή του

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

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

στοιχεία της θέσης αυτής από όλες τις λίστες.

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

Η επίσκεψη έγινε στις 11/5/2020