快速求线段相交点的方法

线段的相交的检测工作中用的较多，简单的求根方法是方便但是需要做很多的相交判断，最近遇到了一个巧妙的方法所以Mark下来（来源 知乎Never的回答）。

思路整理

• 直线参数方程

$$\begin{gathered} x(t_1)=x_1+t_1(x_2-x_1) \\ y(t_1)=y_1+t_1(y_2-y_1) \\ x(t_2)=x_3+t_2(x_4-x_3) \\ y(t_2)=y_3+t_2(y_4-y_3) \end{gathered}$$

• 求交点，得出矩阵方程

$$\left[\begin{array}{cc}{x}_2-x_1& x_3-x_4\\ y_2-y_1& y_3-y_4\end{array}\right]\left[\begin{array}{c}{t}_1\\ t_2\end{array}\right]=\left[\begin{array}{c}{x}_3-x_1\\ y_3-y_1\end{array}\right]$$
若矩阵可逆有交点，相反则无。

• 判断是否在范围内
  根据参数方程，只需判断 $t_1,t_2\in [0,1]$。

例程

#include "pch.h"
#include <iostream>
int main()
{
std::cout << "x1, y1?" << std::endl;
double x1, y1;
std::cin >> x1 >> y1;
std::cout << "x2, y2?" << std::endl;
double x2, y2;
std::cin >> x2 >> y2;
std::cout << "x3, y3?" << std::endl;
double x3, y3;
std::cin >> x3 >> y3;
std::cout << "x4, y4?" << std::endl;
double x4, y4;
std::cin >> x4 >> y4;
double a = x2 - x1,
b = x3 - x4,
c = y2 - y1,
d = y3 - y4,
g = x3 - x1,
h = y3 - y1;
double f = a * d - b * c;
if (fabs(f) < 1.0e-6)
{
std::cerr << "Inverse matrix cannot be computed." << std::endl;
return 1;
}
double t1 = (d * g - b * h) / f;
double t2 = (-c * g + a * h) / f;
if ((t1 < 0) || (t1 > 1) ||
(t2 < 0) || (t2 > 1))
{
std::cerr << "Two lines do not intersect.";
return 1;
}
std::cout << "t1= " << t1 << " t2= " << t2 << std::endl;
std::cout << "Interset point:(" << x1 + t1 * (x2 - x1) << "," << y1 + t1 * (y2 - y1) << ")" << std::endl;
}

最后

以上就是靓丽裙子为你收集整理的快速求线段相交点的方法的全部内容，希望文章能够帮你解决快速求线段相交点的方法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。