Cómo probar si un punto está dentro de un polígono convexo en coordenadas enteras en 2D?

Question

El polígono se da como una lista de objetos Vector2I (coordenadas 2 dimensional, entero). ¿Cómo puedo probar si un punto dado está dentro? Todas las implementaciones que he encontrado en la web fallan por algún contraejemplo trivial. Realmente parece ser difícil escribir una aplicación correcta. El idioma no importa lo que yo quiero yo mismo puerto.

Answer 1

Si es convexa, de manera trivial para comprobar es que el punto que se está en el mismo lado de todos los segmentos (si atravesado en el mismo orden).

Puede comprobar que con facilidad con el producto vectorial (ya que es proporcional al coseno del ángulo formado entre el segmento y el punto, aquellos con signo positivo pondrían en el lado derecho y aquellos con signo negativo en el lado izquierdo ).

Aquí está el código 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

The Casting Ray o métodos de bobinado son los más comunes para este problema. Vea la artículo de Wikipedia para más detalles.

Además, la salida este página para una solución bien documentado en C.

Answer 3

Si el polígono es convexo, a continuación, en C #, la siguiente implementa el " prueba si siempre en el mismo lado ", y corre a lo sumo en O (n de puntos de polígono):

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

La función pointPolygonTest en OpenCV "determina si el punto está dentro de un contorno, exterior, o se encuentra en un borde": http://docs.opencv.org/modules/imgproc /doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

Answer 5

La respuesta de FORTRAN casi funcionó para mí, si me encontré con que tenía que traducir el polígono de modo que el punto que está probando es el mismo que el origen. Aquí está el código JavaScript que escribí para hacer este trabajo:

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

la forma en que sé es algo por el estilo.

a escoger un punto en algún lugar fuera del polígono puede estar muy lejos de la geometría. a continuación, se dibuja una línea desde este punto. me refiero a crear una ecuación de línea con estos dos puntos.

a continuación, por cada línea en este polígono, se comprueba si se intersecan.

ellos suma de número de líneas intersectadas le dan que está dentro o no.

si es impar: en el interior

si es par: fuera

Answer 7

O del hombre que escribió el libro ver - la geometría de página

esta página , discute por qué regla de bobinado es generalmente mejor que cruce ray.

editar - En este momento esto no es Jospeh O'Rourke quien escribió el excelente libro Geometría Computacional en C , es Paul Bourke pero sigue siendo un muy, muy buena fuente de algoritmos de geometría.