Μια ερώτηση για τριγωνισμούς

[A.N.T.]

Θέλω να ρωτήσω κάτι όσους ξέρουν από γραφικά.

Έστω ότι έχω ένα σύνολο σημείων στο εσωτερικό ενός (επίπεδου) πολυγώνου.
Θέλω να φτιάξω ένα πλέγμα τριγώνων από αυτά τα σημεία.
Αν το πολύγωνο είναι κυρτό, τα τρίγωνα φτιάχνονται με Delaunay.

Αν όμως δεν είναι, μπορεί να εφαρμοστεί Delauny ;
Δηλ. ο τριγωνισμός Delaunay μπορεί να γίνει σε σημεία που περιέχονται σε μη κυρτά πολύγωνα ;

Στην βιβλιογραφία δεν αναφέρεται ξεκάθαρα.
Είδα π.χ. ένα ορισμό που ο τριγωνισμός Delaunay οριζόταν στην convex hull ενός συνόλου σημείων.
(Αλλά δεν απέκλειε ρητά τα μη κυρτά.)
Επίσης, το αντίστοιχο διάγραμμα Voronoi έχει ακραία γειτονικά σημεία που ορίζουν την convex hull των σημείων.
Aπό αυτά συμπεραίνω ότι ο τριγωνισμός Delaunay αφορά μόνον κυρτό πολύγωνο.

Αλλά αν πάρω σημεία σε ένα μη κυρτό πολύγωνο, φτιάξω έναν τυχαίο τριγωνισμό και
μετά εναλλάσσοντας τις ακμές πετύχω να ικανοποιείται το MaxMin angle κριτήριο,
ο τελικός τριγωνισμός δεν θα είναι Delauny ;

Γενικά, τριγωνισμός Delauny σε σημεία που ανήκουν σε μη κυρτό πολύγωνο ορίζεται ;
Μέχρι τώρα δεν είδα ούτε "ναι" ούτε "όχι"...

[Παπι]

Off Topic

Παρε το blender (blender.org) φτιαξε εναν converter απο x3d σε ενα δικο σου φορματ και κανε την δουλεια σοτ

[A.N.T.]

Αν ήθελα κάτι έτοιμο θα έριχνα το σχήμα σε μια γεννήτρια πλέγματος και θα ξεμπέρδευα - σιγά να μην έμπλεκα με το Blender...

Θέλω να ξέρω τι ειναι σωστό : ο ορισμός ισχύει για μη κυρτά πολύγωνα ή όχι ;

[Παπι]

Τι να σου πω, απο youtube που ειδα εν δραση τον αλγοριθμο, βλεπω οτι η δουλεια του ειναι να βρει ενα κυρτο πολυγωνο μεσα σε καποια τυχαια σημεια. Εσενα πως σου βγαινει κοιλο; Αν εχει περισσοτερα απο 3 σημεια παντα μπορεις να βρεις ενα κυρτο πολυγωνο.
Φυσικα υπαρχει και η τεραστια πυθανοτητα να μην εχω καταλαβει τον αλγοριθμο

[A.N.T.]

Δεν έχεις καταλάβει ούτε τον ορισμό, ούτε τον προβληματισμό μου.

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

Αν τα σημεία που δίνονται ανήκουν στο εσωτερικό ενός πολυγώνου,
με τον τριγωνισμό ουσιωδώς φτιάχνεται ένα πλέγμα τριγώνων στο πολύγωνο (κατασκευή mesh).
Άρα με τον τριγωνισμό μπορούν να γίνει meshing ενός πολυγώνου.

Στους ορισμούς υπονοείται (αλλά όχι ξεκάθαρα) ότι ο τριγωνισμός Delaunay ορίζεται στην
convex hull (κυρτό πολύγωνο) του συνόλου των σημείων.
(Και βέβαια το voronoi διάγραμμα - το δυικό του delaunay - έχει σημεία που ορίζουν convex hull.)
Συνεπώς, αν τα σημεία περιέχονται σε κυρτό πολύγωνο, επιδέχονται τριγωνισμό Delaunay,
δηλ. αν δίνεται ένα κυρτό πολύγωνο με σημεία εντός αυτού, παράγεται πλέγμα με Delaunay.
Aν όμως δεν είναι κυρτό, τι γίνεται, μπορεί να τριγωνιστεί με Delaunay ή όχι ;
Προφανώς τα σημεία μπορούν πάντα να τριγωνιστούν με Delaunay αλλά τότε το πολύγωνο που θα ορίζει ο τριγωνισμός
δεν θα συμπίπτει με το δοθέν - θα είναι κυρτό.

