Como testar se um ponto está dentro de um polígono convexo em 2D inteiro coordenadas?

Question

O polígono é dada como uma lista de objectos Vector2I (2 dimensional, coordenadas de número inteiro). Como posso testar se um determinado ponto está dentro? Todas as implementações que eu encontrei na web falhar por algum trivial contra-exemplo. Ele realmente parece ser difícil de escrever uma aplicação correcta. O idioma não importa, eu vou porta-lo eu mesmo.

Answer 1

Se é convexo, uma maneira trivial para verificar é que o ponto está colocando no mesmo lado de todos os segmentos (se atravessado na mesma ordem).

Você pode verificar se facilmente com o produto cruzado (como é proporcional ao co-seno do ângulo formado entre o segmento eo ponto, aqueles com sinal positivo colocaria no lado direito e aqueles com sinal negativo no lado esquerdo ).

Aqui está o código em 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

O Ray Fundição ou métodos de enrolamento são as mais comuns para este problema. Veja a Wikipedia artigo para mais detalhes.

Além disso, confira este página para um solução bem documentado em C.

Answer 3

Se o polígono é convexo, então em C #, os seguintes instrumentos do " teste se sempre no mesmo lado " método e executado no máximo em O (n de pontos de polígonos):

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;
}

Answer 4

A função pointPolygonTest em openCV "determina se o ponto está dentro de um contorno, fora, ou encontra-se em uma vantagem": http://docs.opencv.org/modules/imgproc /doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

Answer 5

A resposta de fortran quase funcionou para mim, exceto que eu descobri que eu tinha para traduzir o polígono de modo que o ponto que você está testando é o mesmo que a origem. Aqui é o JavaScript que eu escrevi para fazer este trabalho:

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 6

a maneira que eu sei é algo parecido.

você escolhe um lugar ponto fora do polígono pode ser longe da geometria. então você desenhar uma linha a partir deste ponto. Quer dizer que você criar uma equação de linha com estes dois pontos.

, em seguida, para cada linha neste polígono, você verificar se eles se cruzam.

-los soma do número de linhas entrecortadas dar-lhe que está dentro ou não.

Se é estranho: dentro

se é mesmo: outside

Answer 7

Ou do homem que escreveu o livro Sé - geometria página

desta página , ele discute regra por enrolamento é geralmente melhor do que cruzamento ray.

Editar - Desculpe isso não é Joseph O'Rourke que escreveu o excelente livro Computational Geometry em C , é Paul Bourke mas ainda um muito, muito boa fonte de algoritmos de geometria.