Comment tester si un point est à l'intérieur d'un polygone convexe en 2D entier coordonnées?

les méthodes de coulée ou D'enroulement par Rayon sont les plus courantes pour ce problème. Voir le article de Wikipedia pour plus de détails.

aussi, Consultez cette page pour une solution bien documentée en C.

si le polygone est convexe, alors en C#, le suivant met en œuvre le " test si toujours du même côté "méthode, et fonctionne au plus à O (n des points du polygone):

public static bool IsInConvexPolygon(Point testPoint, List<Point> polygon)
{
    //Check if a triangle or higher n-gon
    Debug.Assert(polygon.Length >= 3);

    //n>2 Keep track of cross product sign changes
    var pos = 0;
    var neg = 0;

    for (var i = 0; i < polygon.Count; i++)
    {
        //If point is in the polygon
        if (polygon[i] == testPoint)
            return true;

        //Form a segment between the i'th point
        var x1 = polygon[i].X;
        var y1 = polygon[i].Y;

        //And the i+1'th, or if i is the last, with the first point
        var i2 = i < polygon.Count - 1 ? i + 1 : 0;

        var x2 = polygon[i2].X;
        var y2 = polygon[i2].Y;

        var x = testPoint.X;
        var y = testPoint.Y;

        //Compute the cross product
        var d = (x - x1)*(y2 - y1) - (y - y1)*(x2 - x1);

        if (d > 0) pos++;
        if (d < 0) neg++;

        //If the sign changes, then point is outside
        if (pos > 0 && neg > 0)
            return false;
    }

    //If no change in direction, then on same side of all segments, and thus inside
    return true;
}

la fonction pointPolygonTest dans openCV " détermine si le point est à l'intérieur d'un contour, à l'extérieur, ou se trouve sur un bord": http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

la réponse de fortran a presque fonctionné pour moi sauf que j'ai trouvé que je devais traduire le polygone de sorte que le point que vous testez est la même que l'origine. Voici le JavaScript que j'ai écrit pour faire ce travail:

function Vec2(x, y) {
  return [x, y]
}
Vec2.nsub = function (v1, v2) {
  return Vec2(v1[0]-v2[0], v1[1]-v2[1])
}
// aka the "scalar cross product"
Vec2.perpdot = function (v1, v2) {
  return v1[0]*v2[1] - v1[1]*v2[0]
}

// Determine if a point is inside a polygon.
//
// point     - A Vec2 (2-element Array).
// polyVerts - Array of Vec2's (2-element Arrays). The vertices that make
//             up the polygon, in clockwise order around the polygon.
//
function coordsAreInside(point, polyVerts) {
  var i, len, v1, v2, edge, x
  // First translate the polygon so that `point` is the origin. Then, for each
  // edge, get the angle between two vectors: 1) the edge vector and 2) the
  // vector of the first vertex of the edge. If all of the angles are the same
  // sign (which is negative since they will be counter-clockwise) then the
  // point is inside the polygon; otherwise, the point is outside.
  for (i = 0, len = polyVerts.length; i < len; i++) {
    v1 = Vec2.nsub(polyVerts[i], point)
    v2 = Vec2.nsub(polyVerts[i+1 > len-1 ? 0 : i+1], point)
    edge = Vec2.nsub(v1, v2)
    // Note that we could also do this by using the normal + dot product
    x = Vec2.perpdot(edge, v1)
    // If the point lies directly on an edge then count it as in the polygon
    if (x < 0) { return false }
  }
  return true
}

la façon dont je le sais est quelque chose comme ça.

vous choisissez un point à l'extérieur du polygone, il peut être loin de la géométrie. ensuite, vous dessinez une ligne à partir de ce point. je veux dire que vous créez une équation linéaire avec ces deux points.

ensuite pour chaque ligne dans ce polygone, vous vérifiez si elles se croisent.

la somme du nombre de lignes croisées vous donne qu'il est à l'intérieur ou pas.

s'il est impair: à l'intérieur

s'il est pair : à l'extérieur

Ou de l'homme qui a écrit le livre de voir - géométrie de la page

spécifiquement cette page , il explique pourquoi la règle d'enroulement est généralement meilleure que Ray crossing.

edit - Désolé, ce n'est pas Joseph O'Rourke qui a écrit l'excellent livre de Calcul de la Géométrie dans C , c'est Paul Bourke, mais encore une très très bonne source de la géométrie algorithmique.