Point dans le Polygone aka test de collision

Question

Quel est votre meilleur, le plus élégant 2D "point à l'intérieur du polygone" ou d'un Polygone.contient(p:Point) algorithme?

Edit: Il peut y avoir des réponses différentes pour des flotteurs vs entiers. L'objectif principal est la vitesse.

Answer 1

Pour les graphismes, je n'avais jamais aller avec des Entiers. De nombreux Systèmes d'exploitation utiliser des Entiers pour la peinture de l'INTERFACE utilisateur (les pixels sont ints, après tout), mais Mac OS X par exemple utilise des float pour tout (il parle de points. Un point peut se traduire par un pixel, mais en fonction de la résolution de l'écran, il peut traduire à quoi que ce soit d'autre, mais un pixel et si la résolution est très élevée d'un moniteur, en théorie, un pixel peut se traduire par un demi-point, donc 1.5/1.5 peut être un autre pixel de 1/1 et 2/2). Cependant, je n'ai jamais remarqué que les Mac de l'Isu sont beaucoup plus lents que les autres de l'Isu. Après tout 3D (OpenGL ou Direct3D) fonctionne également avec des flotteurs de tous les temps et moderne bibliothèques graphiques peuvent très souvent prendre avantage de la puissance élevée Gpu d'un système sans même vous en rendre compte (comme un GPU peut également accélérer 2D de la peinture, pas de la 3D; 2D est seulement un sous-ensemble de la 3D, de considérer que la 2D en 3D où le Z les coordonnées sont toujours à 0 par exemple).

Maintenant, vous avez dit que la vitesse est votre préoccupation principale, d'accord, allons-y pour la vitesse. Avant d'exécuter un algorithme sophistiqué, faites d'abord un test simple. Créer un axe aligné boîte englobante autour de votre polygone. C'est très facile, rapide et peut déjà sûr vous des tonnes de temps CPU. Comment cela fonctionne? Itérer sur tous les points du polygone (chaque point X/Y) et de trouver les valeurs min/max de X et de Y. E. g. vous avez les points (9/1), (4/3), (2/7), (8/2), (3/6). Xmin est de 2, Xmax est 9, Ymin est 1 et Ymax est 7. Maintenant, vous savez qu'aucun point au sein de votre polygone peut jamais avoir une valeur de x plus petit que 2 et supérieur à 9, à aucun moment, ne peut avoir une valeur inférieure à 1 et supérieur à 7. De cette façon, vous pouvez exclure rapidement de nombreux points n'étant pas à l'intérieur de votre polygone:

// p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
    // Definitely not within the polygon!
}

C'est le premier test à exécuter sur n'importe quel point. Si ce test déjà exclut le point du polygone (même si c'est un très gros test!), alors il ne sert à rien de courir tous les autres tests. Comme vous pouvez le voir, ce test est ultra rapide.

Si ce test ne sera pas exclure le point, il est dans l'axe aligné boîte englobante, mais cela ne signifie pas qu'il est dans le polygone; il signifie seulement qu'il pourrait être dans le polygone. Ce dont nous avons besoin prochain est un plus sophistiqué de test pour vérifier si le point est vraiment dans le polygone ou juste à l'intérieur de la boîte englobante. Il ya un couple de façons de comment cela peut être calculée. Il a également fait une énorme différence, c'est le polygone peut avoir des trous ou si elle est solide. Voici des exemples de solides (un convexe, l'un concave):

Et voici une avec un trou:

Le vert a un trou au milieu!

Le plus simple est d'utiliser la projection de rayons, car il peut gérer tous les polygones indiqué ci-dessus correctement, aucun traitement particulier n'est nécessaire et il fournit toujours une bonne vitesse. L'idée de l'algorithme est assez simple: Dessinez un virtuel ray à partir de n'importe où à l'extérieur du polygone de votre point de vue et de compter combien de fois il frappe un côté du polygone. Si le nombre de résultats est le même, c'est à l'extérieur du polygone, si c'est bizarre, c'est à l'intérieur.

Le numéro du bobinage algorithme est plus précis pour les points étant très, très, très proche d'un polygone ligne; ray casting peut échouer ici en raison de la précision et de l'arrondissement des problèmes, mais d'enroulement nombre est beaucoup plus lente et si un point est accidentellement détectés à l'extérieur du polygone si c'est tellement proche d'un polygone ligne, que votre œil ne peut même pas dire si c'est à l'intérieur ou à l'extérieur, est-ce vraiment un problème? Je ne pense pas, donc nous allons garder les choses simples.

Vous avez encore la boîte englobante de ci-dessus, vous vous souvenez? Bon, maintenant, disons que votre point est p (p.x/p.y). Votre ray susceptibles d'aller de

• (Xmin - e/p).y) pour (p.x/p.y) ou
• (p.x/p.y), (Xmax + e/p).y) ou
• (p.x/Ymin - e) (p.x/p.y) ou
• (p.x/p.y) pour (p.x/Ymax + e)

Il ne sera pas question. Choisissez ce qui sonne le mieux pour vous. Il est seulement important que le rayon commence certainement à l'extérieur du polygone et s'arrête au point.

