performance - كيف يمكنني تحديد ما إذا كانت نقطة ثنائية الأبعاد داخل Polygon؟




graphics collision-detection (20)

أحاول إنشاء نقطة ثنائية الأبعاد سريعة داخل خوارزمية مضلع ، لاستخدامها في اختبار النتائج (على سبيل المثال ، Polygon.contains(p:Point) ). اقتراحات لتقنيات فعالة سيكون موضع تقدير.


أدرك أن هذا أمر قديم ، ولكن هنا خوارزمية صب الشعاع منفذة في الكاكاو ، في حال كان أي شخص مهتم. لست متأكدا من أنها الطريقة الأكثر فعالية لفعل الأشياء ، ولكنها قد تساعد شخص ما على الخروج.

- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point
{
    NSBezierPath *currentPath = [path bezierPathByFlatteningPath];
    BOOL result;
    float aggregateX = 0; //I use these to calculate the centroid of the shape
    float aggregateY = 0;
    NSPoint firstPoint[1];
    [currentPath elementAtIndex:0 associatedPoints:firstPoint];
    float olderX = firstPoint[0].x;
    float olderY = firstPoint[0].y;
    NSPoint interPoint;
    int noOfIntersections = 0;

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];
        [currentPath elementAtIndex:n associatedPoints:points];
        aggregateX += points[0].x;
        aggregateY += points[0].y;
    }

    for (int n = 0; n < [currentPath elementCount]; n++) {
        NSPoint points[1];

        [currentPath elementAtIndex:n associatedPoints:points];
        //line equations in Ax + By = C form
        float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;  
        float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);
        float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);

        float _A_BAR = olderY - points[0].y;
        float _B_BAR = points[0].x - olderX;
        float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);

        float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);
        if (det != 0) {
            //intersection points with the edges
            float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det;
            float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det;
            interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);
            if (olderX <= points[0].x) {
                //doesn't matter in which direction the ray goes, so I send it right-ward.
                if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {  
                    noOfIntersections++;
                }
            } else {
                if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {
                     noOfIntersections++;
                } 
            }
        }
        olderX = points[0].x;
        olderY = points[0].y;
    }
    if (noOfIntersections % 2 == 0) {
        result = FALSE;
    } else {
        result = TRUE;
    }
    return result;
}

أعتقد أن الكود التالي هو أفضل حل (مأخوذ من here ):

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

الحجج

  • nvert : عدد الرؤوس في المضلع. ما إذا كان تكرار قمة الرأس الأولى في النهاية قد تمت مناقشته في المقالة المشار إليها أعلاه.
  • vertx، verty : Arrays يحتوي على إحداثيات x- و y من رؤوس المضلعات.
  • testx، testy : X-and y-coordinate of the test point.

انها قصيرة وفعالة وتعمل على حد سواء للمضلعات المحدبة والمقعرة. كما اقترح من قبل ، يجب عليك التحقق من المستطيل المحيط أولاً وعلاج الثقوب المضلعة بشكل منفصل.

الفكرة وراء هذا بسيطة جدا. يصفه المؤلف على النحو التالي:

أقوم بتشغيل شعاع نصف لا نهائي أفقياً (زيادة x ، ثابت y) من نقطة الاختبار ، وحساب عدد الحواف التي يعبرها. عند كل تقاطع ، يتحول الشعاع بين الداخل والخارج. وهذا ما يسمى نظرية منحنى الأردن.

يتحول المتغير c من 0 إلى 1 ومن 1 إلى 0 في كل مرة يتجاوز فيها الشعاع الأفقي أي حافة. لذلك فهو يتتبع بشكل أساسي ما إذا كان عدد الحواف المتقاطعتين مفرطًا أم فرديًا. 0 تعني حتى و 1 تعني غريب.


إن مقالة Eric Haines التي استشهد بها bobobobo ممتازة حقًا. ومما يثير الاهتمام بشكل خاص الجداول التي تقارن أداء الخوارزميات ؛ طريقة جمع زاوية سيئة حقا مقارنة مع الآخرين. ومن المثير للاهتمام أيضًا أن التحسينات مثل استخدام شبكة بحث لتقسيم المضلع إلى أقسام "داخل" و "خارج" يمكن أن تجعل الاختبار سريعًا بشكل لا يصدق حتى على المضلعات التي يبلغ حجمها أكثر من 1000 جانب.

على أي حال ، إنها أيام مبكرة ولكن تصويتي يذهب إلى طريقة "المعابر" ، وهو ما يصفه ميكي إلى حد كبير. ومع ذلك وجدت أنه أكثر وصفًا ومدونًا من قبل ديفيد بورك . أنا أحب أنه لا يوجد أي علم حساب المثلثات الحقيقي ، وأنه يعمل من أجل محدب ومقعر ، وأنه يؤدي بشكل جيد بقدر ما يزداد عدد الأضلاع.

بالمناسبة ، ها هي واحدة من جداول الأداء من مقال إريك هينز عن الاهتمام ، واختبارها على المضلعات العشوائية.

                       number of edges per polygon
                         3       4      10      100    1000
MacMartin               2.9     3.2     5.9     50.6    485
Crossings               3.1     3.4     6.8     60.0    624
Triangle Fan+edge sort  1.1     1.8     6.5     77.6    787
Triangle Fan            1.2     2.1     7.3     85.4    865
Barycentric             2.1     3.8    13.8    160.7   1665
Angle Summation        56.2    70.4   153.6   1403.8  14693

Grid (100x100)          1.5     1.5     1.6      2.1      9.8
Grid (20x20)            1.7     1.7     1.9      5.7     42.2
Bins (100)              1.8     1.9     2.7     15.1    117
Bins (20)               2.1     2.2     3.7     26.3    278

النسخة السريعة من إجابة nirg :

extension CGPoint {
    func isInsidePolygon(vertices: [CGPoint]) -> Bool {
        guard !vertices.isEmpty else { return false }
        var j = vertices.last!, c = false
        for i in vertices {
            let a = (i.y > y) != (j.y > y)
            let b = (x < (j.x - i.x) * (y - i.y) / (j.y - i.y) + i.x)
            if a && b { c = !c }
            j = i
        }
        return c
    }
}

حساب مجموع المنحى من الزوايا بين النقطة p وكل من apgon مضلعات. إذا كانت الزاوية الموجهة الإجمالية 360 درجة ، تكون النقطة في الداخل. إذا كان الإجمالي هو 0 ، فإن النقطة تكون خارج.

أنا أحب هذه الطريقة بشكل أفضل لأنها أكثر قوة وأقل اعتمادا على الدقة العددية.

تعد الطرق التي تحسب فيها التوزيع المتساوي لعدد التقاطعات محدودة نظرًا لأنه يمكنك "الوصول" إلى قمة أثناء حساب عدد التقاطعات.

تعديل: من جانب الطريق ، هذه الطريقة تعمل مع المضلعات المقعرة والمحدبة.

تحرير: لقد وجدت مؤخرا مقالة ويكيبيديا حول هذا الموضوع.


حقا مثل الحل نشرها Nirg وتحريرها بواسطة bobobobo. أنا فقط جعلت جافا سكريبت ودية ومقروءة أكثر قليلا لاستخدامي:

