algorithmicProject-1

Non-amblygonal triangulation of Planar Straight Line Graphs (PSLG) using CGAL library

ΜΕΛΗ:

ΕΥΑΓΓΕΛΟΣ ΚΑΛΑΜΠΟΚΗΣ-1115202100045-sdi2100045@di.uoa.gr ΕΡΙΚ ΚΑΓΙΑΤΣΚΑ-1115202100043sdi2100043@di.uoa.gr

ΕΚΤΕΛΕΣΗ ΠΡΟΓΡΑΜΜΑΤΟΣ: Προκειμένου να εκτελεστεί το πρόγραμμα πρέπει να ακολουθήσουμε τα παρακάτω βήματα:

1. Είσοδος στον φάκελο build (cd build)
2. cmake ..
3. make
4. ./main ../$folder/$instance_name ( όπου $folder ο φάκελος που περιέχει τα instances που θέλουμε και $instance_name το όνομα του instance)

ΛΕΙΤΟΥΡΓΙΑ ΑΛΓΟΡΙΘΜΟΥ:

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

ΑΡΧΕΙΑ: Το πρόγραμμα αποτελείται από 2 βασικά αρχεία:

1. main.cpp: Το main αρχείο το οποίο πραγματοποιεί το delaynay triangulation καλεί τις συναρτήσεις που είναι υπεύθυνες για την εισαγωγή steiner points και edge flips και πραγματοποιεί επίσης τις αναγνώσεις και εγγραφές από και σε json αρχεία

2. triangulation.hpp: Είναι το αρχείο που χειρίζεται την εισαγωγή steiner points και τα edge flips. Το αρχείο αυτό χρησιμοποιεί templates για τις συναρτήσεις που χρησιμοποιούνται όπως και είχε ζητηθεί. Συγκεκριμένα αποτελείται από τις εξής συναρτήσεις:

I. isObtuse: Η συνάρτηση αυτή δέχεται 3 σημεία και επιστρέφει αν το τρίγωνο που σχηματίζουν είναι αμβλυγώνιο ή όχι.

II. isPointInTriangle: Δέχεται 4 σημεία, 3 ενός τριγώνου και 1 ακόμα, η συνάρτηση επιστρέφει true εαν το σημείο βρίσκεται μέσα στο τρίγωνο.

III. getCentroid: Επιστρέφει το σημείο που βρίσκεται στο κέντρο του τριγώνου.

IV. getProjection: Επιστρέφει το σημείο που βρίσκεται στο τέλος της προβολής της αμβλείας γωνίας

V. getMidpointOfLongestEdge: Επιστρέφει το σημείο που βρίσκεται στο μέσο της μεγαλύτερης πλευράς ενός αμβλυγώνιου τριγώνου.

VI. countObtuseTriangles: Συνάρτηση που υπολογίζει το συνολικό αριθμό των αμβλυγώνιων στο cdt.

VII. processCluster: Συνάρτηση που αφαιρεί τις κοινές ακμές από ένα σύνολο αμβλυγώνιων τριγώνων που είναι γείτονες μεταξύ τους.

VIII. tryPointInsertion: Η συνάρτηση αυτή καλείται από κάθε μέθοδο που υπολογίζει ένα σημείο και ελέγχει ποια μέθοδος επιστρέφει τα καλύτερα αποτέσματα επιστρέφοντας τον συνολικό αριθμό των αμβλυγώνιων που παράγει η κάθε μια από αυτές.

IX. areNeighbours: Η συνάρτηση αυτή επιστρέφει αν 2 τρίγωνα είναι γειτονικά ή όχι

X. collectNeighbouringObtuseTriangles: Επιστρέφει ένα vector που περίεχει τα obtuse triangles που είναι γειτονικά μεταξύ τους, σχηματίζοντας δηλαδή ένα obtuseCluster.

ΧI. getConvexHullCentroid: υπολογίζει το κέντρο του οbtuseCluster.

XII. tryMergingObtuseTriangles: Σχηματίζει το κυρτό πολύγωνο με βάση το obtuse cluster και επιστρέφει το κέντρο του.

XIII. addSteinerPoints: Η συνάρτηση αυτή διατρέχει όλα τα τρίγωνα του cdt και δοκιμάζει την εισαγωγή steiner points χρησιμοποιώντας τις προαναφερθείσες μεθόδους επιλέγοντας αυτή που σχηματίζει τα λιγότερα αμβλυγώνια τρίγωνα

XIV. isFlipableForNonObtuse: Αποτελεί μια custom is flippable που δεν βασίζεται στο να διατηρεί τη συνθήκη ενός cdt αλλά δοκιμάζει να κάνει flip σε αμβλυγώνια τρίγωνα αν αυτό τα κάνει μη αβλυγώνια ελέγχοντας να μην υπάρχουν επίσης οverlaps μεταξύ των ακμών.

XV. flipEdgesToMakeNonObtuse: H συνάρτηση αυτή πραγματοποιεί το flip συνδυάζοντας την isFlipableForNonObtuse και τη flip της cdt εφόσον βοηθά στη μείωση των αμβλυγώνιων τριγώνων.

XVI. toFraction: Χρησιμοποιείται για να παραγάγει το επιθυμητό output σε json μορφή