c++ - 这个线交叉点是如何工作的？

Question

我正在为类作业构建小行星游戏。要完成它，我需要一个线相交算法/代码。我找到了一个有用的，但我不明白它背后的数学。这是如何工作的？

point* inter( point p1, point p2, point p3, point p4)
{
point* r;

//p1-p2 is the first edge. 
//p3-p4 is the second edge.
r = new point;
float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;

//I do not understand what this d represents.
float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
// If d is zero, there is no intersection
if (d == 0) return NULL;

// I do not understand what this pre and pos means and
// how it's used to get the x and y of the intersection
float pre = (x1*y2 - y1*x2), pos = (x3*y4 - y3*x4);
float x = ( pre * (x3 - x4) - (x1 - x2) * pos ) / d;
float y = ( pre * (y3 - y4) - (y1 - y2) * pos ) / d;

// Check if the x and y coordinates are within both lines
if ( x < min(x1, x2) || x > max(x1, x2) ||
        x < min(x3, x4) || x > max(x3, x4) ) return NULL;
if ( y < min(y1, y2) || y > max(y1, y2) ||
        y < min(y3, y4) || y > max(y3, y4) ) return NULL;

cout << "Inter X : " << x << endl;
cout << "Inter Y : " << y << endl;

// Return the point of intersection
r->x = x;
r->y = y;
return r; 
}

Answer 1

确定二维平面中两条线的交点(如果有的话)(它们可能平行)是一个经典的数学问题。您找到的算法基于求解具有两个线性方程的系统。这是通过计算行列式 (d) 来完成的。如果为零，则直线平行。否则计算交点。

有关公式的详细说明，例如本教程:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2