Newsgroup: it.discussioni.ingegneria
Titolo: Il punto appartiene ad una figura chiusa?

Nessuno sa dove reperire algoritmi per determinare se un punto
appartiene o meno ad un figura chiusa costruita solo da linee e
archi?
Grazie 1000.
Miche.

 archi?
Prova a cercare "convex hull" (inviluppo convesso) con Google.
Ciao
-- 
"In theory, practice and theory are the same;
in practice, they never are."

Ho dato uno sguardo proprio ieri sera a quell'algoritmo, ma
non fa per me, perche` io potrei avere anche figure chiuse concave.
Come pensavi di risolvere il mio problema con quell'algoritmo???
Ciao e grazie.
Miche.


 Come pensavi di risolvere il mio problema con quell'algoritmo???
Ci provo: nota la figura (cioe' le coordinate dei punti che compongono
gli estremi) racchiudi i punti all'interno di una circonferenza che ha
per diametro la distanza massima fra tutte le coppie di punti. Prendi
un punto esterno alla circonferenza e verifichi che questo segmento
non intersechi alcun lato della figura originaria (ci sono casi limite
di tangenza in un punto e di intersezioni multiple, ma dovrebbero
essere eliminabili: con un numero pari di intersezioni il punto e'
fuori, altrimenti e' dentro).
Non credo ci sia un algoritmo pronto ma dovresti riuscire a recuperare
i vari "pezzi".
Ti avviso che la geometria computazionale non e' altro che un hobby
per me, quindi potrei aver scritto delle emerite stronzate.
Dai un'occhiata a "computational geometry", sempre con Google, ma
attento a non perderti   ;-)


 ha scritto nel messaggio
news:9uo2ct$9hfn8$1...@ID-87012.news.dfncis.de...

il problema e' abbastanza complesso e (a meno che tu non identifichi una
classe ottimizzata di algoritmi applicabili alle tue figure) temo dovrai
rassegnarti ad impiegare la procedura generale (valida per piu' o meno tutte
le figure) :
-considerare in sequenza tutti i lati della figura (assumo qui' di avere a
che fare con segmenti di retta ma il metodo puo' essere facilmente esteso)
-per ogni lato definire la posizione interna ed esterna (sono possibili
diverse soluzioni, funzione del problema), quindi verificare se si trova
dentro o fuori
-se per almeno due lati risulta interno allora e' interno alla figura.

 dentro o fuori
Ecco.
Qui mi trovo indifficolta`.
Come faccio a sapere se la posizione e` interna o esterna.
Io so solo che la figura e` chiusa, ma per ogni lato non riesco
a dire dove si trova l'interno e l'esterno.
Hai idea di come farlo?
Ciao e grazie 1000.
Miche.

 Miche.
putroppo anche qui' la soluzione generale e' piuttosto complessa,
identifica un segmento nel perimetro della figura per cui conosci quale e'
la regione interna e quella esterna, quindi percorri tutto il perimetro
mantenendo la stessa disposizione delle regioni,
spero tuttavia ti sia possibile trovare qualcosa di piu' semplice :-)

 ha scritto nel messaggio
news:9uo2ct$9hfn8$1...@ID-87012.news.dfncis.de...


 > Miche.
identifica un segmento nel perimetro della figura per cui conosci quale e'
la regione interna e quella esterna, quindi percorri tutto il perimetro
mantenendo la stessa disposizione delle regioni,
spero ti sia possibile trovare qualcosa di semplice,
ad esempio considera il seguente codice :
bool TestPolygon(int x, int y, point *p, int n )
// x,y point to test
// *p (array) of vertices of irregular region (x0,y0) (x1,y1) (x2,y2) ....
//  n number of vertices
{
bool inside = FALSE;
int i, j;
for ( i = 0, j = n-1; i < n; j = i++ ) {
if ( ( ((p[i].X <= x) && (x < p[j].X)) || ((p[j].X <= x) && (x < p[i].X)) )
&& (y < (p[j].Y - p[i].Y) * (x - p[i].X) / (p[j].X - p[i].X) + p[i].Y)
)  inside = !inside;
}
return( inside);
}

