[c#]Algoritmo per verificare se un punto è contenuto in 1 poligono concavo e convesso

[3nigma666]

Ciao a tutti, spero possa essere utile questa soluzione che ho trovato per verificare se un punto è contenuto o meno all'interno di un poligono, sia che esso sia concavo sia convesso. Io l'ho applicato a google maps, ovvero dato un poligono disegnato con le coordinate gps , verifico se un punto è all'interno o meno.

ecco il codice:


public class puntoAppartienePoligono
{
#region Variables
Dictionary<int, MarkerColorato> ListaVertici;
#endregion
#region 2 versione

public puntoAppartienePoligono(Dictionary <int, MarkerColorato> Lista)
{
ListaVertici = Lista;
}

public bool IsInside(MarkerColorato punto)
{
CultureInfo usCulture = new CultureInfo("en-US");

/* The points creating the polygon. */
float[] x = new float[ListaVertici.Count];
float[] y = new float[ListaVertici.Count];
float x1,x2;

/* The coordinates of the point */
float px, py;
px = float.Parse(punto.X,usCulture);
py = float.Parse(punto.Y,usCulture);

/* How many times the ray crosses a line-segment */
int crossings = 0;

///* Coordinates of the points */
for (int i = 0; i < ListaVertici.Count;i++)
{
x[i] = float.Parse(ListaVertici.ElementAt(i).Value.X,usCulture);
y[i] = float.Parse(ListaVertici.ElementAt(i).Value.Y,usCulture);
}

/* Iterate through each line */
//for ( int i = 0; i < 8; i++ ){
for ( int i = 0; i < ListaVertici.Count-1; i++ )
{
/* This is done to ensure that we get the same result when
the line goes from left to right and right to left */
if (x[i] < x[(i + 1) % (ListaVertici.Count - 1)])
{
x1 = x[i];
x2 = x[(i + 1) % (ListaVertici.Count - 1)];
}
else
{
x1 = x[(i + 1) % (ListaVertici.Count - 1)];
x2 = x[i];
}

/* First check if the ray is possible to cross the line */
if ( px > x1 && px <= x2 && ( py < y[i] || py <= y[(i+1)%8] ) )
{
//static const float eps = 0.000001;
const float eps = (float)0.000001;

/* Calculate the equation of the line */
float dx = x[(i + 1) % (ListaVertici.Count - 1)] - x[i];
float dy = y[(i + 1) % (ListaVertici.Count - 1)] - y[i];
float k;

//if ( fabs(dx) < eps ){
if (Math.Abs(dx) < eps)
k = float.PositiveInfinity;
else
k = dy/dx;

float m = y[i] - k * x[i];

/* Find if the ray crosses the line */
float y2 = k * px + m;
if ( py <= y2 )
crossings++;
}
}

//printf("The point is crossing %d lines", crossings);
if (crossings % 2 == 1)
return true;
else
return false;
}
#endregion
}


come potete vedere nel costruttore gli passo un tipo MarkerColorato, che altro non è che una classe che ho definito io.

Ecco sotto al definizione della classe:



public class MarkerColorato
{
public string X;
public string Y;
public string Localita;
public static string[] colors = { "black", "brown", "purple", "yellow", "blue", "gray", "orange", "red", "white" };
public static string coloreOk = "green";
public string color;
public int areaID;
string label;

public MarkerColorato(string x, string y)
{
X = x;
Y = y;
label = RandomHelper.RandomString(1, false);
UseRandomColor();
}

public MarkerColorato(string x, string y, string localita)
{
X = x;
Y = y;
Localita = localita;
label = RandomHelper.RandomString(1, false);
UseRandomColor();
}

public MarkerColorato(string x, string y, int id)
{
X = x;
Y = y;
areaID = id;
label = RandomHelper.RandomString(1, false);
UseRandomColor();
}


/// <summary>Assegna a questo marker un colore random</summary>
public void UseRandomColor()
{
color = colors[RandomHelper.RandomNumber(0, 8)];
}

public string urlMarker()
{
string urlMarkerBase = "&markers=";
string urlLabel = "|label:";
string urlChiusuraLabel = "|";
string urlColor = "color:"+color;
string urlCoordinateMarker = X + "," + Y;
return urlMarkerBase + urlColor + urlLabel + label + urlChiusuraLabel + urlCoordinateMarker;
}


}



spero possa essere utile a qualcuno.