[C]Consigli su programmino in C su problema geometrico

[ArchangelInHell]

Buonasera a tutti!Volevo sapere se potete darmi qualche consiglio(meglio se prima possibile)su questo problema che il mio professore mi ha detto di fare.
Allora..il problema è..data una griglia(considerata come una matrice di poligoni)geografica data con coordinate LAT e LON(latitudine e longitudine)di tipo float e rispettivamente di dimensioni 300x200,assegnato in modo random un punto trovare in quale poligono si trova il punto.Il punto campione lo assegniamo noi.Inoltre ci ha consigliato di considerare sia LAT che LON come matrici nei quali inserire rispettivamente le coordinate x e y.
Quindi il problema è testare tutti i poligoni che formano la griglia e dire quindi in quale poligono è il punto.Già di base possiamo sfruttare un algoritmo che serve per vedere se un punto è in un poligono e ve lo posto:

// cn_PnPoly(): crossing number test for a point in a polygon
//      Input:   P = a point,
//               V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
//      Return:  0 = outside, 1 = inside
// This code is patterned after [Franklin, 2000]
int
cn_PnPoly( Point P, Point* V, int n )
{
    int    cn = 0;    // the crossing number counter

    // loop through all edges of the polygon
    for (int i=0; i<n; i++) {    // edge from V[i] to V[i+1]
       if (((V[i].y <= P.y) && (V[i+1].y > P.y))    // an upward crossing
        || ((V[i].y > P.y) && (V[i+1].y <= P.y))) { // a downward crossing
            // compute the actual edge-ray intersect x-coordinate
            float vt = (float)(P.y - V[i].y) / (V[i+1].y - V[i].y);
            if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect
                ++cn;   // a valid crossing of y=P.y right of P.x
        }
    }
    return (cn&1);    // 0 if even (out), and 1 if odd (in)

}

Inoltre,oltre a definire il punto come una struttura e a definire le matrici LAT e LON,molto gentilmente un amico del mio gruppo mi ha consigliato un modo per passare la matrice sempre nel verso positivo e non considerare numeri molto alti in questo modo:

#include <stdio.h>

#define N 10
#define M 10

typedef struct {float x,y;}Point;

int main(int argc,char* argv[])
{
 flat lat[M][N];
 flat lon[M][N];
 flat latoff=0.0;
 flat lonoff=0.0;

 for (int i=0;i<M;i++)
 {
  for(int j=0;j<N;j++)
  {
   if(i != 0)
   {
    latoff=lat[i-1][j]
   }
   lat[i][j]=latoff+random()%5;
   lon[i][j]=lonoff+random()%5;
   lonoff=lon[i][j];
  }
  lonoff=0;
 }
}

Ora l'unico problema è che dovrei definire i vertici dei poligoni,mi potete dare qualche consiglio?

[wizard_at]

ciao.
ti consiglio di mettere il codice tra CODE.
[code].....[\CODE] (con la sbarra nell'altro senso)

[banryu79]

Originariamente inviato da ArchangelInHell

Ora l'unico problema è che dovrei definire i vertici dei poligoni,mi potete dare qualche consiglio?

Definirei un Poligono come un Vector di puntatori a struttura Punto [ordinati in senso antiorario]