1
\$\begingroup\$

Having a bit of trouble with point in polygon collision detection using the ray method
i.e. http://en.wikipedia.org/wiki/Point_in_polygon
My problem is I need to give an end to the infinite line created.
As with this infinite line I always get an even number of intersections and hence an invalid result.
i.e. ignore or intersection to the right of the point being checked
what I have
bad
what I want
good


My current code based of Mecki awesome response

for (int side = 0; side < vertices.Length; side++)
        {
            // Test if current side intersects with ray.

            // create infinite line 
            // See: http://en.wikipedia.org/wiki/Linear_equation
            a = end_point.Y - start_point.Y;
            b = start_point.X - end_point.X;
            c = end_point.X * start_point.Y - start_point.X * end_point.Y;

        //insert points of vector
            d2 = a * vertices[side].Position.X + b * vertices[side].Position.Y + c;
            if (side - 1 < 0)
                d1 = a * vertices[vertices.Length - 1].Position.X + b * vertices[vertices.Length - 1].Position.Y + c;
            else
                 d1 = a * vertices[side-1].Position.X + b * vertices[side-1].Position.Y + c;

            // If points have opposite sides, intersections++;
            if (d1 > 0 && d2 < 0 )
                intersections++;
            if (d1 < 0 && d2 > 0 )
                intersections++;

        }
//if intersections odd inside = true
    if ((intersections % 2) == 1)
        inside = true;
    else
        inside = false; 
\$\endgroup\$
  • \$\begingroup\$ It might help if you knew that what you are referring to is called a line segment (assuming it has 2 end points) or a ray (assuming it has 1). When looking for intersection tests, they will often be classified using that terminology; a line is infinite, a ray has a start point but no end and a segment has a start and an end. \$\endgroup\$ – Andon M. Coleman Jun 6 '14 at 1:31
  • 1
    \$\begingroup\$ Also, it is more efficient to perform (intersections & 1) == 1 to test if an integer is odd than (intersections % 2) == 1. Any odd number in binary is going to have the least significant bit set to 1, so you can test that without division. \$\endgroup\$ – Andon M. Coleman Jun 6 '14 at 1:36
1
\$\begingroup\$

You should be thinking about the problem from the point of view of casting a ray from a point to infinity. In your drawings you're casting a ray from infinity to a point.

This is a math problem, so if you're having trouble writing the code I'd be keen to recommend you try to solve the problem on paper first and then transcribe your math into code. This is always the best approach for geometry problems like this.

The idea is to compute the intersection point of both lines, then use barycentric coordinates to see if your intersection point lays within the line segment of your polygon. This last part seems to be what your d1 and d2 variables are doing.

\$\endgroup\$

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.