function insidePoly(poly, pointx, pointy) {
    var i, j;
    var inside = false;
    for (i = 0, j = poly.length - 1; i < poly.length; j = i++) {
        if(((poly[i].y > pointy) != (poly[j].y > pointy)) && (pointx < (poly[j].x-poly[i].x) * (pointy-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) ) inside = !inside;
    }
    return inside;
}

لقد قمت ببعض الأعمال في هذا الوقت عندما كنت باحثًا تحت إشراف Michael Stonebraker - أنت تعرف ، الأستاذ الذي جاء مع Ingres و PostgreSQL ، وما إلى ذلك.

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

إذا كنت تريد خوارزمية رائعة ، فابحث عن كود مصدر مشروع PostgreSQL مفتوح المصدر للعمل الجغرافي ...

أريد أن أشير إلى ذلك ، لم نحصل على أي فكرة عن اليمين مقابل اليسار (كما صارت مشكلة "داخل" مقابل "خارج" ...

تحديث

يوفر ارتباط BKB عددًا جيدًا من الخوارزميات المعقولة. كنت أعمل على مشاكل علوم الأرض ولذلك احتجت إلى حل يعمل في خطوط الطول والعرض ، ولديها مشكلة غريبة في العوائق - هل المنطقة داخل المنطقة الأصغر أو المنطقة الأكبر؟ الجواب هو أن "اتجاه" الأمور المتعلقة بالقمة مهم - إما أنه أعسر أو يمين ، وبهذه الطريقة يمكنك الإشارة إلى أي من المنطقتين بأنها "داخل" أي مضلع معين. على هذا النحو ، استخدم عملي حل الثلاثة المذكورة في تلك الصفحة.

بالإضافة إلى ذلك ، استخدمت عملي وظائف منفصلة لاختبارات "على الخط".

... منذ أن سأل شخص ما: توصلنا إلى أن اختبارات مربع الإحاطة كانت أفضل عندما يتجاوز عدد السماعات بعض الأرقام - قم باختبار سريع جدًا قبل إجراء الاختبار الأطول إذا لزم الأمر ... يتم إنشاء مربع إحاطة عن طريق أخذ أكبر س ، أصغر س ، أكبر ذ وأصغر ص ووضعها معا لجعل أربع نقاط من مربع ...

نصيحة أخرى للذين يتبعون: قمنا بكل حوسبة أكثر تطوراً و "تعتيمًا خفيفًا" في مساحة الشبكة ، كل ذلك في نقاط إيجابية على متن طائرة ثم أعيد إسقاطها مرة أخرى إلى خطوط الطول / العرض "الحقيقية" ، وبالتالي تجنب الأخطاء المحتملة التفاف حول عندما خط واحد عبر خط 180 ، وعند التعامل مع المناطق القطبية. عملت كبيرة!


نسخة Obj-C من رد nirg مع طريقة العينة لنقاط الاختبار. جواب نيرج كان جيداً بالنسبة لي

- (BOOL)isPointInPolygon:(NSArray *)vertices point:(CGPoint)test {
    NSUInteger nvert = [vertices count];
    NSInteger i, j, c = 0;
    CGPoint verti, vertj;

    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        verti = [(NSValue *)[vertices objectAtIndex:i] CGPointValue];
        vertj = [(NSValue *)[vertices objectAtIndex:j] CGPointValue];
        if (( (verti.y > test.y) != (vertj.y > test.y) ) &&
        ( test.x < ( vertj.x - verti.x ) * ( test.y - verti.y ) / ( vertj.y - verti.y ) + verti.x) )
            c = !c;
    }

    return (c ? YES : NO);
}

- (void)testPoint {

    NSArray *polygonVertices = [NSArray arrayWithObjects:
        [NSValue valueWithCGPoint:CGPointMake(13.5, 41.5)],
        [NSValue valueWithCGPoint:CGPointMake(42.5, 56.5)],
        [NSValue valueWithCGPoint:CGPointMake(39.5, 69.5)],
        [NSValue valueWithCGPoint:CGPointMake(42.5, 84.5)],
        [NSValue valueWithCGPoint:CGPointMake(13.5, 100.0)],
        [NSValue valueWithCGPoint:CGPointMake(6.0, 70.5)],
        nil
    ];

    CGPoint tappedPoint = CGPointMake(23.0, 70.0);

    if ([self isPointInPolygon:polygonVertices point:tappedPoint]) {
        NSLog(@"YES");
    } else {
        NSLog(@"NO");
    }
}


هنا نسخة C # من الإجابة التي قدمها nirg ، والتي تأتي من here . لاحظ أن استخدام الرمز من مصدر RPI يتطلب الإحالة.

تمت إضافة علامة اختيار مربع في الجزء العلوي. ومع ذلك ، وكما يشير جيمس براون ، فإن الشفرة الرئيسية تكاد تكون بالسرعة التي يفحص بها المربع المحيط نفسه ، لذلك يمكن أن يؤدي التحقق من المربع المحيط إلى إبطاء العملية الكلية ، في حالة أن معظم النقاط التي تقوم بفحصها هي داخل المربع المحيط. . لذا يمكنك ترك مربع الاختيار المحيط ، أو قد يكون البديل هو حساب مربعات مربعة للمضلعات في حالة عدم تغيير الشكل كثيرًا.

public bool IsPointInPolygon( Point p, Point[] polygon )
{
    double minX = polygon[ 0 ].X;
    double maxX = polygon[ 0 ].X;
    double minY = polygon[ 0 ].Y;
    double maxY = polygon[ 0 ].Y;
    for ( int i = 1 ; i < polygon.Length ; i++ )
    {
        Point q = polygon[ i ];
        minX = Math.Min( q.X, minX );
        maxX = Math.Max( q.X, maxX );
        minY = Math.Min( q.Y, minY );
        maxY = Math.Max( q.Y, maxY );
    }

    if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
    {
        return false;
    }

    // http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
    bool inside = false;
    for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
    {
        if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
             p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
        {
            inside = !inside;
        }
    }

    return inside;
}

هنا هو متغير جافا سكريبت من إجابة M. كاتز على أساس نهج Nirg:

function pointIsInPoly(p, polygon) {
    var isInside = false;
    var minX = polygon[0].x, maxX = polygon[0].x;
    var minY = polygon[0].y, maxY = polygon[0].y;
    for (var n = 1; n < polygon.length; n++) {
        var q = polygon[n];
        minX = Math.min(q.x, minX);
        maxX = Math.max(q.x, maxX);
        minY = Math.min(q.y, minY);
        maxY = Math.max(q.y, maxY);
    }

    if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
        return false;
    }

    var i = 0, j = polygon.length - 1;
    for (i, j; i < polygon.length; j = i++) {
        if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) &&
                p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) {
            isInside = !isInside;
        }
    }

    return isInside;
}

