Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've been using this method which was taken from Game Coding Complete to detect whether a point is inside of a polygon. It works in almost every case, but is failing on a few edge cases, and I can't figure out the reason.

For example, given a polygon with vertices at (0,0) (0,100) and (100,100), the algorithm is returning:

  • True for any point strictly inside the polygon
  • False for any of the vertices
  • False for (0, 50) which lies on one of the edges of the polygon
  • True (?) for (50,50) which is also on one of the edges of the polygon

I'd actually like to relax the algorithm so that it returns true in all of these cases. In other words, it should return true for points that are strictly inside, for the vertices themselves, and for points on the edges of the polygon.

If possible I'd also like to give it enough tolerance so that it always tend towards "true" in face of floating point fluctuations. For example, I have another method, that given a line segment and a point, returns the closest location on the line segment to the given point.

Currently, given any point outside the polygon and one of its edges, there are cases where the result is categorized as being inside by the method above, while other points are considered outside. I'd like to give it enough tolerance so that it always returns true in this situation.

The way I've currently solved the problem is an hack, which consists of using an external library to inflate the polygon by a few pixels, and performing the tests on the inflated polygon, but I'd really like to replace this with a proper solution.

share|improve this question
    
One small caveat I'll offer: are you sure you want to have tolerance in this test? In particular, if you have a single polygon you're testing then the tolerance approach makes sense, but if you're doing point-in-polygon tests against several polys in a mesh then it can be even trickier to make sure that the points along the edge don't show up as being in multiple polygons (or to come up with a consistent scheme for handling them if they do). –  Steven Stadnicki Jul 6 '12 at 17:20
    
@StevenStadnicki That's a good point, but I think I really need it for my case. I'm using a single polygon to represent the walkable area of a room on a 2D graphic adventure game. If I manually place the character outside of the polygon and he tries to walk, I prevent him from moving (on purpose). But when walking inside the polygon, the pathfinder often leads the character to the very edges or vertices of the polygon. In that situation, I absolutely need the character to know that he is still inside the polygon, so that he does not get stuck. –  David Gouveia Jul 6 '12 at 17:30
    
In that case, I think I would actually change the polygon rather than the point-in-poly test - expand it by a pixel or so in each direction. Or does that run into animation issues with the character clipping the edge of the room? –  Steven Stadnicki Jul 6 '12 at 17:39
    
@StevenStadnicki That's what I'm doing at the moment actually, but inflating the polygon correctly is not trivial and I ended up having to rely on an external library to do it. The process also introduces new vertices into the polygon to correctly deal with some sharp turns in the polygon, and I have to recompute it every time the underlying polygon changes (in the level editor), which is not ideal. I'd rather just make my collision tests more forgiving. :) –  David Gouveia Jul 6 '12 at 17:49
    
@StevenStadnicki Just for reference, this is what I was talking about on my previous comment. :) –  David Gouveia Jul 6 '12 at 19:39

3 Answers 3

up vote 1 down vote accepted

Since the algorithm already parses all edges of the polygon to see how many times a ray cast from test crosses them, I think it's reasonable to add a check to see whether test lies on the edge exactly (or within an epsilon).

In order to avoid too much additional complexity (the usual point - segment distance computation is really awful), I suggest approximating the edge to an extremely thin ellipse and see whether test is on that ellipse. This is the resulting code (only the inner loop shown):

oldPoint = polygon[points-1];
float oldSqDist = sqlength(oldPoint - test);

for (unsigned int i=0 ; i < points; i++)
{
    newPoint = polygon[i];
    float newSqDist = sqlength(newPoint - test);

    if (oldSqDist + newSqDist + 2.0f * std::sqrt(oldSqDist * newSqDist) - sqlength(newPoint - oldPoint) < EPSILON)
        return true;

    if (newPoint.x > oldPoint.x)
    {
        left = oldPoint;
        right = newPoint;
    }
    else
    {
        left = newPoint;
        right = oldPoint;
    }

    if ((newPoint.x < test.x) == (test.x <= oldPoint.x)
       && (test.y-left.y) * (right.x-left.x)
        < (right.y-left.y) * (test.x-left.x) )
    {
        inside=!inside;
    }

    oldPoint = newPoint;
    oldSqDist = newSqDist;
}

