# Points inside a Polygon, failing for shapes with 0,0

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. 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

• Could you provide a link to the explanation of the algorithm?
– Leo
Sep 21, 2016 at 12:24
• Sure, added in the question. Sep 21, 2016 at 12:46

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;
}