[C++] Dati N punti, come trovo quelli che compongono il perimetro?

[Abadir_82]

Edit: risolto...

[Furla]

non capisco se intendi trovare l'equazione di tutti i punti sul perimetro, o se vuoi solo misurarlo (facendo la somma dei lati). in ogni caso non capisco: tu stai parlando di punti interni o esterni a cosa? al poligono? non credo, visto che il perimetro è "di frontiera"...

[cionci]

Edit: risolto...
Perché non hai postato la soluzione ed hai persino cancellato il problema ? Avrebbe potuto risultare utile anche ad altre persone.

[astorcas]

non capisco se intendi trovare l'equazione di tutti i punti sul perimetro, o se vuoi solo misurarlo (facendo la somma dei lati). in ogni caso non capisco: tu stai parlando di punti interni o esterni a cosa? al poligono? non credo, visto che il perimetro è "di frontiera"...


Credo che intenda una cosa del tipo: dato un insieme di punti sul piano tracciare il poligono più grande (area) che abbia come vertici un sottoinsieme dei punti dati e che racchiuda tutti gli altri punti non facenti parte dell'insieme dei vertici.

E' questo oppure ho detto una vaccata?


Edit: infatti! Sono interessato al problema!

[Abadir_82]

Credo che intenda una cosa del tipo: dato un insieme di punti sul piano tracciare il poligono più grande (area) che abbia come vertici un sottoinsieme dei punti dati e che racchiuda tutti gli altri punti non facenti parte dell'insieme dei vertici.

E' questo oppure ho detto una vaccata?


Edit: infatti! Sono interessato al problema!


Ho cancellato perche' pensavo che non fosse di interesse, un po' come quello dell'altro giorno del fare l'xcopy con funzioni di windows.
No, il problema era: dati N punti del piano tracciare il poligono che li inglobi tutti e che abbia area massima.
Devo ancora implementare il codice, pero' ti posto la soluzione che usero', magari ti viene utile.

- Cerchi il punto con coordinata Y maggiore.
- Tracci tutte le rette tra quel punto e gli altri e guardi il valore dell'angolo che formano con l'asse X. La retta che forma l'angolo piu' grande identifica il prossimo punto (contando di andare in senso orario). Se vuoi vedere il punto precedente ti basta cercare la retta che forma l'angolo piu' piccolo.

Per verificare l'appartenenza di un punto ad un poligono, cosa che credo di serva, traccia le rette tra quel punto ed i vertici, identifica gli angoli e sommali. Se la somma e' pari a 360 allora il punto fa parte del poligono.

[banryu79]

No, il problema era: dati N punti del piano tracciare il poligono che li inglobi tutti e che abbia area massima.

Intendi: che li abbia tutti come suoi vertici?

Chiedo perchè con l'espressione "che li inglobi" a me era venuto da pensare che il poligono risultante potesse anche utilizzare solo un sottoinsieme di detti punti per tracciare il suo contorno purchè al suo interno "inglobasse" anche gli altri; a quel punto avrebbe avuto anche un senso il vincolo dell'area maggiore dato che si potevano generare più poligoni diversi.

La tua soluzione funziona ma se l'ho capita bene è anche l'unica soluzione perchè genera l'unico poligono in quanto deve usare tutti i punti come vertici di definizione del suo contorno ;)
@EDIT: mi correggo, non è l'unico poligono possibile, mi sono sbagliato.

Confrontando gli angoli puoi anche implementare facilmente un algoritmo che ti sappia dire se il tuo poligono è concavo o convesso proprio con una verifica dell'andamento degli angoli dei segmenti che i vertici del suo contorno, ordinati in senso antiorario (o orario) formano... ;)

@EDIT:

Per verificare l'appartenenza di un punto ad un poligono, cosa che credo di serva, traccia le rette tra quel punto ed i vertici, identifica gli angoli e sommali. Se la somma e' pari a 360 allora il punto fa parte del poligono

C'è un algoritmo migliore : link (http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html)

[Abadir_82]

Intendi: che li abbia tutti come suoi vertici?

Chiedo perchè con l'espressione "che li inglobi" a me era venuto da pensare che il poligono risultante potesse anche utilizzare solo un sottoinsieme di detti punti per tracciare il suo contorno purchè al suo interno "inglobasse" anche gli altri; a quel punto avrebbe avuto anche un senso il vincolo dell'area maggiore dato che si potevano generare più poligoni diversi.

La tua soluzione funziona ma se l'ho capita bene è anche l'unica soluzione perchè genera l'unico poligono in quanto deve usare tutti i punti come vertici di definizione del suo contorno ;)
@EDIT: mi correggo, non è l'unico poligono possibile, mi sono sbagliato.

Confrontando gli angoli puoi anche implementare facilmente un algoritmo che ti sappia dire se il tuo poligono è concavo o convesso proprio con una verifica dell'andamento degli angoli dei segmenti che i vertici del suo contorno, ordinati in senso antiorario (o orario) formano... ;)

@EDIT:

