如何检测两个线段相交的位置？

Question

如何检测两个线段相交的位置？

如何确定两条线是否相交，如果它们相交，在x，y点处是什么？

Answer 1

对于使用矢量交叉产品的这个问题，有一个很好的方法。将二维向量叉积v&nbsp;&nbsp;×&nbsp;&nbsp;w定义为v&nbsp;x&nbsp;&nbsp;w&nbsp;y&nbsp;&nbsp;-&nbsp;&nbsp;v&nbsp;y&nbsp;w&nbsp;x。假设两个线段从p到p&nbsp;&nbsp;+&nbsp;&nbsp;r和从q到q&nbsp;&nbsp;+&nbsp;&nbsp;s。然后第一行上的任何点都可表示为p&nbsp;&nbsp;+&nbsp;&nbsp;t&nbsp;&nbsp;r（对于标量参数&nbsp;&nbsp;t）和第二行上的任何点可表示为q&nbsp;&nbsp;+&nbsp;&nbsp;u&nbsp;&nbsp;s（对于标量参数&nbsp;&nbsp;u）。如果我们能找到t和u，则两条线相交：p&nbsp;+&nbsp;t&nbsp;&nbsp;r&nbsp;=&nbsp;q&nbsp;+&nbsp;u&nbsp;&nbsp;s跨两侧小号，让（p&nbsp;+&nbsp;t&nbsp;&nbsp;r）×&nbsp;s&nbsp;=（q&nbsp;+&nbsp;u&nbsp;&nbsp;s）×&nbsp;s由于s&nbsp;&nbsp;×&nbsp;&nbsp;s&nbsp;= 0，这意味着t&nbsp;&nbsp;（r&nbsp;×&nbsp;s）=（q&nbsp;-&nbsp;p）×&nbsp;s因此，解决t：t&nbsp;=（q&nbsp;-&nbsp;p）×&nbsp;s&nbsp;/（r&nbsp;×&nbsp;s）以同样的方式，我们可以为你解决：（p&nbsp;+&nbsp;t&nbsp;&nbsp;r）×&nbsp;r&nbsp;=（q&nbsp;+&nbsp;u&nbsp;&nbsp;s）×&nbsp;ru&nbsp;&nbsp;（s&nbsp;×&nbsp;r）=（p&nbsp;-&nbsp;q）×&nbsp;ru&nbsp;=（p&nbsp;-&nbsp;q）×&nbsp;r&nbsp;/（s&nbsp;×&nbsp;r）为了减少计算步骤的数量，可以方便地重写如下（记住s&nbsp;&nbsp;×&nbsp;&nbsp;r&nbsp;= -&nbsp;&nbsp;r&nbsp;&nbsp;×&nbsp;&nbsp;s）：u&nbsp;=（q&nbsp;-&nbsp;p）×&nbsp;r&nbsp;/（r&nbsp;×&nbsp;s）现在有四种情况：如果r&nbsp;&nbsp;×&nbsp;&nbsp;s&nbsp;&nbsp;= 0且（q&nbsp;&nbsp;-&nbsp;&nbsp;p）×&nbsp;&nbsp;r&nbsp;&nbsp;= 0，则两条线共线。在这种情况下，根据第一个线段（p&nbsp;+&nbsp;t&nbsp;r）的等式表示第二个段（q和q&nbsp;&nbsp;+&nbsp;&nbsp;s）的端点：t&nbsp;0&nbsp;=（q&nbsp;-&nbsp;p）·&nbsp;&nbsp;r&nbsp;/（r&nbsp;&nbsp;·&nbsp;&nbsp;r）t&nbsp;1&nbsp;=（q&nbsp;+&nbsp;s&nbsp;-&nbsp;p）·&nbsp;&nbsp;r&nbsp;/（r&nbsp;&nbsp;·&nbsp;&nbsp;r）=&nbsp;t&nbsp;0&nbsp;+&nbsp;s&nbsp;&nbsp;·&nbsp;&nbsp;r&nbsp;/（r&nbsp;&nbsp;·&nbsp;&nbsp;r）如果t&nbsp;0和t&nbsp;1之间的间隔与区间[0,1]相交，则线段共线并重叠;&nbsp;否则它们是共线的和不相交的。注意，如果s和r指向相反的方向，则s&nbsp;&nbsp;·&nbsp;&nbsp;r&nbsp;<0，因此要检查的间隔是[&nbsp;t&nbsp;1，t&nbsp;0&nbsp;]而不是[&nbsp;t&nbsp;0，t&nbsp;1&nbsp;]。如果r&nbsp;&nbsp;×&nbsp;&nbsp;s&nbsp;&nbsp;= 0并且（q&nbsp;&nbsp;-&nbsp;&nbsp;p）×&nbsp;&nbsp;r&nbsp;&nbsp;≠0，则两条线平行且不相交。如果- [R&nbsp;&nbsp;×&nbsp;&nbsp;小号&nbsp;&nbsp;≠0和0≤&nbsp;&nbsp;吨&nbsp;&nbsp;≤1和0≤&nbsp;&nbsp;ü&nbsp;&nbsp;≤1，两条线段在点满足p&nbsp;+&nbsp;吨&nbsp;- [R&nbsp;=&nbsp;q&nbsp;+&nbsp;Ü&nbsp;&nbsp;小号。否则，两个线段不平行但不相交。信用：这种方法是3D线交叉算法的二维专业化，来自Ronald Goldman的文章“三维空间中的两条线的交点”，发表于图形宝石，第304页。在三个维度中，通常的情况是这些线是倾斜的（既不平行也不相交），在这种情况下，该方法给出了两条线最接近的点。

Answer 2

FWIW，以下功能（在C中）都检测线交叉并确定交点。它基于Andre LeMothe的“&nbsp;Windows游戏编程大师的诀窍&nbsp;”中的算法。它与其他答案中的某些算法（例如Gareth's）没有什么不同。LeMothe然后使用Cramer的规则（不要问我）自己解决方程。我可以证明它在我的微弱小行星克隆中起作用，并且似乎正确处理Elemental，Dan和Wodzu在其他答案中描述的边缘情况。它也可能比KingNestor发布的代码更快，因为它是所有的乘法和除法，没有平方根！我想在那里有一些除以零的可能性，尽管在我的情况下这不是一个问题。很容易修改，以避免崩溃。//&nbsp;Returns&nbsp;1&nbsp;if&nbsp;the&nbsp;lines&nbsp;intersect,&nbsp;otherwise&nbsp;0.&nbsp;In&nbsp;addition,&nbsp;if&nbsp;the&nbsp;lines&nbsp; //&nbsp;intersect&nbsp;the&nbsp;intersection&nbsp;point&nbsp;may&nbsp;be&nbsp;stored&nbsp;in&nbsp;the&nbsp;floats&nbsp;i_x&nbsp;and&nbsp;i_y.char &nbsp;get_line_intersection(float&nbsp;p0_x,&nbsp;float&nbsp;p0_y,&nbsp;float&nbsp;p1_x,&nbsp;float&nbsp;p1_y,&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;float&nbsp;p2_x,&nbsp;float&nbsp;p2_y,&nbsp;float&nbsp;p3_x,&nbsp;float&nbsp;p3_y,&nbsp;float&nbsp;*i_x,&nbsp;float&nbsp;*i_y){ &nbsp;&nbsp;&nbsp;&nbsp;float&nbsp;s1_x,&nbsp;s1_y,&nbsp;s2_x,&nbsp;s2_y; &nbsp;&nbsp;&nbsp;&nbsp;s1_x&nbsp;=&nbsp;p1_x&nbsp;-&nbsp;p0_x;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s1_y&nbsp;=&nbsp;p1_y&nbsp;-&nbsp;p0_y; &nbsp;&nbsp;&nbsp;&nbsp;s2_x&nbsp;=&nbsp;p3_x&nbsp;-&nbsp;p2_x;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s2_y&nbsp;=&nbsp;p3_y&nbsp;-&nbsp;p2_y; &nbsp;&nbsp;&nbsp;&nbsp;float&nbsp;s,&nbsp;t; &nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;=&nbsp;(-s1_y&nbsp;*&nbsp;(p0_x&nbsp;-&nbsp;p2_x)&nbsp;+&nbsp;s1_x&nbsp;*&nbsp;(p0_y&nbsp;-&nbsp;p2_y))&nbsp;/&nbsp;(-s2_x&nbsp;*&nbsp;s1_y&nbsp;+&nbsp;s1_x&nbsp;*&nbsp;s2_y); &nbsp;&nbsp;&nbsp;&nbsp;t&nbsp;=&nbsp;(&nbsp;s2_x&nbsp;*&nbsp;(p0_y&nbsp;-&nbsp;p2_y)&nbsp;-&nbsp;s2_y&nbsp;*&nbsp;(p0_x&nbsp;-&nbsp;p2_x))&nbsp;/&nbsp;(-s2_x&nbsp;*&nbsp;s1_y&nbsp;+&nbsp;s1_x&nbsp;*&nbsp;s2_y); &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(s&nbsp;>=&nbsp;0&nbsp;&&&nbsp;s&nbsp;<=&nbsp;1&nbsp;&&&nbsp;t&nbsp;>=&nbsp;0&nbsp;&&&nbsp;t&nbsp;<=&nbsp;1) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Collision&nbsp;detected &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(i_x&nbsp;!=&nbsp;NULL) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*i_x&nbsp;=&nbsp;p0_x&nbsp;+&nbsp;(t&nbsp;*&nbsp;s1_x); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(i_y&nbsp;!=&nbsp;NULL) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*i_y&nbsp;=&nbsp;p0_y&nbsp;+&nbsp;(t&nbsp;*&nbsp;s1_y); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;&nbsp;//&nbsp;No&nbsp;collision}顺便说一句，我必须说，在LeMothe的书中，虽然他显然得到了正确的算法，但是他展示的具体例子插错了数字并且计算错误。例如：（4 *（4 - 1）+ 12 *（7 - 1））/（17 * 4 + 12 * 10）= 844 / 0.88= 0.44那让我困惑了几个小时。:(