Déterminer si une existe coordonnée à l'intérieur d'un polygone

Question

Je travaille sur une application logicielle de suivi open source et geofence et je avoir un peu de difficulté à comprendre les mathématiques pour le geofencing.

Je dois déterminer si oui ou non une coordonnée existe à l'intérieur d'un polygone. Cependant, la partie la plus délicate est que le polygone n'a pas de numéro de série de côtés. Je dois être en mesure de calculer de cinquante côtés ou cinq côtés.

Ma recherche dit que la meilleure façon est de prendre mon point (que je vais appeler x) et un point en dehors du polygone (y appeler) et déterminer si la ligne ((xx, xy), (yx, aa) ) intersecte avec les limites du polygone. Si elle croise un nombre impair de fois, le point x doit être à l'intérieur du polygone.

Sachant que, cependant, je ne peux pas comprendre comment exprimer cela dans un algorithme .. Je vais évidemment besoin de boucle à travers les différentes lignes du polygone, mais la construction du chèque que je ne me échappe. Quelqu'un peut-il être utile? S'il vous plaît sais que je ne demande pas nécessairement la solution. Tout ce qui me permettra de le découvrir la réponse est une aide énorme.

Très apprécié.

Answer 1

Voir ici

Answer 2

Une clé ici est de réaliser que vous êtes libre de choisir un point Y que vous aimez. Un choix vraiment sympa est le point (xx, -infinity). En d'autres termes, le point directement en bas du point en question et infiniment loin. Maintenant, la question devient: combien des bords du polygone Croisez vos coordonnées X-dessous du point en question. Ainsi, seuls segments de ligne qui chevauchent la coordonnée X ont besoin d'être pris en considération.

Si le point est P = (x, y), et les points d'extrémité de segment sont P1 = (x1, y1) et P2 = (x2, y2) la coordonnée y du segment où elle traverse x est donnée par sy = (x-x1) * (y2-y1) / (x2-x1) + y1

Vérifier si sy

Il y a des problèmes subtils quand l'un des vertices du polygone est exactement la même position que le point y en question. Vous devrez faire attention à ce cas.

Answer 3

Justin,

Vous devrez peut-être mieux définir « en dehors du polygone » pour construire un segment.

Prenez le min & max de toutes les coordonnées x et y et la construction d'un rectangle (xmin, ymin), (Xmax, Ymin), (Xmax, Ymax), (Xmin, Ymax). Tout point en dehors du rectangle serait certainement en dehors du polygone - continuent alors que d'autres ont montré ci-dessus. Chaque segment du polygone et de la ligne de construction est définie par une équation y = ax + b et, pour chaque segment, une série XLO et xhi. Votre ligne soit construit traverse un segment dans la plage ou non. Autrement dit, la solution de deux équations simultanées dans l'intervalle de segment existe ou non. Il suffit de compter le nombre de solutions qui existent pour obtenir le nombre d'intersections.

Answer 4

Je suppose que vous êtes dans un plan (2D).

• Calculer les pentes de chaque côté (dans un système de coordonnées) et la pente de la droite à partir du point X au point Y (ligne XY).
• Pour tous les côtés où la pente ne correspond pas à la pente de XY, calculer le point d'intersection.
• Pour chaque point, déterminer si le point d'intersection est le segment de ligne XY et le segment de ligne définissant le côté. Dans ce cas, vous avez traversé ce côté. (Cochez les coordonnées de l'intersection et de voir si les deux composantes x et y sont compris dans la plage de valeurs pour chaque segment de ligne.)
• Comptez le nombre de passages à niveau, et vous avez votre réponse.

Answer 5

Calculer la nombre enroulement du polygone et le point.

Answer 6

Essayez ceci,

public static bool PointinPolygon( Point[] points, Point p )
    {
        bool result = false;

        for( int i = 0; i < points.Length - 1; i++ )
        {
            if( ( ( ( points[ i + 1 ].Y <= p.Y ) && ( p.Y < points[ i ].Y ) ) || ( ( points[ i ].Y <= p.Y ) && ( p.Y < points[ i + 1 ].Y ) ) ) && ( p.X < ( points[ i ].X - points[ i + 1 ].X ) * ( p.Y - points[ i + 1 ].Y ) / ( points[ i ].Y - points[ i + 1 ].Y ) + points[ i + 1 ].X ) )
            {
                result = !result;
            }
        }
        return result;
    }