Come verificare se un punto è all'interno di un poligono convesso in 2D coordinate intere?

Question

Il poligono è data come un elenco di oggetti Vector2I (coordinate 2 dimensionale, intero). Come faccio a testare se un dato punto è dentro? Tutte le implementazioni che ho trovato sul web non riescono per qualche banale esempio contrario. Sembra davvero essere difficile scrivere una corretta attuazione. La lingua non importa come io vi porto io stesso esso.

Answer 1

Se è convessa, un modo banale per verificare è che il punto si posa sullo stesso lato di tutti i segmenti (se percorsa nello stesso ordine).

È possibile verificare che facilmente con il prodotto vettoriale (come è proporzionale al coseno dell'angolo formato tra il segmento e il punto, quelli con segno positivo sarebbe posare sul lato destro e quelli con segno negativo sul lato sinistro ).

Ecco il codice in 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

Il Casting Ray o metodi di avvolgimento sono le più comuni per questo problema. Vedere la Wikipedia articolo per i dettagli.

Inoltre, Check out questa pagina per un soluzione ben documentata in C.

Answer 3

Se il poligono è convesso, poi in C #, il seguente implementa il " test se sempre sullo stesso lato ", e funziona al massimo a O (n di punti poligono):

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 funzione pointPolygonTest in OpenCV "determina se il punto è all'interno di un contorno, fuori, o si trova su un bordo": http://docs.opencv.org/modules/imgproc /doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

Answer 5

La risposta di FORTRAN quasi ha funzionato per me tranne che ho trovato ho dovuto tradurre il poligono in modo che il punto che si sta testando è la stessa come l'origine. Ecco il JavaScript che ho scritto a fare questo lavoro:

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

il modo in cui ciò che so è una cosa del genere.

si sceglie un punto da qualche parte al di fuori del poligono può essere lontano dalla geometria. poi si disegna una linea da questo punto. voglio dire si crea un'equazione linea con questi due punti.

poi per ogni linea in questo poligono, si controlla se si intersecano.

li somma del numero di linee intersecate darvi è dentro o no.

Se è strano: al suo interno

se è ancora: fuori

Answer 7

O da l'uomo che ha scritto il libro vedere - pagina geometria

questa pagina , discute regola perché avvolgimento è generalmente migliore di attraversamento dei raggi.

modifica - Spiacente, questo non è Jospeh O'Rourke che ha scritto il eccellente libro Geometria computazionale in C , è Paul Bourke, ma ancora molto molto buona fonte di algoritmi di geometria.