كيفية اختبار ما إذا كانت هناك نقطة داخل مضلع محدب في الإحداثيات الصحيحة 2D؟

Question

يتم إعطاء المضلع كقائمة من كائنات Vector2i (الإحداثيات 2 الأبعاد، عدد صحيح). كيف يمكنني اختبار ما إذا كانت نقطة معينة في الداخل؟ تفشل جميع التطبيقات التي وجدتها على الويب على مثال مضاد تافهة. يبدو أنه من الصعب حقا كتابة التنفيذ الصحيح. اللغة لا تهم كما سأكره بنفسي.

Answer 1

إذا كان محددا، فستكون طريقة تافهة للتحقق من ذلك هي أن النقطة توضع على نفس الجانب من جميع القطاعات (إذا تم اجتيازها بنفس الترتيب).

يمكنك التحقق من ذلك بسهولة مع المنتج المتقاطع (كما يتناسب مع جيب التمام الرياضي من الزاوية المشكلة بين القطاع والنقطة، فإن أولئك الذين لديهم علامة إيجابية سوف يضعون على الجانب الأيمن وأولئك الذين لديهم علامة سلبية على الجانب الأيسر).

هنا هو الرمز في بيثون:

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

تعد أساليب RAY CASTING أو WINDING هي الأكثر شيوعا لهذه المشكلة. انظر ويكيبيديا المادة للتفاصيل.

أيضا، تحقق من هذه الصفحة للحصول على حل موثق جيدا في C.

Answer 3

إذا كان المضلع محددا، فعندئذ في C #، فإن الإجراءات التالية "اختبار إذا كان دائما على نفس الجانب"الطريقة، وتشغيلها على الأكثر في O (N من نقاط المضلع):

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

تقوم وظيفة PointPolygontest في OpenCV "بتحديد ما إذا كانت النقطة داخل محيط أو خارج أو تقع على حافة":http://docs.opencv.org/modules/imgproc/doc/sultural_analysis_and_shape_descriptors.htmlllightlight=pointpolygongongongongongontest.

Answer 5

عملت إجابة Fortran تقريبا بالنسبة لي إلا أنني وجدت أن علي ترجمة المضلع بحيث تكون النقطة التي تختبرها هي نفس الأصل. هنا هو جافا سكريبت كتبت لجعل هذا العمل:

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

الطريقة التي أعرفها هي شيء من هذا القبيل.

يمكنك اختيار نقطة في مكان ما خارج المضلع قد يكون بعيدا عن الهندسة. ثم ترسم خطا من هذه النقطة. أعني أنك تنشئ معادلة سطر مع هاتين النقطتين.

ثم لكل سطر في هذا المضلع، يمكنك التحقق مما إذا كانت تتقاطع.

مجموع عدد خطوط التقاطع يمنحك أنه داخل أم لا.

إذا كان غريبا: الداخل

إذا كان الأمر كذلك: خارج

Answer 7

أو من الرجل الذي كتب الكتاب انظر - هندسة الصفحة

خاصة هذه الصفحة, ، يناقش لماذا تحكم متعرج أفضل عموما من عبور الأشعة.

تحرير - آسف هذا ليس كذلك Jospeh O'Rourke. الذي كتب الكتاب الممتاز الهندسة الحسابية في ج, ، إنه بول بورك ولكن لا يزال مصدرا جيدا للغاية لخوارزميات الهندسة.