PDA

View Full Version : [c] riconoscere poligoni convessi!! AIUTO

nefer
05-04-2005, 09:35
Ciao a tutti!!
č da qualche giorno che sbatto la testa su questo problema: data una sequenza di coordinate (intere) cartesiane determinare se delimitano un poligono convesso. Le coordinate sono elencate in senso orario ( non ho ancora capito se questa informazione č utile).
Un poligono č convesso quando per ogni coppia di punti (non necessariamente intere) all'interno di esso il segmento che unisce tali punti č composto da punti che appartengono tutti al poligono.

Un esempio di pol. convesso č la sequenza: (-2,4) (0,5) (4,3) (2,1) (-2,2)

Un esempio di pol non convesso č: (0,-1) (0,2) (2,3) (2,0) (1,1)

Ringrazio tutti quelli che mi vorranno aiutare!!!!
lombardp
05-04-2005, 09:52
Da profano mi verrebbe in mente:

- calcolo la pendenza (in gradi) dei vari segmenti del poligono

- se č convesso la pendenza aumenterā ( o diminuirā) sempre, se invece č concavo, si assisterā almeno a due inversioni di tendenza.
nefer
05-04-2005, 10:20
Non capisco bene cosa intendi!
Data la sequenza di coordinate che ho scritto che definisce un poligono convesso noto che:

da (-2,4) a (0,5) la pendenza sale (č positiva)
da (0,5) a (4,3) la pendenza scende (č negativa)
da (4,3) a (2,1) la pendenza sale (č positiva)
da (2,1) a (-2,2) la pendenza scende (č negativa)

ciao e grazie!
cionci
05-04-2005, 10:52
Prendendo 3 punti consecutivi se tracci una retta fra il punto 1 e il punto 3 questa sarā tutta all'interno del poligono se il punto 2 non comporta una concavitā...sarā tutta fuori dal poligono se il punto 2 comporta una concavitā... Basta verificare che uno dei punti della retta sia al di fuori della retta...

Per fare questo potesti determinare il baricentro del poligono... Se l'intersezione fra la retta che congiunge il punto 2 e il baricentro si interseca con la retta tracciata precedentemente dopo (a partire dal baricentro) il punto 2 allora il poligono č concavo...
lombardp
05-04-2005, 11:29
Originariamente inviato da nefer
Non capisco bene cosa intendi!
Data la sequenza di coordinate che ho scritto che definisce un poligono convesso noto che:

da (-2,4) a (0,5) la pendenza sale (č positiva)
da (0,5) a (4,3) la pendenza scende (č negativa)
da (4,3) a (2,1) la pendenza sale (č positiva)
da (2,1) a (-2,2) la pendenza scende (č negativa)

ciao e grazie!

Pensiamolo come un orologio:

da (-2,4) a (0,5) se fosse un orologio sarebbero le 2
da (0,5) a (4,3) se fosse un orologio sarebbero le 4
da (4,3) a (2,1) se fosse un orologio sarebbero le 8
da (2,1) a (-2,2) se fosse un orologio sarebbero le 10
da (-2,2) a (-2,4) se fosse un orologio sarebbero le 1

Come vedi l'orologio non torna mai indietro, se invece fosse concavo, tornerebbe indietro e poi ripartirebbe in avanti.
71104
05-04-2005, 12:56
ragiona in termini di derivata prima! :)
(lo so benissimo di aver detto una boiata assurda, ma penso che renda bene l'idea per analogia)
nefer
05-04-2005, 16:01
:)
bene grazie ho anche trovato un altro metodo che successivamente mi permetterā di stabilire se un punto č interno al poligono.
Infatti in un poligono convesso se tracciamo le rette passanti per i lati noteremo che tutti i vertici del poligono stanno nello stesso semipiano. Facendo l'operazione su tutti i lati scopriamo sia se il poligono č convesso sia se un punto č interno!!

grazie a tutti!!
end.is.forever
05-04-2005, 19:07
Basta che ciascun angolo interno sia < 180, fai il test per ogni punto calcolando derivata dei segmenti con i due punti limitrofi e poi l'angolo interno tra i due e verifichi che sia minore di 180°.