Newsgroup: it.comp.lang.c++
Titolo: ricerca di un algoritmo

Qualcuno sa suggerirmi come fare a determinare la posizione di un punto
rispetto ad un poligono? Quindi vedere se il punto sta all'interno o
all'esterno del poligono??
Grazie Alessandra  (
ales...@tin.it
)

 wrote in message
8lhsqs$blu$1...@nslave1.tin.it...

In linea di principio considerando una semiretta che parte dal punto e va
verso l' infinito se il numero di intersezioni con i lati del poligono è
pari il punto è esterno, se dispari il punto è interno. Occorre poi prestare
attenzione al fatto che la semiretta non attraversi un vertice ( due
segmenti attraversati anzichè uno) o che il punto stia su un lato del
poligono (a scelta del programmatore considerare se il perimetro è incluso o
escluso dall' insieme)
Sergio Bianchi


Chiedo scusa per la fretta nella risposta, ho riletto dopo e ho visto che mi
sono espresso male, nell' attraversare un vertice possono esservi anche piů
di  due segmenti attraversati (un numero qualsiasi) in funzione della
geometria del poligono e si tratta quindi di un caso da evitare in linea di
principio in quanto č impossibile analizzare ogni possibile forma.
Sergio Bianchi


    with some minor modifications for speed.  It returns 1 for strictly
    interior points, 0 for strictly exterior, and 0 or 1 for points on
    the boundary.  The boundary behavior is complex but determined;
    in particular, for a partition of a region into polygons, each point
    is "in" exactly one polygon.  See the references below for more detail.
    int pnpoly(int npol, float *xp, float *yp, float x, float y)
    {
      int i, j, c = 0;
      for (i = 0, j = npol-1; i < npol; j = i++) {
        if ((((yp[i]<=y) && (y<yp[j])) ||
             ((yp[j]<=y) && (y<yp[i]))) &&
            (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
          c = !c;
      }
      return c;
    }
    The code may be further accelerated, at some loss in clarity, by
    avoiding the central computation when the inequality can be deduced,
    and by replacing the division by a multiplication for those processors
    with slow divides.  For code that distinguishes strictly interior
    points from those on the boundary, see [O'Rourke (C)] pp. 239-245.
Vincenzo
-- 
-----------------------------------------------------------------------
Vincenzo  Positano                	  email: 
posi...@ifc.pi.cnr.it
 
Institute of Clinical Physiology  (IFC - CNR)              Pisa (Italy)
http://NMR-aurora.ifc.pi.cnr.it/positano
=======================================================================


Ciao,
questo argomento qui è OT, poiché si parla di c++; il newsgroup corretto
sarebbe comp.graphics.algorithms.
Comunque quando si tratta do computer graphics sono sempre pronto ad aiutare
:)
Ci sono 2 risposte che ti posso dare:
1) se guardi nelle faq di comp.graphics.algorithms
(
http://www.faqs.org/faqs/graphics/algorithms-faq/
), la domanda 2.03 è 'How
do I find if a point lies within a polygon?', e trovi anche la risposta.
2) Vai su 
http://www.ecse.rpi.edu/Homepages/wrf/geom/pnpoly.html
 dove
l'autore della risposta nelle FAQ spiega dettagliatamente come funziona
l'algoritmo e come si implementa efficientemente.
riciao,
Raffaele (RDA)

> Qualcuno sa suggerirmi come fare a determinare la posizione di un punto
e, giusto per completare, trovi su IoProgrammo di questo mese un
articolo che tratta, tra gli altri, anche proprio questo argomento.
-- 
Topoldo  
www.pianetalinux.com
(Grazie a Dio, sono ateo)