Geo Fencing - point intérieur / extérieur du polygone

Question

J'aimerais déterminer un polygone et implémenter un algorithme permettant de vérifier si un point est à l'intérieur ou à l'extérieur du polygone.

Est-ce que quelqu'un sait s'il existe un exemple d'algorithme similaire?

Answer 1

Si je me souviens bien, l'algorithme consiste à tracer une ligne horizontale à travers votre point de test. Compter le nombre de lignes de du polygone que vous croisent pour atteindre votre point de vue.

Si la réponse est bizarre, vous êtes à l'intérieur. Si la réponse est la même, vous êtes à l'extérieur.

Edit: Ouais, ce qu' il dit (Wikipedia):

Answer 2

Code C #

 bool IsPointInPolygon(List<Loc> poly, Loc point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) 
                || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) 
                && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) 
                    / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))

            c = !c;
        }
    }

    return c;
}
 

Classe de loc

 public class Loc
{
    private double lt;
    private double lg;

    public double Lg
    {
        get { return lg; }
        set { lg = value; }
    }

    public double Lt
    {
        get { return lt; }
        set { lt = value; }
    }

    public Loc(double lt, double lg)
    {
        this.lt = lt;
        this.lg = lg;
    }
}
 

Answer 3

Il suffit de jeter un coup d’œil au problème du point-dans-polygone (PIP) .

Answer 4

Après recherche sur le web et d'essayer les différentes implémentations et le portage de C++, C#, j'ai finalement obtenu mon code de droit:

        public static bool PointInPolygon(LatLong p, List<LatLong> poly)
    {
        int n = poly.Count();

        poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon });
        LatLong[] v = poly.ToArray();

        int wn = 0;    // the winding 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].Lat <= p.Lat)
            {         // start y <= P.y
                if (v[i + 1].Lat > p.Lat)      // an upward crossing
                    if (isLeft(v[i], v[i + 1], p) > 0)  // P left of edge
                        ++wn;            // have a valid up intersect
            }
            else
            {                       // start y > P.y (no test needed)
                if (v[i + 1].Lat <= p.Lat)     // a downward crossing
                    if (isLeft(v[i], v[i + 1], p) < 0)  // P right of edge
                        --wn;            // have a valid down intersect
            }
        }
        if (wn != 0)
            return true;
        else
            return false;

    }

    private static int isLeft(LatLong P0, LatLong P1, LatLong P2)
    {
        double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat)
                - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat));
        if (calc > 0)
            return 1;
        else if (calc < 0)
            return -1;
        else
            return 0;
    }

Le isLeft fonction était de me donner des problèmes d'arrondi et j'ai passé des heures sans se rendre compte que je faisais la conversion de mal, alors pardonnez-moi pour le boiteux si le bloc à la fin de cette fonction.

BTW, c'est l'original du code et de l'article: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Answer 5

De loin la meilleure explication et la mise en œuvre peut être trouvé à Point Dans Le Polygone Numéro Du Bobinage De L'Inclusion

Il y a même une implémentation C++ à la fin de l', explique l'article. Ce site contient également quelques grands algorithmes/des solutions pour d'autres basées sur la géométrie des problèmes.

J'ai modifié et utilisé le C++ mise en œuvre et a également créé un C# de mise en œuvre. Vous voulez absolument utiliser le Numéro du Bobinage de l'algorithme car elle est plus précise que sur le bord de passage de l'algorithme et il est très rapide.