Γωνία με x'x

[Gbax13]

Καλησπέρα παιδιά.

 

Σε ένα πρόγραμμα που δουλεύω ένα κομμάτι (το αρχικό) απαιτεί το εξής: Έχω έναν πίνακα με σημεία α[Ν] στο καρτεσιανό σύστημα συντεταγμένων, όπου βρίσκω το κατώτερο σημείο (y=min), το α[1]. Τα υπόλοιπα Ν-1 σημεία βρίσκονται στο ίδιο τεταρτημόριο και όλα πάνω από το α[1]. Θέλω λοιπόν να ταξινομήσω όλα τα σημεία αυτά με βάση τη γωνία που σχηματίζουν με το α[1](αριστερόστροφα), δηλαδή (σκέφτηκα) τη γωνία που σχηματίζει το διάνυσμα με αρχή το α[1] και πέρας το κάθε σημείο που μου έρχεται, με τον x'x. Μία λύση που έχω σκεφτεί είναι να χρησιμοποιήσω την κλίση του διανύσματος , αφού θα εκτείνεται από 1 έως -1 (γιατί α το κατώτερο σημείο). Το πρόβλημα είναι ότι κάποια στιγμή η κλίση δε θα ορίζεται, ενώ σε περίπτωση δύο συνευθειακών σημείων ως προς το α οι κλίσεις, λόγω διαίρεσης μεταξύ double, μπορεί να μη βγαίνουν ίδιες (αλλιώς θα μπορούσα εύκολα να συγκρίνω τις δύο τετμημένες και να τα ταξινομήσω). Η άλλη λύση θα ήταν ίσως να υπολογίσω cos διανυσμάτων μέσω του εσωτερικού τους γινομένου, αλλά λογικά θα είναι πολλές οι πράξεις, + ότι δεν ξέρω τι να πάρω ως σημείο αναφοράς.

 

Ποια λύση μου προτείνετε;

Ευχαριστώ εκ των προτέρων

 

Υ.Γ.1: Σχετίζεται με convex hull το πρόγραμμα, αν σας βοηθάει καθόλου.

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

[virxen75]

2 σημεία είναι πάντα συνευθειακά

άρα μάλλον εννοείς να είναι παράλληλα ως προς τους άξονες

 

κάνε πρώτα έλεγχο για κοινό X ή κοινό Y (παράλληλα ως προς τους άξονες)

[Gbax13]

Λάθος διατύπωση, δεν εννοούσα δύο σημεία, αλλά τα διανύσματα που ορίζουν δύο σημεία με το ίδιο (α[1]). Τα παράλληλα ως προς τους άξονες δεν αποτελούν πρόβλημα αν ορίσω αρχικά το κατώτερο να είναι το πιο αριστερά ή το πιο δεξιά.

 

Αυτό που με ενδιαφέρει είναι το αν θα χρησιμοποιήσω κλίση (δηλαδή tan) ή άλλον τρόπο, τα υπόλοιπα εντάξει ένα sort είναι

[παπι]

 

Δηλαδη θελεις πχ

a c d b να γινει a b c d ;

[V.I.Smirnov]

Έχοντας μια γνώση από σχετικά θέματα, έχω να παρατηρήσω τα ακόλουθα.

 

1) Tα προβλήματα αυτού του είδους συνήθως προϋποθέτουν ότι είναι διαθέσιμες κάποιες

βασικές δομές και συναρτήσεις όπως πχ. "point", "line", "point-line classification" κλπ που

απλοποιούν τις διαδικασίες. Το σωστό είναι να φτιάξεις πρώτα τα στοιχεία αυτά

(ή να βρεις έτοιμα) και μετά να επιχειρήσεις να λύσεις το πρόβλημα χρησιμοποιώντας τα.

Ακόμα και σε βασικό επίπεδο, βοηθούν πολύ να οργανωθεί ο κώδικας και να εκφραστεί ο

αλγοριθμος με σαφήνεια.

 

2) Το θέμα της ακρίβειας είναι ακανθώδες σε προβλήματα αυτού του είδους.

Για τα βασικά τεστ (συνευθειακά σημεία, σημεία σε περιφέρεια κύκλου, έλεγχος δεξιοστροφίας και

μερικά ακόμη) χρησιμοποιούνται ειδικές ρουτίνες που κάνουν τις πράξεις με αυτόματα ρυθμιζόμενη

ακρίβεια ώστε να αποφεύγονται οι κακοτοπιές. Μια τέτοια βιβλιοθήκη που χρησιμοποιείται συχνά

είναι του Shewchuck. Για πιο πρόχειρα πράγματα, οι συγκρίσεις γίνονται χρησιμοποιώντας μια

