ΓΙΑ ΕΝΗΜΕΡΩΣΗ ΚΑΙ ΣΧΟΛΙΑΣΜΟ.
---------- Forwarded message ----------
From: Vangelis Katsikaros <vkatsikaros [ at ] yahoo [ dot ] gr>
Date: 2009/2/15
Subject: Διαγωνισμός ανάπτυξης ΕΛ/ΛΑΚ
To: info [ at ] ellak [ dot ] gr
Cc: Nathan Hurst <"njh"@njhurst.com>
===========================================================================
Υλοποίηση χωρικών ευρετηρίων 2 διαστάσεων για την βιβλιοθήκη lib2geom
(Inkscape & Scribus)
Ομάδα Υλοποίησης:
Κατσικάρος Ευάγγελος
Nathan Hurst (mentoring)
===========================================================================
Περιγραφή
------------------------------------
Το πρόγραμμα διαχείρισης διανυσματικών γραφικών 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 (το μάθημα
αυτό είναι εκτός του προγράμματος σπουδών).
Στόχοι
------------------------------------
Στόχος του έργου δεν είναι η έρευνα πάνω σε ένα νέο είδος ευρετηρίου
αλλά η χρήση κάποιων από τα ήδη υπάρχοντα της σχετικής βιβλιογραφίας
[3], [4].
* Εύρεση των κατάλληλων προς υλοποίηση 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 με μεγάλα αρχεία τα οποία δείχνουν τόσο την απόδοση όσο και
την ορθότητα των ευρετηρίων.
Χρονοδιάγραμμα
------------------------------------
Το έργο θα ξεκινήσει πριν την απόφαση της επιτροπής στα πλαίσια ενός
ειδικού (εκτός του κύκλου σπουδών) μαθήματος του μεταπτυχιακού που
παρακολουθώ.
- 16 Φεβ: επιλογή δένδρων προς υλοποίηση / πειραματισμοί με την lib2geom
- 23 Φεβ: εκκίνηση υλοποίησης interface
- 02 Μαρ: οριστικοποίηση interface
- 30 Μαρ: υλοποίηση 1ου ευρετηρίου
- 06 Μαρ: υλοποίηση test cases.
- 13 Απρ: υλοποίηση 2ου ευρετηρίου
- 20 Απρ: υλοποίηση test cases.
- 15 Μαΐ: παράδοση έργου.
Συνολικός Χρόνος 3 μήνες.
Χρονοδιάγραμμα
------------------------------------
Κόστος υλοποίησης: 4000 ευρώ.
Βιογραφικά Σημειώματα Ομάδας
------------------------------------
Κατσικάρος Ευάγγελος: αποφοίτησα από το τμήμα Πληροφορικής του
Πανεπιστημίου Πειραιά (Πα.Πει.) (2008) και παρακολουθώ μεταπτυχιακές
σπουδές στο τμήμα Πληροφορικής του Technical University of Denmark
(DTU). Έχω συνεργαστεί στα πλαίσια του Google Summer of Code 2007 με
την MySQL και έχω συμμετάσχει στην εθελοντική ελληνοποίηση και
μετάφραση εγχειρίδιων χρήσης GUI clients. Είμαι υποστηρικτής της
Κοινότητας Ανάπτυξης Ελεύθερου Λογισμικού του Πανεπιστημίου Πειραιά
και καθημερινός χρήστης λειτουργικού συστήματος και λογισμικού
ανοικτού κώδικα.
Nathan Hurst (mentoring): My background is a degree in pure mathematics
and a phd in optimisation algorithms for automated document layout. I'm
currently working for Adobe Systems, Inc in the research labs on
automatic layout and visualisation. Range queries are a common building
block in my research area.
Αναφορές
------------------------------------
[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
[5] Attached email.
Στοιχεία επικοινωνίας
------------------------------------
Κατσικάρος Ευάγγελος: ΑΦΜ 102004060, Ιάσωνος 21, 18537 Πειραιάς, τηλ.
210 4511603.
Yes, this is fine!
njh
On Mon, 9 Feb 2009, Vangelis Katsikaros wrote:
> Hello Nathan
>
> Below I have a modified version of the mail you sent to Francois, which
> we can use for the ELLAK implementation contest (the small greek "summer
> of code" I mentioned). You can change what you want and send it to me
> with a title like the one you sent to Francois "ELLAK implementation
> contest: mentoring/support for Evangelos Katsikaros from 2geom project"
>
> In the application you are mentioned as a team member but I clearly
> state that you will be mentoring the project. When I 'll send the
> application, I will Cc you too (but the application will be in Greek).
> The application must include small CVs of the team members, so I could
> use the last paragraph of the mail for yours. I will keep your CV in
> English.
>
> Of course, if the project gets funded then you will have a share like
> the google summer of code mentors get. If not, then we will have the joy
> and fun of working together :) (which is important anyway!)
>
>
> =======================================================
>
> I'm a developer for Inkscape and for the 2geom geometric tools library
> (used in projects such as inkscape and scribus). I was approached by
> Evangelos Katsikaros regarding the implementation of various range query
> data structures. This project would be a 'study project', part of his
> studies at DTU, and also submitted to the ELLAK open-source
> implementation contest.
>
> I'm offering to provide the 2geom project side mentoring for him,
> helping to get into the code base. In return I'm hoping to learn about
> range query databases such as R-trees, a topic I'm interested in but
> have never had the time to study in detail.
>
> My background is a degree in pure mathematics and a phd in optimisation
> algorithms for automated document layout. I'm currently working for
> Adobe Systems, Inc in the research labs on automatic layout and
> visualisation. Range queries are a common building block in my research
> area.
>
> =======================================================
>
> Regards
> Vangelis
> __________________________________________________
> ×ñçóéìïðïéåßôå Yahoo!;
> ÂáñåèÞêáôå ôá åíï÷ëçôéêÜ ìçíýìáôá (spam); Ôï Yahoo! Mail äéáèÝôåé ôçí êáëýôåñç äõíáôÞ ðñïóôáóßá êáôÜ ôùí åíï÷ëçôéêþí ìçíõìÜôùí http://mail.yahoo.gr
--
Πριν εκτυπώσετε αυτό το μήνυμα, σκεφθείτε το περιβάλλον! Ένα χαρτί
λιγότερο! - http://karounos.gr/blog/