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

Question

Le polygone est donnée à une liste d'objets Vector2I (2 dimensions, coordonnées entières). Comment puis-je vérifier si un point donné est à l'intérieur? Toutes les implémentations i sur le web échouent pour une contre-exemple trivial. Il semble vraiment être difficile d'écrire une mise en œuvre correcte. La langue n'a pas d'importance que je vais le port moi-même il.

Answer 1

Si elle est convexe, de manière triviale pour vérifier qu'il est que le point est couché sur le même côté de tous les segments (si traversés dans le même ordre).

Vous pouvez vérifier que facilement avec le produit vectoriel (comme elle est proportionnelle au cosinus de l'angle formé entre le segment et le point, ceux avec un signe positif serait couché sur le côté droit et ceux avec un signe négatif sur le côté gauche ).

Voici le code en Python:

RIGHT = "RIGHT"
LEFT = "LEFT"

def inside_convex_polygon(point, vertices):
    previous_side = None
    n_vertices = len(vertices)
    for n in xrange(n_vertices):
        a, b = vertices[n], vertices[(n+1)%n_vertices]
        affine_segment = v_sub(b, a)
        affine_point = v_sub(point, a)
        current_side = get_side(affine_segment, affine_point)
        if current_side is None:
            return False #outside or over an edge
        elif previous_side is None: #first segment
            previous_side = current_side
        elif previous_side != current_side:
            return False
    return True

def get_side(a, b):
    x = x_product(a, b)
    if x < 0:
        return LEFT
    elif x > 0: 
        return RIGHT
    else:
        return None

def v_sub(a, b):
    return (a[0]-b[0], a[1]-b[1])

def x_product(a, b):
    return a[0]*b[1]-a[1]*b[0]

Answer 2

Le casting Ray ou méthodes Winding sont les plus courantes pour ce problème. Voir Wikipedia article pour plus de détails.

Vous pouvez également consulter cette page pour solution bien documentée dans C.

Answer 3

Si le polygone est convexe, puis en C #, ce qui suit met en œuvre la "

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 je trouve que je devais traduire le polygone afin que le point que vous testez est le 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 sais est quelque chose comme ça.

vous choisissez un point quelque part en dehors du polygone, il peut être loin de la géométrie. alors vous tracez une ligne de ce point. Je veux dire que vous créez une équation en ligne avec ces deux points.

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

les somme de nombre de lignes entrecroisées vous donner est à l'intérieur ou non.

si elle est impair: à l'intérieur

si elle est même: à l'extérieur

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

cette page , il discute règle pourquoi enroulement est généralement meilleure que passage des rayons.

modifier - Désolé, ce n'est pas Jospeh O'Rourke qui a écrit la excellent livre Géométrie Algorithmique en C , il est Paul Bourke, mais encore très très bonne source d'algorithmes géométriques.

Answer 4

Answer 5

Answer 6

Answer 7

Answer 8

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 »:

Answer 9

La réponse de Fortran a presque fonctionné pour moi sauf que je trouve que je devais traduire le polygone afin que le point que vous testez est le 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
}

Answer 10

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

vous choisissez un point quelque part en dehors du polygone, il peut être loin de la géométrie. alors vous tracez une ligne de ce point. Je veux dire que vous créez une équation en ligne avec ces deux points.

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

les somme de nombre de lignes entrecroisées vous donner est à l'intérieur ou non.

si elle est impair: à l'intérieur

si elle est même: à l'extérieur

Answer 11

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

cette page , il discute règle pourquoi enroulement est généralement meilleure que passage des rayons.

modifier - Désolé, ce n'est pas Jospeh O'Rourke qui a écrit la excellent livre Géométrie Algorithmique en C , il est Paul Bourke, mais encore très très bonne source d'algorithmes géométriques.