Newsgroup: it.comp.lang.c
Titolo: AIUTOOOOO

ciao a tutti,
ho bisogno di un aiuto. Qualcuno sa indicarmi un algorotmo per determinare se un punto (x,y) cade all'interno di un poligono di cui si conoscono i vertici (x1,y1) (x2,y2).. (xn,yn). Un grazie a tutti!
-- 
Posted from [194.243.146.2] by way of 
mta33-acc.tin.it
 [212.216.176.86] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 ha scritto nel messaggio
news:20010514104715.PZVW13790.fep33-svc.tin.it@[127.0.0.1]...


se a Sx .... Out.
Ti sei dimenticato di dire che quella regola vale solo se il
poligono e' convesso... inoltre "se a Sx" e' un po' vago...
piu' giusto e' dire "se esiste almeno un segmento per cui il
punto si trova a Sx allora e' OUT".
Un algoritmo standard valido per poligoni semplicemente
connessi (senza buchi) e' il seguente...
  int inside(int x,int y,             /* Punto */
             int n,int px[],int py[]) /* Poligono */
  {
    int i=n-1,j=0,k=0;
    while(j<n)
    {
      /* Considero il segmento Pi->Pj */
      if ((y>=py[i] && y<py[j]) || (y>=py[j] && y<py[i]))
        /* Il segmento attraversa la y del punto */
        if ( px[i]+(y-py[i])*(px[j]-px[i])/(py[j]-py[i]) > x )
          /* L'ascissa di intersezione e' maggiore di x */
          k++;
      /* Passa al prossimo segmento */
      i=j++;
    }
    return k&1;
  }
In pratica consiste nel contare tutti i lati del poligono che
attraversano la linea che va da (x,y) a (+inf,y): se questo
numero e' dispari ci si trova dentro al poligono, se invece e'
pari allora ci si trova fuori. L'unica cosa a cui bisogna
prestare un po' di attenzione sono i casi "limite" (quando
la linea "tocca" un vertice del poligono).
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff


Non mi pare ci siano problemi se il poligono è convesso. La regola del
camminamento funziona fu poligoni di qualsiasi forma...
Ciao
Giulio

camminamento funziona fu poligoni di qualsiasi forma...
La regola che hai formulato in maniera abbastanza imprecisa
vale *SOLO* se il poligono e' convesso... immagina infatti
questo caso:
    _______________
   |      ____     |
   |     |    |    |
   |  x  |    |    |
   |_____|    |____|
Ovviamente il punto "x" e' interno al poligono ma si
trova dalla "parte sbagliata" quando consideri il lato
inferiore del corridoio orizzontale e quello di sinistra
della parte di destra. L'algoritmo del camminamento per
come lo hai descritto direbbe quindi che il punto "x" e'
esterno al poligono.
Nel caso di poligoni convessi l'algoritmo invece vale...
equivale a verificare che il punto si trovi nell'intersezione
dei semipiani che definiscono il poligono. Un poligono non
convesso non e' rappresentabile come intersezione di semipiani
e quindi il sistema non funziona.



Hai ragione, si vede che sono un po' arrugginito... ma con gualche piccolo
aggiustamento credo che si potrebbe scrivere comunque qualcosa di sensato anche
partendo da questo metodo... lo dico senza avere chiara la soluzione...
Scusa se sono stato insistente...
Ciao
Giulio


partendo da questo metodo... lo dico senza avere chiara la soluzione...
Non credo sia cosi' semplice. Il problema con i poligoni generici e'
che e' impossibile stabilire se un punto e' interno o esterno se non
si sono analizzati tutti i lati.
*Qualunque* algoritmo che risponda "il punto e' fuori" oppure
"il punto e' dentro" prima di aver preso in considerazione tutti
i lati non puo' funzionare ...
Con i convessi il discorso e' profondamente diverso (e piu' semplice).
Andrea
