5
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ 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). \$\endgroup\$ Jul 6, 2012 at 17:20
  • \$\begingroup\$ @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. \$\endgroup\$ Jul 6, 2012 at 17:30
  • \$\begingroup\$ 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? \$\endgroup\$ Jul 6, 2012 at 17:39
  • \$\begingroup\$ @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. :) \$\endgroup\$ Jul 6, 2012 at 17:49
  • \$\begingroup\$ @StevenStadnicki Just for reference, this is what I was talking about on my previous comment. :) \$\endgroup\$ Jul 6, 2012 at 19:39

3 Answers 3

4
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 6, 2012 at 17:42
  • \$\begingroup\$ @DavidGouveia you’re right! I did mean ellipse :-) Spelling fixed. \$\endgroup\$ Jul 6, 2012 at 18:28
  • \$\begingroup\$ 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 :) \$\endgroup\$ Jul 6, 2012 at 18:33
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 6, 2012 at 10:17
1
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ added pastebin link since i dont know how to properly add code \$\endgroup\$
    – matt
    Jul 6, 2012 at 16:39
  • \$\begingroup\$ Sorry, I did not specify in the question, but it is important that the algorithm works with concave polygons too. \$\endgroup\$ Jul 6, 2012 at 17:29
  • \$\begingroup\$ 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 \$\endgroup\$
    – matt
    Jul 6, 2012 at 17:39
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 6, 2012 at 17:55
  • \$\begingroup\$ @matt the code referred to by David is precisely doing a crossing test. \$\endgroup\$ Jul 6, 2012 at 18:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .