Line intersection

Question

How to find whether a line intercepted in a polygon

Please clarify the question a little bit. Do you mean a 2D line intersecting a 2D polygon? A 3D line passing through the plane of a 2D polygon and the intersection point of the line and the plane is also inside the polygon? Is it any general polygon or can we assume it is convex? — A. Levy, May 07 '09 at 05:20
Is there a programming language you are doing this in? Many have built in libraries for this. — Ethan Heilman, May 07 '09 at 05:42

score 3 · Answer 1 · answered May 08 '09 at 04:48

The question is a little bit ambiguous but let's try anyway:

Assume the points (x,y) on the line are defined by the equation Ax + By + C = 0. Then we can obviously determine if a point (x,y) is on the line by evaluating Ax + By + C. If the point is not on the line then the sign of Ax + By + C tells us on which side of the line the point is. Hence by inspecting the signs of the expression Ax + By + C for each vertex (x,y) of the polygon, we can determine if all points of the polygon are on the same side of line or not.

(A slightly different problem would be to determine if a polygon intersects a line segment.)

score 3 · Answer 2 · answered May 21 '09 at 11:12

You can read a reasonable answer from this implementation found in some webpage

Point  * intersection2(Point * _line1, Point * _line2) {

Point  p1,p2,p3,p4;
p1=_line1[0]; p3=_line2[0];
p2=_line1[1]; p4=_line2[1];

// Store the values for fast access and easy
// equations-to-code conversion
double x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
double y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;

double A1 = y2-y1;
double B1 = x1-x2;
double C1 = (A1*x1)+(B1*y1);

double A2 = y4-y3;
double B2 = x3-x4;
double C2 = A2*x3+B2*y3;

double det = A1*B2 - A2*B1;

if (det==0){
    return NULL;
}else{
    // Return the point of intersection
    Point  * ret = new CvPoint2D64f ();
    ret->x = (B2*C1 - B1*C2)/det;
    ret->y = (A1*C2 - A2*C1)/det;
    return ret;

}

}

Reference. C++ Example: Geometry Concepts Line Intersection and its Applications, 2D drawing By lbackstrom from site ucancode

score 0 · Answer 3 · answered May 07 '09 at 05:17

0

You need the points of the polygon on a coordinate graph and the slope and x and y intercept of the line to find that information. From there it's simple math.

answered May 07 '09 at 05:17

Bjorn

69,215
39
136
164

score 0 · Answer 4 · answered May 08 '09 at 05:15

Depending on what exactly you want (I'll assume a line segment as I just wrote that code this week) you can get it in two parts:

first of all I'd suggest encoding lines as

a*X + b*Y - c = 0

because that form has no corner cases for lines like X=5, Y=4 or X=3*Y.

Test if the line intersects any side of the polygon
- Test if the ends of both lines are on opposite sides of the other line. The suggested form makes this easy by just checking the polarity of the LHS
Test if a point on the line is inside the polygon
- Test if a line from some point on your input line to the outside of the polygon corsses the polygon at an odd number of points. Be warned that you will need to check for the same point showing up from several places and because of FP errors this can't be done with an exact match test.

Line intersection

4 Answers4

Linked