Ένας απλούστερος αλγόριθμος υπολογισμού του πυρήνα ενός πολυέδρου
(EL)
A simpler algorithm for computing the kernel of a polyhedron
(EN)
Κεφαλληνός, Διονύσιος
(EL)
Κεφαλληνός, Διονύσιος
(EL)
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
(EL)
Παληός, Λεωνίδας
(EL)
H εύρεση του πυρήνα ενός πολυέδρου συγκαταλέγεται στην οικογένεια προβλημάτων ορατότητας του χώρου με το ελάχιστο πλήθος φυλάκων (art gallery problem). Βρίσκοντας τον πυρήνα έχουμε πλήρη ορατότητα σε όλο τον χώρο με έναν μόνο φύλακα, λύνοντας το πρόβλημα της επόπτευσης. Σε αυτήν την εργασία δίνεται ένας αλγόριθμος για τον υπολογισμό του πυρήνα ενός πολυέδρου. Πολύεδρο είναι ένα απλό στερεό το οποίο ορίζεται από ένα σύνολο κορυφών και ένα σύνολο εδρών στις τρεις διαστάσεις, ως έδρα εννοούμε το πολύγωνο στις τρεις διαστάσεις. Το πολύεδρο χωρίζει το χώρο σε δύο περιοχές στο εσωτερικό του και στο εξωτερικό του. Όλα τα στερεά του πραγματικού κόσμου μπορούν να αναπαρασταθούν ως πολύεδρα. Πυρήνας Κ ενός πολυέδρου P είναι το μεγαλύτερο κυρτό πολύεδρο που μπορεί να υπάρξει εντός του P, με την ιδιότητα κάθε σημείο του Κ να ενώνεται με καθένα σημείο του P μέσω ενός ευθυγράμμου τμήματος L, χωρίς το L να βρίσκεται σε κάποιο σημείο του εκτός του P. H κωδικοποίηση του αλγορίθμου έγινε στη γλώσσα προγραμματισμού C++, και η οπτικοποίηση έγινε με τις βιβλιοθήκες της openGL στο περιβάλλον v1sual stud1o.
(EL)
Determining the kernel of a polyhedron is a subproblem which is included to the generic category of problems of finding the minimum number of guards which is required to watch all the given space (art gallery problem). When we know the kernel, we know all the points that can watch all the space. Of course the kernel can be empty which means no one point (guard) can watch the entire space. In this project we give one algorithm that computes the kernel of a polyhedron. Polyhedron is a simple solid that is defined from a set of vertices and a set of faces in three dimensions. All the solids in real world can be presented as polyhedrons. Kernel K of a polyhedron P is the largest convex polyhedron that can exist inside of P, respecting the following rule. Every point of K can be connected to every point of P via a line segment L, with no point of L outside of P.
Our algorithm uses the idea of duality to compute the kernel of a polyhedron. It transforms the planes of the polyhedron to points in three dimensional space, by a transformation equation one to one that corresponds one plane to one point and one point to one plane. Initially we enlist each plane of the given polyhedron in one of two groups. In the first group we have planes from the up part of the polyhedron, symmetrically in the second group we have planes from the down part of the polyhedron. Then we compute the two convex hulls of the dualized points of each group. Finally from the planes of the convex hulls we take the dualized points (inverse transformation) which are points of the kernel.
The algorithm runs in O(nlogn) time as the algorithm of Preparata and Muller [2] however is simpler algorithm because it uses simpler equation of duality, while the algorithm of Preparata and Muller [2] uses transformation in fourth dimensional space with more complicated manipulations.
The algorithm was coded in C++ programming language and visualized with libraries of openGL in visual studio environment.
(EN)
University of Ioannina
