Ρομπότ στην CGAL

Δίνονται Ν πολύγωνα που θεωρούνται εμπόδια στην κίνηση σημειακού ρομπότ στο επίπεδο: χρησιμοποιήστε τις ρουτίνες της CGAL για να αναπαραστήσετε τον ελευθερο χώρο ώστε, όταν δίδονται 2 σημεία στο επίπεδο, το πρόγραμμά σας να αποφασίζει αν είναι δυνατή η κίνηση από το ένα στο άλλο ή όχι δηλ. αν υπάρχει μονοπάτι που συνδέει τα 2 σημεία χωρίς να τέμνει το εσωτερικό των εμποδίων.

Συγκεκριμένα, η Αναπαράσταση του ελεύθερου χώρου γινεται με 2 τρόπους (διαλέξτε έναν):
(1) Υπολογήσετε μια διαμέριση του ελεύθερου χώρου (π.χ. μέσω υποδιαίρεσης σε τρίγωνα ή τραπέζια). Κατασκευάστε τον γράφο των τριγώνων / τραπεζίων.
(2) Παράγετε τυχαία σημεία σε ολο τον χώρο, κρατάτε μονο αυτά που δεν ανήκουν σε εμπόδια και τα συνδέετε με λιγα κοντινά τους σημεία τετοια ώστε η κινηση προς αυτά να ειναι εφικτή: κατασκευάζετε γράφο που συνδέει τα σημεία μεταξυ των οποίων η κίνηση είναι εφικτή.

Κίνηση ρομπότ:
(1) Εντοπίζετε το τρίγωνο / τραπέζιο της αρχικής και της τελικής θέσης του ρομποτ, αναζητάτε μονοπάτι στον γράφο των τριγώνων / τραπεζίων που συνδέει την αρχική και τελικη θέση.
(2) Συνδέετε την αρχική και τελική θέση με ενα κοντινό τους σημείο τέτοιο ωστε η κινηση προς αυτό να ειναι εφικτή, στη συνέχεια αναζητάτε μονοπάτι στον γράφο των σημείων που συνδέει την αρχική και τελικη θέση.

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