Donc, qu'est-ce que e toute façon? Ainsi, e (en fait, epsilon) donne la boîte englobante certains rembourrage. Comme je l'ai dit, le ray-tracing échoue si on commence trop près d'un polygone ligne. Depuis la boîte englobante peut égaler le polygone (si le polygone est en fait un axe aligné rectangle, la boîte englobante est égal au polygone lui-même! Et le rayon serait de démarrer directement sur le polygone de côté). Quelle taille devrait vous choisir e? Pas trop grand. Il dépend du système de coordonnées de l'échelle que vous utilisez pour le dessin. Vous pouvez sélectionner e à 1.0, cependant, si votre polygones ont des coordonnées de beaucoup inférieure à 1.0, sélectionnez e à 0,001 peut être assez grande. Vous pouvez sélectionner e pour être toujours 1% de la taille des polygones, par exemple, lorsque, ayant un rayon de l'axe x, vous pouvez calculer e comme ceci:

e = ((Xmax - Xmin) / 100)

Maintenant que nous avons le rayon avec ses de début et de fin de coordonnées, le problème se déplace de "est le point dans le polygone" à "comment souvent croise le rayon d'un polygone côté". C'est pourquoi nous ne pouvons pas juste de travailler avec le polygone points comme avant (pour la boîte englobante), maintenant nous avons besoin de la réelle côtés. Un côté est toujours définie par deux points.

side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:

Vous avez besoin de tester le rayon à l'encontre de tous les côtés. Considérons le rayon d'être un vecteur et de chaque côté à un vecteur. Le rayon a frapper chaque côté exactement une fois ou jamais. Il ne peut pas frapper du même côté par deux fois (deux lignes dans l'espace 2D se coupent toujours exactement une fois, sauf si elles sont parallèles, dans ce cas, ils se croisent jamais. Cependant, puisque les vecteurs ont une longueur limitée, deux vecteurs peut ne pas être parallèles et ne se coupent).

// Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
    // Test if current side intersects with ray.
    // If yes, intersections++;
}
if ((intersections & 1) == 1) {
    // Inside of polygon
} else {
    // Outside of polygon
}

C'est très bien, mais comment voulez-vous tester si deux vecteurs se croisent? Voici le code en C (pas testé), cela devrait faire l'affaire:

#define NO 0
#define YES 1
#define COLLINEAR 2

int areIntersecting(
    float v1x1, float v1y1, float v1x2, float v1y2,
    float v2x1, float v2y1, float v2x2, float v2y2
) {
    float d1, d2;
    float a1, a2, b1, b2, c1, c2;

    // Convert vector 1 to a line (line 1) of infinite length.
    // We want the line in linear equation standard form: A*x + B*y + C = 0
    // See: http://en.wikipedia.org/wiki/Linear_equation
    a1 = v1y2 - v1y1;
    b1 = v1x1 - v1x2;
    c1 = (v1x2 * v1y1) - (v1x1 * v1y2);

    // Every point (x,y), that solves the equation above, is on the line,
    // every point that does not solve it, is either above or below the line.
    // We insert (x1,y1) and (x2,y2) of vector 2 into the equation above.
    d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
    d2 = (a1 * v2x2) + (b1 * v2y2) + c1;

    // If d1 and d2 both have the same sign, they are both on the same side of
    // our line 1 and in that case no intersection is possible. Careful, 0 is
    // a special case, that's why we don't test ">=" and "<=", but "<" and ">".
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    // We repeat everything above for vector 2.
    // We start by calculating line 2 in linear equation standard form.
    a2 = v2y2 - v2y1;
    b2 = v2x1 - v2x2;
    c2 = (v2x2 * v2y1) - (v2x1 * v2y2);

    // Calulate d1 and d2 again, this time using points of vector 1
    d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
    d2 = (a2 * v1x2) + (b2 * v1y2) + c2;

    // Again, if both have the same sign (and neither one is 0),
    // no intersection is possible.
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    // If we get here, only three possibilities are left. Either the two
    // vectors intersect in exactly one point or they are collinear
    // (they both lie both on the same infinite line), in which case they
    // may intersect in an infinite number of points or not at all.
    if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;

    // If they are not collinear, they must intersect in exactly one point.
    return YES;
}

Les valeurs d'entrée sont les deux points d'extrémité du vecteur 1 (x et y) et de vecteur 2 (x et y). Si vous avez 2 vecteurs, 4 points, 8 coordonnées. OUI et NON sont claires. OUI augmente intersections, AUCUNE ne fait rien. Qu'en est COLINÉAIRES? Il désigne à la fois les vecteurs se trouvent sur la même ligne infinie, en fonction de la position et de la longueur, ils ne coupe pas du tout ou ils se coupent en un nombre infini de points. Je ne suis pas absolument sûr de la façon de gérer ce cas, je ne voudrais pas compter comme intersection de toute façon. Eh bien, ce cas est plutôt rare dans la pratique de toute façon à cause de la virgule flottante, des erreurs d'arrondi; un code de meilleure qualité serait probablement pas de test pour l' == 0.0f , mais au lieu de quelque chose comme < epsilon, où epsilon est un assez petit nombre (ainsi, les petites erreurs d'arrondi ne conduisent à de mauvais résultats).

