c++ - C++ 中直线与线段的交点

Question

以下是从CP3 中提取的C++ 代码，它计算通过 a 和 b 的线与由 p 和 q 定义的线 段 之间的交点，假设交点存在。有人能解释一下它在做什么以及它为什么起作用(几何上)吗？

// line segment p-q intersect with line A-B.
point lineIntersectSeg(point p, point q, point A, point B) {
  double a = B.y - A.y;
  double b = A.x - B.x;
  double c = B.x * A.y - A.x * B.y;
  double u = fabs(a * p.x + b * p.y + c);
  double v = fabs(a * q.x + b * q.y + c);
  return point((p.x * v + q.x * u) / (u+v), (p.y * v + q.y * u) / (u+v));
}

请注意，此解决方案似乎与解释的解决方案不同 here或在 Wikipedia page因为这个解决方案使用了绝对值函数。

我扩展了交点 (x, y) 的表达式:

Answer 1

一个好的起点是了解如何自己找到线交点:https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

• 线段:y = ax + c
• 直线:y = bx + d
• 十字路口 和

现在我们只需要根据 p 和 q 和 a 和 c em>b 和 d 在 A 和 B 方面。

我们知道我们的两个斜坡:

• a = (p.y - q.y)/(p.x - q.x)
• b = (A.y - B.y)/(A.x - B.x)

我倾向于使用 Point-Slope Form找到 y 截距:

• y -p.y= a(x -p.x) 这将简化为 y = ax - (p.x * q.y - p.y * q.x)/(p.x - q.x)
• y -A.y= a(x -B.x) 这将简化为 y = ax - (A.x * B.y - A.y * B.x)/(A.x - B.x)

因此，如果您允许我将我们的变量混合到数学符号中以便简化更简单，我们交集组件的最终方程是:

• 
• 

一旦分子和分母中的分数合并为一个分数，两者的分母就可以看到(A.x - B.x)(p.x - q.x) 所以两个分母都可以被删除屈服:

• 
•