This page briefly describes the project, funded by ELLAK, that focuses on the creation of spatial indexes for the 2D library lib2geom.
Το πρόγραμμα διαχείρισης διανυσματικών γραφικών Inkscape μαζί με το Scribus και το GIMP αποτελούν δημοφιλή εργαλεία ανοικτού λογισμικού στον χώρο της επεξεργασίας εικόνων/γραφικών και του desktop publishing. Από το Inkscape δημιουργήθηκε η βιβλιοθήκη lib2geom [1],[2] η οποία αναλαμβάνει την διαχείριση 2-διάστατων γεωμετρικών υπολογισμών και αλγορίθμων. Σκοπός της είναι να γίνει μια βιβλιοθήκη γενικής χρήσης η οποία θα χρησιμοποιείται, όχι μόνο από τις κοινότητες των Inkscape και Scribus, αλλά από την ευρύτερη κοινότητα του ανοικτού λογισμικού.
Το έργο αφορά την υλοποίηση χωρικών ευρετηρίων 2 διαστάσεων για την βιβλιοθήκη lib2geom ώστε να είναι δυνατή η διαχείριση αρχείων με μεγάλο πλήθος σημείων πχ (πολύπλοκα διανυσματικά γραφικά με πολλούς κόμβους, διαγράμματα VLSI, χάρτες, αρχιτεκτονικά διαγράμματα κτλ).
Προς το τέλος του 2008 ήρθα σε επαφή με την ομάδα υλοποίησης της lib2geom και εκδήλωσα ενδιαφέρον για ένα σημείο της λίστας TODO, την δημιουργία χωρικών ευρετηρίων 2 διαστάσεων. Τα ευρετήρια που θα δημιουργηθούν θα είναι βασισμένα στα R-Trees. Ένα από τα ιδρυτικά μέλη του Inkscape και συν-διαχειριστής της lib2geom, o Nathan Hurst, εκδήλωσε ενδιαφέρον να επιβλέψει (mentoring) την προσπάθεια αυτή [5]. Η επίβλεψη του μπορεί να επιταχύνει και να διευκολύνει την διαδικασία υλοποίησης καθώς έχει πολύ καλή γνώση της δομής και του κώδικα της lib2geom. Επιπλέον, η υλοποίηση αυτή θα είναι το αντικείμενο ενός ειδικού μαθήματος στο μεταπτυχιακό που παρακολουθώ στο DTU (το μάθημα αυτό είναι εκτός του προγράμματος σπουδών).
Στόχος του έργου δεν είναι η έρευνα πάνω σε ένα νέο είδος ευρετηρίου αλλά η χρήση κάποιων από τα ήδη υπάρχοντα της σχετικής βιβλιογραφίας. * Εύρεση των κατάλληλων προς υλοποίηση R-Trees. * Υλοποίηση ενιαίου interface για την διαχείριση χωρικών ευρετηρίων. * Υλοποίηση ενός ψευδο-ευρετηρίου (ένα απλό array σημείων) για λόγους testing. * Υλοποίηση 2 χωρικών ευρετηρίων παραλλαγών του R-Tree. Περιλαμβάνουν τις εξής ενέργειες: - προσθήκη στοιχείου (O(log)) - διαγραφή στοιχείου (O(log)) - ανανέωση στοιχείου (O(log)) - εύρεση στοιχείου σε συγκεκριμένο εύρος - (προαιρετικά) εύρεση στοιχείου σε κατεύθυνση * Test cases που δείχνουν: - οτι στο ευρετήριο εισάγονται, διαγράφονται και ανανεώνονται στοιχεία με σωστό τρόπο. - την απόδοση του ευρετηρίου
* Κώδικας σε C++ που υλοποιεί τους παραπάνω στόχους. * Ο κώδικας θα διανέμεται μαζί με την lib2geom, η οποία διανέμεται υπό την άδεια LGPL 2.1. Αυτή την στιγμή υπάρχουν πακέτα για Ubuntu και Debian. * Τεκμηρίωση μέσα στον κώδικα. * Test cases με μεγάλα αρχεία τα οποία δείχνουν τόσο την απόδοση όσο και την ορθότητα των ευρετηρίων.
[1] http://lib2geom.sourceforge.net/ [2] http://wiki.inkscape.org/wiki/index.php/Lib2geom_FAQ [3] http://www.rtreeportal.org/ [4] R-Trees: Theory and Applications, Springer, ISBN 1852339772