1
\$\begingroup\$

I've been using an algorithm (http://wiki.unity3d.com/index.php/PolyContainsPoint) to tell me if a point is inside a polygon... in fact a few variants (here and here) but they all come back the same. Shapes with (0,0) vertices fail.

enter image description here

Here's the function:

private bool IsPointInPolygon(Vector2[] polyPoints, Vector2 p)
{
    int j = polyPoints.Length-1; 
    bool inside = false; 
    for (int i = 0; i < polyPoints.Length; j = i++) { 
        if ( ((polyPoints[i].y <= p.y && p.y < polyPoints[j].y) || (polyPoints[j].y <= p.y && p.y < polyPoints[i].y)) && 
            (p.x < (polyPoints[j].x - polyPoints[i].x) * (p.y - polyPoints[i].y) / (polyPoints[j].y - polyPoints[i].y) + polyPoints[i].x)) 
            inside = !inside; 
    } 
    return inside;
}

And here's the testing output for a number of 'cloned' squares being translated around the original square (original shown in black in the diagram) - Notice all the squares with the 0,0 fail. Why is this? I don't really know what the algorithm is doing but have tried a few with exactly the same result..

Vector origin (0.0, 0.0) to Vector destination (1.0, 0.0)
distance: (1.0, 0.0)
New Shape 1 0
New Shape 2 0
New Shape 2 1
New Shape 1 1
PASS

Vector origin (0.0, 0.0) to Vector destination (1.0, 1.0)
distance: (1.0, 1.0)
New Shape 1 1
New Shape 2 1
New Shape 2 2
New Shape 1 2
PASS

Vector origin (0.0, 0.0) to Vector destination (0.0, 1.0)
distance: (0.0, 1.0)
New Shape 0 1
New Shape 1 1
New Shape 1 2
New Shape 0 2
PASS

Vector origin (1.0, 0.0) to Vector destination (0.0, 0.0)
distance: (-1.0, 0.0)
New Shape -1 0
New Shape 0 0
New Shape 0 1
New Shape -1 1
FAIL

Vector origin (1.0, 0.0) to Vector destination (1.0, 1.0)
distance: (0.0, 1.0)
New Shape 0 1
New Shape 1 1
New Shape 1 2
New Shape 0 2
PASS


Vector origin (1.0, 0.0) to Vector destination (0.0, 1.0)
distance: (-1.0, 1.0)
New Shape -1 1
New Shape 0 1
New Shape 0 2
New Shape -1 2
PASS


Vector origin (1.0, 1.0) to Vector destination (0.0, 0.0)
distance: (-1.0, -1.0)
New Shape -1 -1
New Shape 0 -1
New Shape 0 0
New Shape -1 0
FAIL

Vector origin (1.0, 1.0) to Vector destination (1.0, 0.0)
distance: (0.0, -1.0)
New Shape 0 -1
New Shape 1 -1
New Shape 1 0
New Shape 0 0
FAIL


Vector origin (1.0, 1.0) to Vector destination (0.0, 1.0)
distance: (-1.0, 0.0)
New Shape -1 0
New Shape 0 0
New Shape 0 1
New Shape -1 1
FAIL

Vector origin (0.0, 1.0) to Vector destination (0.0, 0.0)
distance: (0.0, -1.0)
New Shape 0 -1
New Shape 1 -1
New Shape 1 0
New Shape 0 0
FAIL

Vector origin (0.0, 1.0) to Vector destination (1.0, 0.0)
distance: (1.0, -1.0)
New Shape 1 -1
New Shape 2 -1
New Shape 2 0
New Shape 1 0
PASS


Vector origin (0.0, 1.0) to Vector destination (1.0, 1.0)
distance: (1.0, 0.0)
New Shape 1 0
New Shape 2 0
New Shape 2 1
New Shape 1 1
PASS
\$\endgroup\$
  • \$\begingroup\$ Could you provide a link to the explanation of the algorithm? \$\endgroup\$ – Leo Sep 21 '16 at 12:24
  • \$\begingroup\$ Sure, added in the question. \$\endgroup\$ – dolyth Sep 21 '16 at 12:46
1
\$\begingroup\$

Is Your Test Point (0, 0) In All These Cases?
Do You Want To Include Boundary Points Inside The Polygon?

If so, then you would get FAIL for all the pink rectangles but PASS for the black one.

Anyway you can check if a point is on the perimeter/boundary of the polygon using this code

private bool IsPointOnPolygon(Vector2[] polyPoints, Vector2 p)
{
    int j = polyPoints.Length - 1;
    bool onPoly = false;

    for (int i = 0; i < polyPoints.Length - 1; i++)
    {
        if ((polyPoints[i].y <= p.y && p.y <= polyPoints[j].y) || (polyPoints[j].y <= p.y && p.y <= polyPoints[i].y))
        {
            if (polyPoints[i].y == polyPoints[j].y)
            {
                if ((polyPoints[i].x <= p.x && p.x <= polyPoints[j].x) || (polyPoints[j].x <= p.x && p.x <= polyPoints[i].x))
                {
                    onPoly = true;
                    break;
                }
            }
            else
            {
                float edgeX = ((polyPoints[j].x - polyPoints[i].x) * (p.y - polyPoints[i].y) / (polyPoints[j].y - polyPoints[i].y) + polyPoints[i].x);
                if (p.x == edgeX)
                {
                    onPoly = true;
                    break;
                }
            }
        }
    }

    return onPoly;
}

Since there is a limit on floating number precision, it can give wrong results for near cases. But you can overcome that issue by using error limit check on edge cases like this

float errLimit = 0.000001f;
if (Math.Abs(p.x - edgeX) < errLimit)
{
    onPoly = true;
    break;
}

Hope I answered your question

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer. What I'm looking for is only return false if a point is within the black square. If it's on the line (i.e. on any of the for corners or edges), then that's ok. So I ask the code... IsPointInPolygon.. and it returns true if is and false if not - and 'not' also including cases where the point is on the line or vertices. I think you've given me the answer, need to test it out. \$\endgroup\$ – dolyth Sep 24 '16 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.