Δες το συνημμένο σχήμα fig.1
Zητείται να τριγωνιστεί ένα σύνολο σημείων που περιέχονται σε ένα μη κυρτό πολύγωνο.
Μπορώ να το τριγωνίσω με Delaunay ή όχι ;
Καταρχήν όχι διότι όπως είπα ο Delaunay ορίζεται σε convex hull (όπως υπαγορεύει και το δυικό διάγραμμα voronoi)
ενώ εδώ το πολύγωνο δεν είναι κυρτό.
Έστω λοιπόν ότι κάνω έναν τυχαίο τριγωνισμό (που διατηρεί βέβαια το δοθέν σύνορο).
Μετά με εναλλαγή των ακμών (edge swapping) τον μετατρέπω έτσι ώστε να ικανοποιείται το
κριτήριο MaxMin angle (ή το κριτήριο του κύκλου) το οποίο ορίζει τον τριγωνισμό Delaunay.
O τριγωνισμός που καταλήγουμε έτσι είναι Delaunay ή όχι ;
Και υπάρχει τρόπος να πάμε σε αυτόν απο την αρχή ;

[Παπι]

Ok...

Αν στη περιπτωση που στο Α και Β η εσωτερικη ενωση (το αποτελεσμα του delaunay) των σημειον ταυτιζετε με αυτη του Γ (που ειναι Α και Β μαζι) τοτε ειναι αποτελεσμα ενος delaunay, λογικα μιλωντας.

Τεσπα κανε την ερωτηση σου εδω

[A.N.T.]

Στην γ) περίπτωση ο (συνολικός) τριγωνισμός ικανοποιεί τα κριτήρια που θα τον χαρακτήριζαν ως delaunay :
το MaxMin angle ή το κριτήριο του κύκλου ή της τοπικής βελτιστοποίησης των ακμών.

ΑΛΛΑ δεν ορίζεται σε convex hull όπως υπονοεί ο ορισμός.
Και το δυικό του διάγραμμα voronoi δεν έχει convex hull που να συμπίπτει με το δοθέν πολύγωνο όπως
θα έπρεπε (και όπως συμβαίνει όταν το δοθέν πολύγωνο είναι κυρτό).
Δηλ. αν θεωρηθεί ως delaunay (αφού ικανοποιεί τα κριτήρια), αντιφάσκει εν μέρη στον κλασικό ορισμό. Αυτό είναι η απορία μου.
Ούτε φαίνεται να μπορεί να φτιαχτεί άμεσα με τις κλασσικές τεχνικές.

Ίσως ένας τρόπος είναι με constrained delaunay triangulation (CDT) όπου στον τελικό τριγωνισμό
ζητείται να υπάρχουν κάποιες προκαθορισμένες ακμές.
Το μη κυρτό τμήμα του συνόρου θα μπορούσε να θεωρηθεί ότι είναι τέτοιες ακμές.
Αλλά τα παραδείγματα CDT που έχω δει ασχολούνται με ακμές στο εσωτερικό, όχι στο περίγραμμα του σχήματος.

Αυτό που λες εσύ στο post #6 είναι ότι η ένωση τριγωνισμών delauny είναι τριγωνισμός delauny.
Αλλά το "λογικά μιλώντας" που γράφεις είναι παντελώς αστήρικτο.
H ένωση κυρτών πολυγώνων - και άρα τριγ. delaunay - δεν είναι αναγκαστικά κυρτό πολύγωνο,
άρα ο τριγωνισμός της ένωσης δεν έπεται ότι θα είναι επίσης delaunay όπως λες.
Το σχήμα σου στο γ) δείχνει ακριβώς το αντίθετο από αυτό που ισχυρίζεσαι :
ενώνεις 3 κυρτά πολύγωνα (δηλ. τρ. delaunay) και παίρνεις ένα μη κυρτό το οποίο δεν μπορεί να
δώσει delaunay άμεσα διότι δεν συμφωνεί με τον ορισμό.
Εξαλλου αν μπορούσε, θα φτιαχνόταν κατευθείαν.


Σε ευχαριστώ πολύ που ασχολήθηκες πάντως....

[xcyanx]

Source: http://www.google.com/url?sa=t&sourc...H3ATmA&cad=rja

