[c] riconoscere poligoni convessi!! AIUTO

[nefer]

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]

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]

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]

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]

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]

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]

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]

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°.