Polygon-Line Collision Detection

Question

I am trying to find a formula to determine if a line intersects a polygon. I have tried, but the code below is not working properly.

bool Check_Collision(float x1,float y1, float x2, float y2)
{
        int j=MyPolyVector.size()-1;
        for (int i=0;i<MyPolyVector.size();i++)
        {
                float x3=MyPolyVector[i].X;
                float x4=MyPolyVector[j].X;
                float y3=MyPolyVector[i].Y;
                float y4=MyPolyVector[j].Y;

                float denom= ((y4-y3)*(x2-x1))-((x4-x3)*(y2-y1));
                float ua = (((x4-x3)*(y1-y3))-((y4-y3)*(x1-x3)))/denom;
                float ub = (((x2-x1)*(y1-y3))-((y2-y1)*(x1-x3)))/denom;
                j=i;

                if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) return true;
        }
        return false;
}

score 2 · Answer 1 · edited May 23 '17 at 11:54

2

I think this link might be interesting for you, to get the know-how: Point in Polygon Problem

There is also a linked resource, for the C-Code: Point in Polygon - C Code

This problem is mostly handled in OpenGL context and the main idea to solve this, is counting the intersections of the polygon and of any straight line, which goes through your point to check.

How much geometry do you have to check, wether a point is inside a polygon?

PS: I just found this post about this issue :-) Stackoverflow - Point in Polygon

edited May 23 '17 at 11:54

Community

1
1

answered Apr 07 '12 at 12:14

loybert

416
1
3
12

Thx for the response but they are different things. – Murat Tutu Apr 07 '12 at 12:21

Semih Ozmen · Answer 2 · 2012-04-07T12:37:49.060

0

I can suggest you to have a look at this book and also search for line line intersection 2D and range checking before your computation.

Also, your code requires division by zero check and further considerations about reciprocal line dimensions and tolerances.

edited Apr 07 '12 at 12:37

answered Apr 07 '12 at 12:28

Semih Ozmen

571
5
20

I m checking the book now. Can you pls explain the division by zero check. – Murat Tutu Apr 07 '12 at 14:16
Since you will use it for division, you should check whether denom is zero or not.. – Semih Ozmen Apr 07 '12 at 17:54

score 0 · Answer 3 · edited Apr 13 '17 at 12:19

It looks like you have incorrect equations for the line intersections. I think that the correct equations are listed here.

That is, a good approach to this problem is to see whether the line intersects any of the line segments on the polygon. So to test this, calculate the point of intersection for the line with each line of the polygon edge, and if ever this point is within the segment of the polygon, then there's an intersection (see whether the point is within the bounds defined by the end points of the segment). (And maybe this is what you're trying to do, but it's a bit hard to tell since you give no explanation.)

Polygon-Line Collision Detection

3 Answers3