Στθν περίπτωςθ μθ κυρτϊν πολυγωνικϊν αντικειμζνων, το πεδίο καταςκευάηεται με βάςθ τον Οριςμό
1, με τθν ανάλυςθ του πολυγϊνου ςε επιμζρουσ κυρτά πολφγωνα. Θ διαδικαςία τθσ ανάλυςθσ
ςτθρίηεται ςτον αλγόρικμο ελάχιςτθσ αποδόμθςθσ ςε κυρτά πολφγωνα (minimum convex polygon
decomposition algorithm) [50] [51] . Άλλοι αλγόρικμοι όπωσ θ τριγωνοποίθςθ Delaunay [52] [53]
μποροφν να χρθςιμοποιθκοφν με το μειονζκτθμα τθσ αυξθμζνθσ πολυπλοκότθτασ του παραγόμενου
πεδίου, μιασ και ο αρικμόσ των αναλυκζντων κυρτϊν ςχθμάτων (τριγϊνων ςτθ ςυγκεκριμζνθ
περίπτωςθ) δεν κα είναι ο ελάχιςτοσ δυνατόσ.

Οπότε αν είναι σωστό αυτό και αν το κατάλαβα σωστά αν έχεις ενα μη κυρτό πολύγωνο τότε το σπας σε επιμέρους κυρτά πολωνα και μπορείς να εφαρμόσεις κάποιον απο τους αλγόριθμους που θες πάνω του. Οπότε αν ισχύει αυτό o ΠΑΠΙ είναι σωστός.

P.S. Sorry για το κείμενο αλλά βγήκε έτσι μετά το copy-paste. Όταν το ανοίξεις απλά πήγαινε στη σελίδα 53 και το γράφει εκεί. Αν πάλι δεν είναι αυτό sorry αλλά δεν έχω ασχοληθεί με το αντικείμενο και δεν είδα κάποιος που ξέρει να απαντάει και είπα να ψάξω λίγο στο google μπας και μπορώ να βοηθήσω.

[A.N.T.]

Φίλε μου η απορία μου είναι φορμαλιστική και όχι πρακτική.

Στην πράξη ξέρω πώς να το φτιάξω.
Μια γεννήτρια πλέγματος που δουλεύει με delaunay ορίζει ένα κυρτό σχήμα προσθέτοντας σημεία,
κάνει τριγωνισμό με delaunay και τέλος αφαιρεί τα περιττά τρίγωνα.
Έτσι απομένει το σύνολο σημείων τριγωνισμένο πλέον στο αρχικό πολύγωνο.
Το αρχικό πολύγωνο μπορεί να είναι κυρτό ή όχι αλλά η γεννήτρια για να εφαρμόσει delaunay το κάνει πάντα κυρτό
και μετά αφαιρεί τα κομμάτια που δεν χρειάζονται.
Nα, όπως στο fig.1 που δείχνω παρακάτω.
Εναλλακτικά εφαρμόζεται advancing front τεχνική που δεν έχει τέτοια προβλήματα
(αλλά δεν δουλεύει σε προκαθορισμένα σημεία - εκεί τα σημεία προστίθενται κατά τη διαδικασία).
Επισημαίνω ότι είναι άλλο πράγμα ο τριγωνισμός πολυγώνου και άλλο ο τριγωνισμός σημείων που περιέχονται σε πολύγωνο.
Εδώ η ιστορία αφορά το δεύτερο.

Από αυτά που είδα, πιθανολογώ ότι delaunay σημείων σε μη κυρτό πολύγωνο δεν μπορεί να γίνει άμεσα παρά
μόνον δια της πλαγίας οδού που ανέφερα πριν : τα τριγωνίζω τυχαία και μετά με edge swapping επιτυγχάνω
να ικανοποιεί τα κριτήρια που έχει ο delaunay.
Ή κάνω τον τριγωνισμό σε ένα κυρτό σχήμα που περιέχει το μη κυρτό και μετά βγάζω τα τρίγωνα που δεν χρειάζονται.
Σε κάθε περίπτωση όμως ο τελικός τριγωνισμός δεν είναι delaunay στο μη κυρτό σχήμα διότι δεν έχει περίμετρο την
convex hull του δυικού διαγράμματος voronoi όπως υπαγορεύει ο ορισμός.
Τα κριτήρια ικανοποιούνται αλλά δεν ικανοποιείται αυστηρά ο ορισμός.
Αυτό μου φαίνεται κάπως σαν αντίφαση.

Eν πάση περιπτώση, σας ευχαριστώ που ασχοληθήκατε...

[xcyanx]

Όπως σου είπα δεν ξέρω, οπότε αυτά που μου λες λίγο τα καταλαβαίνω μιας και δεν έχω ασχοληθεί ποτέ :s... Τέσπα ελπίζω να το βρεις πάντως.