Line intersection

问题:

How to find whether a line intercepted in a polygon

回答1:

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

回答2:

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

回答3:

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.

回答4:

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.