Newsgroup: it.comp.lang.c++
Titolo: Punto dentro o punto fuori???

COme faccio a capire se un punto si trova dentro o fuori la una linea??
Nel mio caso ho un array (m_iaDrawVer) che contiene i punti(i pari le x e i
dispari le y) di una linea chiusa ma non riesco a trovare con precisione un
modo per decidere se un punto č dentro o fuori. Io ho fatto cosě se qualcuno
mi puň dare un suggerimento grazie. In pratica ho provato a contare quante
volte la linea attraversa un a linea verticale al di sotto del punto.
Grazie per qualsiasi aiuto
int iIntersect=0;
 int liPos,liCount=m_iaDrawVert.GetSize();
  for (liPos=0;liPos<liCount-2;liPos+=2)
  {
   if (((m_iaDrawVert[liPos]>pt.x) && (m_iaDrawVert[liPos+2]<pt.x)) ||
((m_iaDrawVert[liPos]<pt.x) && (m_iaDrawVert[liPos+2]>pt.x)))
   {
    if ((m_iaDrawVert[liPos+1]<pt.y) && (m_iaDrawVert[liPos+3]<pt.y))
     iIntersect++;
    else
    {
     double m;
m=((float)((m_iaDrawVert[liPos+3]-m_iaDrawVert[liPos+1])/(m_iaDrawVert[liPos
+2]-m_iaDrawVert[liPos])));
     int q;
     q=m_iaDrawVert[liPos+1];
     if(((m*(-m_iaDrawVert[liPos]+pt.x))+q)<pt.y)
     iIntersect++;
     }
   }
  }
  return ((iIntersect%2));

 del punto.
Se riesci ad ottenere l'equazione della funzione che disegna la linea chiusa 
è semplicissimo: dato P(x1, y1) e y = f(x), puoi controllare se f(x1) == 
y1.
Altrimenti nin zo. ;-) Un modo empirico potrebbe essere calcolare le rette 
di equazione tra due punti successivi e vedere se il tuo punto appartiene. 
Esempio: calcoli la retta f1(x) date le coordinate di P1 e P2 e verifichi 
se P vi appartiene, in caso negativo calcoli f2(x) date le coordinate di P2 
e P3 e così via. Però non funziona molto bene se la linea è curva.
-- 
Andrea Bergia - studente          Linux Registred User #281550
Per favore non mandatemi allegati in Word o PowerPoint.
Si veda 
http://www.fsf.org/philosophy/no-word-attachments.html


    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.
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra


Avevo gia' fatto, a mie spese la scoperta che l'algoritmo nel libro di
Sedgewick "Algorithms in C", per vedere se un punto era interno a un
poligono (convesso o concavo), era sballato.
Avevo usato quell'algoritmo per realizzare delle "zone di guardia" di
un'applicazione per radar navali, per vedere quando una barca entrava in una
zona poligonale costruita dall'utente.
Ebbene in fase di test, c'erano dei casi particolari in cui si aveva falso
allarme o al contrario c'erano allarmi non rilevati per altri casi
particolari.
Avevo poi trovato nel web un buon algoritmo, visto che cercare di
costruirselo da soli era assai complesso, specialmente nel caso di poligoni
concavi.
Non ricordo piu' pero' l'indirizzo dove trovare questo algoritmo e non so se
l'algoritmo postato da Antonio Cuni sia valido anche per poligoni concavi.
Maurus

 modo per decidere se un punto č dentro o fuori.
Umh... forse non ho capito bene il problema, ma:
Visto che tu nell'array hai le coordinate dei punti del segmento, non
sarebbe sufficiente cercare se la x del punto appartiene a qualche posizione
pari dell'array, e se c'č, controllare che nella posizione successiva alla x
trovata, ci sia un valore uguale a quello della y del punto. Es.:
#include <iostream>
struct Punto {
    double x, y;
};
double segmento[] = {1.2, 2.4, 3.2, 4.2, 5.3, 7.9};
bool dentro (Punto p, double* seg) {
    for (int i = 0; i < 6; i++)
        if (i % 2 == 0)
            if ((seg[i] == p.x) && (seg[i + 1] == p.y))
                return true;
   return false;
};
int main () {
    Punto point;
    point.x = 3.2;
    point.y = 4.2;
    if (dentro (point, segmento))
        std::cout << "Il punto č interno al segmento" << std::endl;
    return 0;
}
Ciao
--
DigitalShock

 ha scritto nel messaggio
news:SvTq9.33130$%M1.8...@twister2.libero.it...

Considerando una semiretta con origine nel punto, se i segmenti intersecati
sono in numero dispari il punto č all' interno del poligono. Nel caso che il
punto stia su un segmento del perimetro devi decidere/sapere se il perimetro
appartiene o no al poligono. Nel caso la semiretta passi esattamente su un
vertice determinato da due segmenti  č necessario utilizzare un altra
semiretta.
------
Sergio Bianchi

Ma non vuole semplicemente sapere se un punto appartiene al segmento?
Ciao
--
DigitalShock

Ah, ho visto ora che avevi scritto "linea chiusa" intendendo "spezzata
chiusa"...
Cmq, la mia funziona la puoi usare per vedere se il punto si trova o meno
nel perimetro, nel caso questo ti serva...
ciao
--
DigitalShock