Miche.
Ciao e 73-51 de Tartaruga .
.oO-=> TARTARUGA (* Gabriele *) <=-Oo.
E-Mail: 
ru...@libero.it
Packet CB: 
http://www.geocities.com/ita490/
Astronomy: 
http://www.geocities.com/rugabri/
"Chi dorme non piglia pesci, ma chi non dorme, alla fin fine...muore..."
(C) Tartaruga 1999 ;-)

>Miche.
Occhio ai punti che stanno esattamente sui vertici: fai un controllo a
priori, perchè altrimenti ti ritrovi con delle singolarità nel calcolo
degli angoli ;-)


 -per conoscere il seno usi il prodotto vettoriale
Penso di calcolarmi l'angolo per ogni segmento con l'inverso del cos.
Grazie 1000.
Ciao, Miche.

Ciao, Miche.


 averlo letto su qualche NG, probabilmente quello di MatLab ;-)
Da quanto ho capito l'algoritmo funziona solo per figure piane, a me è capitato
durante il
 periodo di tesi di dover verificare se un punto appartiene o meno ad un volume
chiuso (risolto poi con un metodo poco elegante e poco efficace basato su reti
neurali
che mi dava solo la probabilità che tale punto appartenesse al volume).
C' è un algoritmo anche per questo caso sicuramente più complesso???
Attenzione!!! Il volume non era una sfera o un cubo ma di una forma qualsiasi 
chiusa (il problema sorgeva già nel definire in modo matematico il volume
stesso).
Grazie, Salvatore
-- 
Posted from  [217.59.175.113] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 stesso).
Cazzarola!!!!
Tu sei gia` avanti. Addirittura il 3D???
Anche a me in futuro servira` la soluzione di questo problema, ma per
adesso non ci provo nemmeno.
Se il tuo lavoro era per una tesi allora penso che tu abbia gia` guardato
su tutta la letteratura che riguarda la geometria computazionale.
In caso contrario... tentar non nuoce ;-))))
Coso mai riuscissi a vedere un po' di luce in questa oscurita`, butta un
fischio.
Ciao, Miche.

Grazie, Salvatore


 degli angoli ;-)
guarda che il test basato sulla somma degli angoli  e' il sistema piu' lento
e generalmente viene sconsigliato per impieghi nella grafica,
vedi
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/
per maggiori informazioni,
un algoritmo molto valido e' quello riportato nel precedente post a firma
Roberto P.

Roberto P.
Non dubito che il metodo che ho riportato non sia ottimizzato...poi
ognuno usa algoritmi diversi a seconda delle esigenze. Se devo farlo
girare 2 volte č inutile ottimizzarlo. Se devo farlo girare in
continuazione, allora cercherņ il top in termini di velocitą. Come al
solito č inutile comprarsi l'idromassaggio per farsi un bagno solo ;-)


 Ciao e 73-51 de Tartaruga .
Ho scritto principalmente per segnalare una pagina (vedi mio precedente
messaggio)  in cui l'argomento e' trattato in modo (a mio parere)
sufficientemente accurato, a dire il vero non mi e' chiaro , dalla lettura
dei messaggi, se la richiesta fosse relativa alla creazione di codice (e in
questo caso vale la nota relativa all'altro algoritmo che e' suggerito nella
maggior parte di FAQ dedicate all'argomento) o preparazione di una tesina (e
in questo caso sono sicuramente interessanti i metodi come quello da te
esposto), c'e' stata anche (mi sembra) una richiesta di metodi operanti in
3D, il metodo esposto (2D) puo' essere trasportato in 3D (sostituiendo i
tests sui segmenti con tests sui piani)
ciao :-)

 tests sui segmenti con tests sui piani)
La domanda  iniziale, fatta da me, chiedeva un algoritmo per poi farci un
programma.
La richiesta era per il 2D, ma come dici tu, quell'algoritmo dei segmenti
va bene anche per il 3D se trasportato sui piano.
Siccome mi servira` in futuro, nessuno sa dove si trattano queste
cose in modo piu` pratico che teorico???
Ciao e grazie.
Miche.

 cose in modo piu` pratico che teorico???
intanto ti suggerirei di leggerti la faq del newsgroup
comp.graphics.algorithms :
http://www.faqs.org/faqs/graphics/algorithms-faq/
li troverai dei riferimenti a codici e letture che ti potranno aiutare.