c - 如何找到两条线段(不是两条直线)是否相交

Question

我想找到一种方法来检查两条线段是否相交。我正在使用 Xlib 编程来实现这个。

我在网上查过，但我只找到了找到两条线的交点的方法，但没有找到两条线段的交点。

我如何使用 X lib 编程实现它？

Answer 1

为此您不需要 Xlib。设两段为

• A1 = (x1, y1) -> B1 = (x1 + dx1, y1 + dy1) 和
• A2 = (x2, y2) -> B2 = (x2 + dx2, y2 + dy2)。

让

• vp = dx1 * dy2 - dx2 * dy1

如果 vp == 0 线段平行且没有交点。

否则，令v = (vx, vy) 为A1 和A2 之间的 vector

• vx = x2 - x1
• vy = y2 - y1

计算

• k1 = (vx * dy2 - vy * dx2)/vp
• k2 = (vx * dy1 - vy * dx1)/vp

如果 k1 或 k2 落在 [0, 1] 区间之外，则线段不相交(但底层线相交)。否则，路口在

(x1 + k1 * dx1, y1 + k1 * dy1)

顺便说一句，如果你想知道对称性，那将是同一个点

(x2 + k2 * dx2, y2 + k2 * dy2)

这些公式与How do you detect where two line segments intersect?上的答案基本相似除了从那里编码对于新手或匆忙的人来说不一定是微不足道的(就像我自己很多次一样)。