# Point in Polygon, Ray Method: ending infinite line

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 what I want 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;

• 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. – Andon M. Coleman Jun 6 '14 at 1:31
• 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. – Andon M. Coleman Jun 6 '14 at 1:36

## 1 Answer

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.