VBA VERSION:

Note: Remember that if your polygon is an area within a map that Latitude/Longitude are Y/X values as opposed to X/Y (Latitude = Y, Longitude = X) due to from what I understand are historical implications from way back when Longitude was not a measurement.

CLASS MODULE: CPoint

Private pXValue As Double
Private pYValue As Double

'''''X Value Property'''''

Public Property Get X() As Double
    X = pXValue
End Property

Public Property Let X(Value As Double)
    pXValue = Value
End Property

'''''Y Value Property'''''

Public Property Get Y() As Double
    Y = pYValue
End Property

Public Property Let Y(Value As Double)
    pYValue = Value
End Property

MODULE:

Public Function isPointInPolygon(p As CPoint, polygon() As CPoint) As Boolean

    Dim i As Integer
    Dim j As Integer
    Dim q As Object
    Dim minX As Double
    Dim maxX As Double
    Dim minY As Double
    Dim maxY As Double
    minX = polygon(0).X
    maxX = polygon(0).X
    minY = polygon(0).Y
    maxY = polygon(0).Y

    For i = 1 To UBound(polygon)
        Set q = polygon(i)
        minX = vbMin(q.X, minX)
        maxX = vbMax(q.X, maxX)
        minY = vbMin(q.Y, minY)
        maxY = vbMax(q.Y, maxY)
    Next i

    If p.X < minX Or p.X > maxX Or p.Y < minY Or p.Y > maxY Then
        isPointInPolygon = False
        Exit Function
    End If


    ' SOURCE: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

    isPointInPolygon = False
    i = 0
    j = UBound(polygon)

    Do While i < UBound(polygon) + 1
        If (polygon(i).Y > p.Y) Then
            If (polygon(j).Y < p.Y) Then
                If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then
                    isPointInPolygon = True
                    Exit Function
                End If
            End If
        ElseIf (polygon(i).Y < p.Y) Then
            If (polygon(j).Y > p.Y) Then
                If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then
                    isPointInPolygon = True
                    Exit Function
                End If
            End If
        End If
        j = i
        i = i + 1
    Loop   
End Function

Function vbMax(n1, n2) As Double
    vbMax = IIf(n1 > n2, n1, n2)
End Function

Function vbMin(n1, n2) As Double
    vbMin = IIf(n1 > n2, n2, n1)
End Function


Sub TestPointInPolygon()

    Dim i As Integer
    Dim InPolygon As Boolean

'   MARKER Object
    Dim p As CPoint
    Set p = New CPoint
    p.X = <ENTER X VALUE HERE>
    p.Y = <ENTER Y VALUE HERE>

'   POLYGON OBJECT
    Dim polygon() As CPoint
    ReDim polygon(<ENTER VALUE HERE>) 'Amount of vertices in polygon - 1
    For i = 0 To <ENTER VALUE HERE> 'Same value as above
       Set polygon(i) = New CPoint
       polygon(i).X = <ASSIGN X VALUE HERE> 'Source a list of values that can be looped through
       polgyon(i).Y = <ASSIGN Y VALUE HERE> 'Source a list of values that can be looped through
    Next i

    InPolygon = isPointInPolygon(p, polygon)
    MsgBox InPolygon

End Sub

C# version of nirg's answer is here: I'll just share the code. It may save someone some time.

