44
συντεταγμένες του κέντρου του κελιού. Για τα γεγονότα εισόδου καταγράφονται και για τα
τρία γεγονότα του κελιού, οι συντεταγμένες του κελιού, η γωνία που προκύπτουν και το ύψος
τους. Τα γεγονότα εισόδου πραγματοποιούν την αποθήκευση των μετρήσεων στην δομή
δεδομένων. Επομένως, οποιαδήποτε μέτρηση απαιτείται για τον υπολογισμό των υπόλοιπων
γεγονότων εισάγεται μέσω των γεγονότων εισόδου. Για να υπολογιστεί το ύψος του κελιού ο
αλγόριθμος του Van Kreveld χρησιμοποιεί για όλα τα γεγονότα, το ύψος από το κέντρο του
κελιού, με αποτέλεσμα να υπάρχει απώλεια ακρίβειας, όταν η ημιευθεία δεν περνάει από το
κέντρο των κελιών. Για αυτό τον λόγο, στον παρών αλγόριθμο χρησιμοποιείται η τεχνική της
παρεμβολής. Με την τεχνική αυτή, το ύψος κάθε γεγονότος υπολογίζεται προσεγγιστικά, με
αποτέλεσμα για τα γεγονότα του ίδιου κελιού να καταγράφουν διαφορετικά ύψη. Για να
υπολογιστεί το ύψος στα γεγονότα εισόδου και εξόδου χρησιμοποιούνται τα τέσσερα γειτονικά
κελιά, όπως φαίνεται και στο
Σχήμα 27 Επιλογή των κελιών με κόκκινες κουκίδες για τον υπολογισμό του ύψους για το κάθε γεγονός με την
τεχνική της παρεμβολής
14
.
Όπως φαίνεται και παραπάνω η τεχνική της παρεμβολής χρησιμοποιείται για το γεγονός
εισόδου και το γεγονός εξόδου, καθώς τα γεγονότα κέντρου συμβαίνουν στο κέντρο κελιού το
ύψος του οποίου το DEM παρέχει την ακριβής τιμή. Τα κελιά που χρησιμοποιούνται για την
παρεμβολή είναι τα τέσσερα πιο κοντινά κέντρα κελιών στη θέση του γεγονότος εισόδου ή
εξόδου. Η επιλογή των κελιών που χρησιμοποιούνται αλλάζει ανάλογα με τη θέση του κελιού
σε σχέση με τη θέση του παρατηρητή, όπως περιγράφεται και στο κεφάλαιο 3.3.1.Ο τύπος που
χρησιμοποιείται για παρεμβολή τεσσάρων σημείων είναι ο παρακάτω, όπου h1, h2, h3, h4 τα
ύψη των γύρω κελιών και h το ύψος για το οποίο γίνεται η προσέγγιση:
ℎ =
ℎ1+ℎ2+ℎ3+ℎ4
4
(5)
14
Πηγή του σχήματος είναι η δημοσίευση [32]