[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.