public static bool IsPointInPolygon(IList<Point> polygon, Point testPoint) {
            bool result = false;
            int j = polygon.Count() - 1;
            for (int i = 0; i < polygon.Count(); i++) {
                if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) {
                    if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) {
                        result = !result;
                    }
                }
                j = i;
            }
            return result;
        }

Heres a point in polygon test in C that isn't using ray-casting. And it can work for overlapping areas (self intersections), see the use_holes argument.

/* math lib (defined below) */
static float dot_v2v2(const float a[2], const float b[2]);
static float angle_signed_v2v2(const float v1[2], const float v2[2]);
static void copy_v2_v2(float r[2], const float a[2]);

/* intersection function */
bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,
                         const bool use_holes)
{
    /* we do the angle rule, define that all added angles should be about zero or (2 * PI) */
    float angletot = 0.0;
    float fp1[2], fp2[2];
    unsigned int i;
    const float *p1, *p2;

    p1 = verts[nr - 1];

    /* first vector */
    fp1[0] = p1[0] - pt[0];
    fp1[1] = p1[1] - pt[1];

    for (i = 0; i < nr; i++) {
        p2 = verts[i];

        /* second vector */
        fp2[0] = p2[0] - pt[0];
        fp2[1] = p2[1] - pt[1];

        /* dot and angle and cross */
        angletot += angle_signed_v2v2(fp1, fp2);

        /* circulate */
        copy_v2_v2(fp1, fp2);
        p1 = p2;
    }

    angletot = fabsf(angletot);
    if (use_holes) {
        const float nested = floorf((angletot / (float)(M_PI * 2.0)) + 0.00001f);
        angletot -= nested * (float)(M_PI * 2.0);
        return (angletot > 4.0f) != ((int)nested % 2);
    }
    else {
        return (angletot > 4.0f);
    }
}

/* math lib */

static float dot_v2v2(const float a[2], const float b[2])
{
    return a[0] * b[0] + a[1] * b[1];
}

static float angle_signed_v2v2(const float v1[2], const float v2[2])
{
    const float perp_dot = (v1[1] * v2[0]) - (v1[0] * v2[1]);
    return atan2f(perp_dot, dot_v2v2(v1, v2));
}

static void copy_v2_v2(float r[2], const float a[2])
{
    r[0] = a[0];
    r[1] = a[1];
}

Note: this is one of the less optimal methods since it includes a lot of calls to atan2f , but it may be of interest to developers reading this thread (in my tests its ~23x slower then using the line intersection method).



Java Version:

public class Geocode {
    private float latitude;
    private float longitude;

    public Geocode() {
    }

    public Geocode(float latitude, float longitude) {
        this.latitude = latitude;
        this.longitude = longitude;
    }

    public float getLatitude() {
        return latitude;
    }

    public void setLatitude(float latitude) {
        this.latitude = latitude;
    }

    public float getLongitude() {
        return longitude;
    }

    public void setLongitude(float longitude) {
        this.longitude = longitude;
    }
}

public class GeoPolygon {
    private ArrayList<Geocode> points;

    public GeoPolygon() {
        this.points = new ArrayList<Geocode>();
    }

    public GeoPolygon(ArrayList<Geocode> points) {
        this.points = points;
    }

    public GeoPolygon add(Geocode geo) {
        points.add(geo);
        return this;
    }

    public boolean inside(Geocode geo) {
        int i, j;
        boolean c = false;
        for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {
            if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&
                    (geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))
                c = !c;
        }
        return c;
    }

}

Scala version of solution by nirg (assumes bounding rectangle pre-check is done separately):

def inside(p: Point, polygon: Array[Point], bounds: Bounds): Boolean = {

  val length = polygon.length

  @tailrec
  def oddIntersections(i: Int, j: Int, tracker: Boolean): Boolean = {
    if (i == length)
      tracker
    else {
      val intersects = (polygon(i).y > p.y) != (polygon(j).y > p.y) && p.x < (polygon(j).x - polygon(i).x) * (p.y - polygon(i).y) / (polygon(j).y - polygon(i).y) + polygon(i).x
      oddIntersections(i + 1, i, if (intersects) !tracker else tracker)
    }
  }

  oddIntersections(0, length - 1, tracker = false)
}

There is nothing more beutiful than an inductive definition of a problem. For the sake of completeness here you have a version in prolog which might also clarify the thoughs behind ray casting :

Based on the simulation of simplicity algorithm in here

Some helper predicates:

