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)之间的向量A1A2

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

这些公式基本上类似于如何检测两条线段相交的位置？除了从那里编码对于新手或匆忙的人来说不一定是微不足道的（就像我自己很多次一样）。