Dernier mais non le moindre: Si vous pouvez utiliser le matériel 3D pour résoudre le problème, oubliez ce qui est ci-dessus. Il est beaucoup plus rapide et beaucoup plus facile. Il suffit de laisser le GPU de faire tout le travail pour vous. Créer une peinture de la surface qui est hors de l'écran (de sorte que vous pouvez peindre en elle, sans qu'elle en apparaissant n'importe où sur l'écran). Remplir complètement avec la couleur noire. Maintenant, laissez-OpenGL ou Direct3D la peinture de votre polygone (ou même la totalité de votre polygones si vous voulez juste tester si le point est à l'intérieur de l'un d'eux, mais vous n'avez pas de soins pour laquelle) dans cette surface de dessin et de remplissage du polygone(s) avec une couleur différente, par exemple blanc. Pour vérifier si un point est à l'intérieur du polygone, d'obtenir la couleur de ce point à partir de la surface de dessin. C'est juste un O(1) mémoire de fetch. Si elle est blanche, c'est à l'intérieur, si c'est noir, c'est à l'extérieur. Facile, n'est-ce pas? Cette méthode sera payante si vous avez très peu de polygones (par exemple de 50 à 100), mais un putain de beaucoup de points de test (> 1000), dans ce cas, cette méthode est beaucoup plus rapide que n'importe quoi d'autre. Il ne sera un problème si votre surface de dessin doit être énorme parce que votre polygones. Si votre surface de dessin doit être de 100 MO ou plus pour faire les polygones ajustement, cette méthode peut devenir très lent (malgré le fait qu'il gaspille des tonnes de mémoire).

Answer 2

Je pense que le morceau de code suivant est la meilleure solution (prises à partir d' ici):

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

Arguments

• nvert: Nombre de sommets du polygone. S'il convient de répéter le premier sommet à la fin a été discuté dans l'article mentionné ci-dessus.
• vertx, très: les Tableaux contenant les x - et y-les coordonnées des sommets du polygone.
• testx, hargneuse: X et y les coordonnées du point d'essai.

C'est à la fois court et efficace, et qui fonctionne à la fois pour les polygones convexes et concaves. Comme suggéré précédemment, vous devriez vérifier le rectangle de délimitation de la première et de traiter polygone trous séparément.

L'idée derrière cela est assez simple. L'auteur la décrit comme suit:

Je lance un semi-infini ray horizontalement (augmentation de x, y fixe) à partir du point d'essai, et de compter le nombre d'arêtes qu'il traverse. À chaque passage, le rayon commute entre l'intérieur et l'extérieur. Cela s'appelle la Jordanie de la courbe de théorème.

Answer 3

Voici une version C# de la réponse donnée par nirg, qui vient de ce RPI professeur. Notez que l'utilisation du code à partir de ce RPI source nécessite l'attribution.

Un cadre de la boîte de contrôle a été ajouté dans la partie supérieure.

    public bool IsPointInPolygon( Point p, Point[] polygon )
    {
        double minX = polygon[ 0 ].X;
        double maxX = polygon[ 0 ].X;
        double minY = polygon[ 0 ].Y;
        double maxY = polygon[ 0 ].Y;
        for ( int i = 1 ; i < polygon.Length ; i++ )
        {
            Point q = polygon[ i ];
            minX = Math.Min( q.X, minX );
            maxX = Math.Max( q.X, maxX );
            minY = Math.Min( q.Y, minY );
            maxY = Math.Max( q.Y, maxY );
        }

        if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
        {
            return false;
        }

        // http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
        bool inside = false;
        for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
        {
            if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
                 p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
            {
                inside = !inside;
            }
        }

        return inside;
    }

Answer 4

Voici un JavaScript variante de la réponse de M. Katz basé sur Nirg son approche:

function pointIsInPoly(p, polygon) {
    var isInside = false;
    var minX = polygon[0].x, maxX = polygon[0].x;
    var minY = polygon[0].y, maxY = polygon[0].y;
    for (var n = 1; n < polygon.length; n++) {
        var q = polygon[n];
        minX = Math.min(q.x, minX);
        maxX = Math.max(q.x, maxX);
        minY = Math.min(q.y, minY);
        maxY = Math.max(q.y, maxY);
    }

    if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
        return false;
    }

    var i = 0, j = polygon.length - 1;
    for (i, j; i < polygon.length; j = i++) {
        if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) &&
                p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) {
            isInside = !isInside;
        }
    }

    return isInside;
}

Answer 5

Calculer le orientées somme des angles entre le point p et chacun des sommets du polygone. Si le total de l'angle orienté est de 360 degrés, le point est à l'intérieur. Si le total est de 0, le point est à l'extérieur.

J'aime cette méthode préférable car il est plus robuste et moins dépendante de la précision numérique.

Méthodes de calcul de planéité du nombre d'intersections sont limitées parce que vous pouvez "tirer" un apex lors du calcul du nombre d'intersections.

EDIT: Par ailleurs, cette méthode fonctionne avec concaves et convexes des polygones.