exor(A,B):- \+A,B;A,\+B.
in_range(Coordinate,CA,CB) :- exor((CA>Coordinate),(CB>Coordinate)).

inside(false).
inside(_,[_|[]]).
inside(X:Y, [X1:Y1,X2:Y2|R]) :- in_range(Y,Y1,Y2), X > ( ((X2-X1)*(Y-Y1))/(Y2-Y1) +      X1),toggle_ray, inside(X:Y, [X2:Y2|R]); inside(X:Y, [X2:Y2|R]).

get_line(_,_,[]).
get_line([XA:YA,XB:YB],[X1:Y1,X2:Y2|R]):- [XA:YA,XB:YB]=[X1:Y1,X2:Y2]; get_line([XA:YA,XB:YB],[X2:Y2|R]).

The equation of a line given 2 points A and B (Line(A,B)) is:

                    (YB-YA)
           Y - YA = ------- * (X - XA) 
                    (XB-YB) 

It is important that the direction of rotation for the line is setted to clock-wise for boundaries and anti-clock-wise for holes. We are going to check whether the point (X,Y), ie the tested point is at the left half-plane of our line (it is a matter of taste, it could also be the right side, but also the direction of boundaries lines has to be changed in that case), this is to project the ray from the point to the right (or left) and acknowledge the intersection with the line. We have chosen to project the ray in the horizontal direction (again it is a matter of taste, it could also be done in vertical with similar restrictions), so we have:

               (XB-XA)
           X < ------- * (Y - YA) + XA
               (YB-YA) 

Now we need to know if the point is at the left (or right) side of the line segment only, not the entire plane, so we need to restrict the search only to this segment, but this is easy since to be inside the segment only one point in the line can be higher than Y in the vertical axis. As this is a stronger restriction it needs to be the first to check, so we take first only those lines meeting this requirement and then check its possition. By the Jordan Curve theorem any ray projected to a polygon must intersect at an even number of lines. So we are done, we will throw the ray to the right and then everytime it intersects a line, toggle its state. However in our implementation we are goint to check the lenght of the bag of solutions meeting the given restrictions and decide the innership upon it. for each line in the polygon this have to be done.

is_left_half_plane(_,[],[],_).
is_left_half_plane(X:Y,[XA:YA,XB:YB], [[X1:Y1,X2:Y2]|R], Test) :- [XA:YA, XB:YB] =  [X1:Y1, X2:Y2], call(Test, X , (((XB - XA) * (Y - YA)) / (YB - YA) + XA)); 
                                                        is_left_half_plane(X:Y, [XA:YA, XB:YB], R, Test).

in_y_range_at_poly(Y,[XA:YA,XB:YB],Polygon) :- get_line([XA:YA,XB:YB],Polygon),  in_range(Y,YA,YB).
all_in_range(Coordinate,Polygon,Lines) :- aggregate(bag(Line),    in_y_range_at_poly(Coordinate,Line,Polygon), Lines).

traverses_ray(X:Y, Lines, Count) :- aggregate(bag(Line), is_left_half_plane(X:Y, Line, Lines, <), IntersectingLines), length(IntersectingLines, Count).

% This is the entry point predicate
inside_poly(X:Y,Polygon,Answer) :- all_in_range(Y,Polygon,Lines), traverses_ray(X:Y, Lines, Count), (1 is mod(Count,2)->Answer=inside;Answer=outside).

This only works for convex shapes, but Minkowski Portal Refinement, and GJK are also great options for testing if a point is in a polygon. You use minkowski subtraction to subtract the point from the polygon, then run those algorithms to see if the polygon contains the origin.

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

مزيد من المعلومات: http://xenocollide.snethen.com/mpr2d.html

أيضا ، الأحجار الكريمة برمجة اللعبة 7 يتحدث عن كيفية القيام بذلك في 3D (:


When using qt (Qt 4.3+), one can use QPolygon's function containsPoint


You can do this by checking if the area formed by connecting the desired point to the vertices of your polygon matches the area of the polygon itself.

Or you could check if the sum of the inner angles from your point to each pair of two consecutive polygon vertices to your check point sums to 360, but I have the feeling that the first option is quicker because it doesn't involve divisions nor calculations of inverse of trigonometric functions.

I don't know what happens if your polygon has a hole inside it but it seems to me that the main idea can be adapted to this situation

You can as well post the question in a math community. I bet they have one million ways of doing that







point-in-polygon