Wie zu testen, ob sich ein Punkt innerhalb eines konvexen Polygon ist in 2D ganzzahligen Koordinaten?

Question

Das Polygon wird als eine Liste von Objekten gegeben Vector2I (2 dimensional, ganzzahligen Koordinaten). Wie kann ich testen, ob ein gegebener Punkt innerhalb? Alle Implementierungen i im Web gefunden scheitern einige triviale Gegenbeispiel. Es scheint wirklich schwer zu sein, eine korrekte Umsetzung zu schreiben. Die Sprache spielt keine Rolle, wie ich mich Port, es wird.

Answer 1

Wenn sie konvex ist, eine triviale Weise, sie zu überprüfen, besteht darin, dass der Punkt auf der gleichen Seite aller Segmente legt (wenn in der gleichen Reihenfolge durchlaufen).

, die leicht mit dem Kreuzprodukt überprüfen kann (wie es zum Kosinus des Winkels zwischen dem Segment und dem Punkt, die mit positivem Vorzeichen würden liegen auf der rechten Seite und die mit negativen Vorzeichen auf der linken Seite ausgebildet ist proportional ).

Hier ist der Code 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

Die Ray Casting oder Wickelverfahren sind die häufigsten für dieses Problem. Sehen Sie sich die Wikipedia-Artikel .

Überprüfen Sie auch, Diese Seite für eine gut dokumentierte Lösung in C.

Answer 3

Wenn das Polygon konvex ist, dann in C # implementiert die folgenden die " Test, wenn immer auf der gleichen Seite " Verfahren, und läuft bei O (n Polygonpunkte) höchstens:

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

Die pointPolygonTest Funktion in OpenCV „bestimmt, ob der Punkt innerhalb einer Kontur liegt, außerhalb oder auf einer Kante liegt“: http://docs.opencv.org/modules/imgproc /doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

Answer 5

Fortran Antwort für mich fast gearbeitet, außer ich fand ich das Polygon zu übersetzen hatte, so dass der Punkt, Sie testen die gleiche wie die Herkunft ist. Hier ist das JavaScript, das ich schrieb, diese Arbeit zu machen:

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

die Art, wie ich weiß, ist so ähnlich.

Sie irgendwo außerhalb des Polygons wählen Sie einen Punkt aus der Geometrie weit weg sein kann. dann ziehen Sie eine Linie von diesem Punkt. Ich meine, Sie mit diesen beiden Punkten eine Linie Gleichung erstellen.

dann für jede Zeile in diesem Polygon, Sie prüfen, ob sie sich überschneiden.

sie Summe der Anzahl der geschnittenen Linien geben Sie es im Inneren ist oder nicht.

Wenn es ungerade ist: innerhalb

, wenn es auch: außerhalb

Answer 7

Oder von dem Mann, der das Buch schrieb sehen - Geometrie Seite

diese Seite , er beschreibt, warum Windungsregel im allgemeinen besser als Strahlüberquerung ist.

Bearbeiten - Leider ist dies nicht Jospeh O'Rourke , der schrieb die ausgezeichnetes Buch Computational Geometry in C , dann ist es Paul Bourke, aber immer noch ein sehr, sehr gute Quelle für Geometrie-Algorithmen.