παράμετρο e ως ακρίβεια, π.χ. αντί x1==x2, θέτεις abs(x1-x2)<e με e=.001 ή .0001 κλπ

 

3) Σε ότι αφορά την convex hull, υπάρχει πληθώρα τεχνικών. Εγώ για το επίπεδο ξέρω τρεις τρόπους :

incremental, gift wrappping και graham scan. Αλλά όλες τις είχα φτιάξει με δομές και ρουτίνες του

τύπου "point", "line", "classifyPoint" κ.α. που αποσαφηνίζουν και συντομεύουν πολύ την έκφραση

του αλγόριθμου.

Ο incremental αλγόριθμος είναι για μένα ο βολικότερος - τουλάχιστον εκεί που τον εφάρμοσα κάποτε -

διότι επιτρέπει να εισέρχονται νέα σημεία σε μια ήδη υπάρχουσα convex hull δίχως να πρέπει να υπολογί-

ζονται όλα από την αρχή κάθε φορά.

 

 

Στο συγκεκριμένο πράγμα που ρωτάς (post #3), ναι, γίνεται και με την εφαπτoμένη :

χρειάζεται απλώς μια ρουτίνα που να δίνει την προσανατολισμένη γωνία ενός διανύσματος

ως προς τον (θετικό) x άξονα στο διάστημα [0,2π).

 

-

[Gbax13]

 

Δηλαδη θελεις πχ

a c d b να γινει a b c d ;

Nαι, αυτό.

 

@smirnov ναι εγώ graham scan κάνω, δε χρειάζομαι κάτι πιο δυναμικό και από όσο διάβασα είναι αρκετά γρήγορος για αυτό που θέλω (διαβάζω πίνακα, φτιάχνω convex hull, εμφανίζω τα σημεία σε άλλο αρχείο). Το πρόβλημά μου δεν είναι ο υπόλοιπος αλγόριθμος, γιαυτό και δεν ανέφερα κάτι. Όσο για τις συγκρίσεις ανάμεσα σε double ξέρω ότι είθισται να μη χρησιμοποιούνται '<>=', αλλά fabs(a-<1e-7 για παράδειγμα ή αυτό που είπες.

 

Ευχαριστώ για τη βοήθεια.

[V.I.Smirnov]

Αν θυμάμαι καλά, ο αλγόριθμος Graham, αν χρησιμοποιηθεί μια κατάλληλη μέθοδος ταξινόμησης,

είναι τάξης O(nlogn). Αν μάλιστα το σύνολο σημείο σημείων είναι ταξινομημένο, τρέχει σε O(n).

 

Δεν ξέρω τι ακριβώς έχεις κατά νου αλλά η tanφ (δηλ. η κλίση) έχει περίοδο π (όχι 2π).

Για να βρεθεί σωστά η προσανατολισμένη γωνία στο διάστημα 2π χρειάζεται μια μικρή διερεύνηση.

Η απλή κλίση δεν επαρκεί.

Eγώ έβρισκα πρώτα, όπως ανάφερα, τις προσανατολισμένες γωνίες των διανυσμάτων με τον

άξονα Οx στο διάστημα [0,2π) και μετά έκανα την ταξινόμηση. Έτσι, σε οποιοδήποτε

τεταρτημόριο κι αν βρίσκονταν τα σημεία η ταξινόμηση γινόταν σωστά και δεν μπερδευόμουν

σε καμιά περίπτωση.

 

 

Καλή συνέχεια...

 

-

Επεξ/σία 26 Φεβρουαρίου 2012 από V.I.Smirnov

[mvaggel]

Σκέψεις (αν το έχω καταλάβει σωστά).

 

Το α[1] είναι το κατώτερο σημείο, αλλά όχι και το πιο αριστερό (παντού υποθέτω τεταρτημόριο όπου

x:0->άπειρο, y:0->άπειρο).

 

Αν φ=0 ο άξονας y (κάθετος), η γωνία σου μπορεί να είναι -π/2<φ<π/2, άρα -1<cos(φ)<1

 

Σε αυτό το διάστημα, αν cos(φ1)<cos(φ2) => φ1<φ2

 

Για το cos(Φi)=(Xi-X1)/(sqrt((Xi-X1)^2+(Yi-Y1)^2))

 

To tan(φ) για φ=0 δεν ορίζεται

 

Το sin(φ)=sin(-φ), άρα μόνο με αυτό δε μπορείς να συγκρίνεις θετικές και αρνητικές γωνίες

 

Συμπερασματικά: Αν υπολογίσεις τα cos, τα ταξινομείς και έχεις και τις γωνίες ταξινομημένες

[Gbax13]

Smirnov, όταν λες προσανατολισμένες γωνίες εννοείς με εξωτερικό γινόμενο;

 

Mvaggel, το "cos(Φi)=(Xi-X1)/(sqrt((Xi-X1)^2+(Yi-Y1)^2))" προέκυψε από εσωτερικό γινόμενο; αν μπορείς εξήγησέ το.

[V.I.Smirnov]

Αυτό που εννοώ είναι το εξής.

 

Κάθε διάνυσμα v έχει μια γωνία σε σχέση με το μοναδιαίο διάνυσμα i του x άξονα.

Η γωνία αυτή, φ(i,v), είναι κατά τα γνωστά εκείνη κατά την οποία πρέπει να στραφεί

κατά την θετική φορά το i για να συμπέσει με το v. Κυμαίνεται από 0 έως 2π.

Όμοια ισχύει αν αντί για το i τεθεί ένα άλλο, οποιαδήποτε διάνυσμα.

Με την γωνία αυτή, βρίσκεται ο προσανατολισμός ενός διανύσματος ανεξάρτητα από το

τεταρτημόριο όπου βρίσκονται τα άκρα του.

Τα παραπάνω αναφέρονται στο επίπεδο (στο χώρο υπάρχουν κάποιες διαφορές).

 

Έστω τα διανύσματα u, v, με συντεταγμένες (ux,uy) και (vx,vy) ως προς την βάση (i,j).

(Eδώ i,j είναι τα μοναδιαία διανύσματα των αξόνων.)

Η προσανατολισμένη γωνία φ των u,v βρίσκεται με χρήση των σχέσεων :

 

cosφ=(uxvx+uyvy)/sqrt(ux^2+uy^2) εδώ ο αριθμητής είναι το εσωτερικό γινόμενο των u,v

sinφ=(uxvy-uyvx)/sqrt(ux^2+uy^2) εδώ ο αριθμητής είναι το εξωτερικό γινόμενο των u,v

 

Υπενθυμίζεται ότι τα sinφ και cosφ δεν είναι αμφιμονοσήμαντες συναρτήσεις στο [0,2π).

Π.χ. cos(2π-φ)=cosφ και sin(π-φ)=sinφ. Συνεπώς, μόνον μια εκ των παραπάνω σχέσεων δεν

αρκεί για να βρεθεί το σωστό τεταρτημόριο.

Χρησιμοποιώντας αμφότερες τις δυο σχέσεις, κάνεις μια μικρή διερεύνηση για να βρεθεί η φ στο [0,2π).

Βγαίνει και με χρήση της εφαπτομένης αλλά πάλι απαιτείται διερεύνηση.

Επισημαίνεται ότι τα ux,uy,vx,vy είναι οι συντεταγμένες των διανυσμάτων που

συγκρίνονται, όχι των άκρων τους. Π.χ. αν τα σημεία Α,Β ορίζουν το διαν. u,

δηλ. u=ΑΒ, θα είναι ux= Bx-Ax και uy=By-Ay.

Aν το διάνυσμα είναι το μηδενικό, πρόκειται για ειδική περίπτωση και την χειρίζεσαι κατάλληλα.

 

Βρίσκοντας έτσι την γωνία κάθε διανύσματος, μπορεί μετά να γίνει η ταξινόμησή τους ανάλογα με αυτήν.

Πιθανόν γίνεται και πιο εύκολα ή γρήγορα, απλώς αυτός είναι τρόπος που δουλεύει πάντα και δεν μπερδεύεσαι.

Η σχέση περί της οποίας ρωτάς τον mvag όντως προκύπτει από εσωτερικό γινόμενο.

 

Τέλος μαθήματος γεωμετρίας....

 

-

[Gbax13]

Είσαι μέγας ναι κατάλαβα ότι κάτι έπαιζε με εσωτερικό γινομενο. Σορρυ για τις άπειρες ερωτήσεις αλλα κάπου χάθηκα στην ψαγμενη απάντηση του mvagg

 

Sent from my iPod touch using Insomnia

[mvaggel]

Mvaggel, το "cos(Φi)=(Xi-X1)/(sqrt((Xi-X1)^2+(Yi-Y1)^2))" προέκυψε από εσωτερικό γινόμενο; αν μπορείς εξήγησέ το.

 

Βασικά το συνημίτονο της φ είναι η προσκύμμενη κάθετη (Xi-X1) προς την υποτεινουσα (ρίζα του: (Xi-X1)στο τετράγωνο συν (Yi-Y1)στο τετράγωνο, πυθαγόρειο θεώρημα). Προφανώς καταλήγεις στο ίδιο και με προσέγγιση δυανυσματική και εσωτερικό γινόμενο (μου διαφεύγει αυτή η στιγμή η θεωρία, πάνε χρόνια που έχω να ασχοληθώ, αλλά έχω εμπιστοσύνη στον Smirnov (παρότι προτιμώ την Absolut ))