Where sqlength() is your favourite way of doing x * x + y * y. I tested the code with EPSILON = 1e-10f and got good results. In real life you should have EPSILON vary relatively to the size of your polygon.

share|improve this answer
    
I had considered this possibility before, but was holding back on implementing it before knowing if there was an easier way to add the epsilon to the algorithm. However, I was going to use the usual point-segment distance which I already have implemented somewhere else. But your suggestion to approximate the edge as an ellipse (I might be wrong but I think ellipsis refers to the ... mark :P) is just brilliant! Also, thanks for providing the implementation, it's working great, and it would have taken me a while to figure it out otherwise from the description. –  David Gouveia Jul 6 '12 at 17:42
    
@DavidGouveia you’re right! I did mean ellipse :-) Spelling fixed. –  Sam Hocevar Jul 6 '12 at 18:28
    
I've just posted a follow up question to this, and would be really grateful if you could give some input. As part of the problem, I think I'll need to add an epsilon to a line-segment intersection test, and was thinking that maybe the ellipse trick would work there too :) –  David Gouveia Jul 6 '12 at 18:33

A common approach to this sort of thing is to add epsilons to the floating-point comparisons. I'm not completely sure how to do this in the code you linked, since it seems that it's flipping the inside/outside bit as a result of some comparisons - so perhaps you'd need the epsilon to be positive when currently inside, and negative when outside, or vice versa. The idea would be to make the compares forgiving in the direction that tends to make the result 'inside'.

share|improve this answer
    
Indeed, I am aware of how to do epsilon comparisons. But for this algorithm I really have no idea what I'm doing. I've already tried adding epsilons on every place that seemed to make sense. And other things such as tweaking < to <=. But every time I managed to correct one case, another would become broken. –  David Gouveia Jul 6 '12 at 10:17

May I suggest another approach? As described in Real Time Collision Detection, to test if a point is inside a convex polygon oriented counter-clockwise, one fast way is to subdivide in half the polygon and check if the triangle formed by v0 (the first vertex of the poly), vk (k = n/2, with n the number of vertices) and p is oriented CCW. If so we can check again, incrementing k and see if the triangle is again CCW or not. If not the point lies inside the polygon, if not we must check again. The test is implemented as follow (just copying from the text):

int PointInConvexPolygon(Point p, int n, Point v[])
{
    int low = 0, high = n;
    do 
    {
        int mid = (low + high)/2;
        if (TriangleIsCCW(v[0], v[mid], p)) low = mid;
        else high = mid;
    } 
    while (low + 1 < high);
    if (low == 0 || high == n) return 0;
    return TriangleIsCCW(v[low], v[high], p);
}

http://pastebin.com/QkHi1Hrg

Here TriangleIsCCW checks if p lies on the left or on the right the segment formed by v[low] and v[high], and can be implemented as a method that checks if the determinant |ax ay 1| |bx by 1| |cx cy 1| with A (ax, ay), B (bx, by), C (cx, cy) the points checked. If the determinant is positive, the points are oriented CCW, if is 0 they are collinear. This can be used for particular cases as the points lying on the edge or on the vertex.

share|improve this answer
    
added pastebin link since i dont know how to properly add code –  matt Jul 6 '12 at 16:39
    
Sorry, I did not specify in the question, but it is important that the algorithm works with concave polygons too. –  David Gouveia Jul 6 '12 at 17:29
    
oh, in this case you could perform a crossing test, to check whether a ray starting from a point crosses the polygon an odd number of times. However, the code above can be useful when working on convex hulls for example –  matt Jul 6 '12 at 17:39
    
Thanks for the suggestions! :) But the problem wasn't only being able to detect if a point was on the edge of the polygon (which I've now treated as a special case thanks to Sam's suggestion) but also to give it a little margin of failure, which his suggestion also handles very well. I think using the crossing test would be the same, since I would still need to add those special cases. –  David Gouveia Jul 6 '12 at 17:55
    
@matt the code referred to by David is precisely doing a crossing test. –  Sam Hocevar Jul 6 '12 at 18:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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