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

Question

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
– Leo, Commented Sep 21, 2016 at 12:24

Maxkiel · Accepted Answer · 2016-09-23 15:47:36Z

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

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. — dolyth
– dolyth, Commented Sep 24, 2016 at 9:57

Stack Exchange Network

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

1 Answer 1

You must log in to answer this question.

Hot Network Questions

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

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions