Χωρικά Ερετήρια για το Inkscape

Περιγραφή

Το πρόγραμμα διαχείρισης διανυσματικών γραφικών 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 με μεγάλα αρχεία τα οποία δείχνουν τόσο την απόδοση όσο και την ορθότητα των ευρετηρίων.

Χρονοδιάγραμμα

Το έργο θα ξεκινήσει πριν την απόφαση της επιτροπής στα πλαίσια ενός ειδικού (εκτός του κύκλου σπουδών) μαθήματος του μεταπτυχιακού που παρακολουθώ. Συνολικός Χρόνος 3 μήνες.