C'è un algoritmo migliore : link (http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html)

Scusami, avevo capito male la tua risposta di prima. Allora si, avevi ragione, intendevo proprio quello che dicevi tu.
Con ingloba intendo il fatto che il punto stia nell'area racchiusa dal poligono, ma non necessariamente sul perimetro.
Come giustamente hai detto si va da un minino di 3 punti per il perimetro e tutti gli altri interni ad un massimo di infiniti punti per il perimetro e nessuno interno.
A me basta prendere quello piu' grande, non mi serve controllare concavo o convesso. Il link per vedere l'appartenenza ad un poligono invece lo guardo, puo' sempre far comodo.

[sottovento]

Purtroppo ho finito l'Universita' da troppi anni per ricordarmi l'algoritmo.
E' comunque un problema noto, che ha interessato diversi ricercatori nel corso degli anni.
Quando ho questo tipo di problemi da risolvere, consulto delle librerie di algoritmi. Magari puoi confrontare la tua soluzione con una di quelle riportate. Non ho visto il link di banryu79, ma puoi controllare il libro di Sedgewick "Algorithms in C", penso che esista anche la versione italiana. Oppure puoi controllare i libri di Knuth. Li trovi in tutte le librerie e probabilmente anche on line.
Se fai lo sviluppatore per professione, ti consiglio di comprarti una copia di questi libri, ti semplificano la vita.

[banryu79]

omissis...
Non ho visto il link di banryu79...

E' una pagina che illustra il cosidetto PNPOLY - Point Inclusion in Polygon Test.
Credo sia il metodo "canonico" per risolvere il problema; pare esista almeno dagli anni 70.

[71104]

No, il problema era: dati N punti del piano tracciare il poligono che li inglobi tutti e che abbia area massima. intendevi dire minima?

[cionci]

intendevi dire minima?
Credo massima...perché ad esempio metti di avere 5 punti:

. .
.
. .

Il poligono di area massima è un rettangolo, quello di area minima è composto da due triangoli.

[Abadir_82]

Credo massima...perché ad esempio metti di avere 5 punti:

. .
.
. .

Il poligono di area massima è un rettangolo, quello di area minima è composto da due triangoli.

Esatto, massima.

Purtroppo sono in Olanda per lavoro e libri di algoritmi non ne ho sottomano. Ad ogni modo tutto risolto :).

No no, sono qua solo per altri 3 mesi per il progetto Leonardo.

[71104]

Credo massima...perché ad esempio metti di avere 5 punti:

. .
.
. .

Il poligono di area massima è un rettangolo, quello di area minima è composto da due triangoli. anche questo è vero, ma se è di area massima allora il problema non è ben posto perché potrebbe trattarsi di un poligono arbitrariamente grande e non avrebbe senso. bisognerebbe specificare che gli angoli del poligono devono essere un sottoinsieme dei punti dati (magari era specificato nel post cancellato).

[banryu79]

Ecco un altro link utile per gli interessati --> Point In Polygon Strategies (http://tog.acm.org/editors/erich/ptinpoly/)
[link presente nella pagina web di cui ho postato il ink nel post #6]

[sottovento]

E' una pagina che illustra il cosidetto PNPOLY - Point Inclusion in Polygon Test.
Credo sia il metodo "canonico" per risolvere il problema; pare esista almeno dagli anni 70.
Allora probabilmente stiamo parlando dello stesso algoritmo. Scusa il mio inutile intervento :rolleyes:

[banryu79]

Allora probabilmente stiamo parlando dello stesso algoritmo. Scusa il mio inutile intervento :rolleyes:
Non è stato inutile, e ogni intervento e testimonianza di conoscenza è benaccetto :)

[Mirkolo]

Ora ho capito cosa intendevi nell'altro topic quando parlavi di ordinamento dei punti :) Meglio tardi che mai..
C'ho pensato su un attimo pure io e penso che l'ideale sia definire una funzione di costo come combinazione lineare di area e perimetro.
Generare una lista di triangoli che coprono tutta la lista di punti e che non intersecano tra di loro. Calcolare l'area come somma delle aree dei triangoli e il perimetro come somma delle lunghezze dei lati che appartengono a un solo triangolo. Poi valutare l'eliminazione dei triangoli che portano a un miglioramento della funzione di costo a patto che ogni vertice appartenga ad almeno due tringoli diversi. Alla fine elencare in ordine solo i lati che appartengono a un solo triangolo. Intuitivamente io avrei fatto così.
Lavorare solo con l'area o solo con il perimetro porta a qualche incoveniente in alcuni casi particolari (vedi perimetri frastagliati per minimizzare l'area o aree troppo grandi per minimizzare il perimetro).
Ciao

[marco.r]

ll calcolo dell' inviluppo convesso e' un problema noto e piu' che studiato.
Algoritmi per la sua soluzione si dovrebbero trovare in un comune testo di algoritmi (appunto) oppure, se uno e' pigro, su wikipedia (http://en.wikipedia.org/wiki/Graham_scan) :p