判断两条线段是否相交以及求相交的交点坐标
最近在看recast&detour源码的时候有遇到许多数学上的算法问题，特此记录，以便以后查看。
方法一：
求线段AB 和 线段CD 有没有交点以及交点坐标。
1）先对AB和CD线段的aabb包围盒进行相交性检测，看是否 肯定不相交。
2）再用二维叉积进行进一步判断相交可能性。令：
\[\begin{gathered}a1 = cross2d(\overrightarrow {AB} ,\overrightarrow {AD} ) \hfill \\
a2 = cross2d(\overrightarrow {AB} ,\overrightarrow {AC} ) \hfill \\
a3 = cross2d(\overrightarrow {CD} ,\overrightarrow {CA} ) \hfill \\
a4 = cross2d(\overrightarrow {CD} ,\overrightarrow {CB} ) \hfill \\
\end{gathered} \]
如果 a1 * a2 > 0 （说明 C 和 D点 在线段AB的同一侧）：
如果 a3 * a4 = 0 ： 判断相交且交点是A或B，否则不相交。
如果 a1 * a2 < 0（说明 C 和 D点 在线段AB的异侧） ：
如果 a3 * a4 <=0： 判断相交（=0时交点是A或B），否则不相交。
如果 a1 * a2 = 0（说明 C 或 D点 在线段AB上）：
如果 a3 * a4 = 0 , 所有两线段有重合定义为不相交，否则就是相交。
ps：a4 也等于 a3 + a2 - a1。可以通过面积或者叉积的分配规律证明
方法二
求解相交点的坐标，列方程求解，此方法同时计算除了交点坐标。
http://dec3.jlu.edu.cn/webcourse/t000096/graphics/chapter5/01_1.html
问题：求线段A(x1,y1)B(x2,y2) 和 线段C(x3,y3)D(x4,y4)之间的交点。
使用参数方程表示线段AB 和 CD所在的直线方程：
\[\left\{ {\begin{array}{*{20}{c}}
{x = {x_1} + \lambda ({x_2} - {x_1})} \\
{y = {y_1} + \lambda ({y_2} - {y_1})}
\end{array}} \right.\left\{ {\begin{array}{*{20}{c}}
{x = {x_3} + \mu ({x_4} - {x_3})} \\
{y = {y_3} + \mu ({y_4} - {y_3})}
\end{array}} \right.\]
如果两个线段之间有交点，即联立方程求参数lamda 和 mu
\[\begin{array}{*{20}{c}}
{({x_2} - {x_1})\lambda - ({x_4} - {x_3})\mu = {x_3} - {x_1}} \\
{({y_2} - {y_1})\lambda - ({y_4} - {y_3})\mu = {y_3} - {y_1}}
\end{array}\]
列成行列式，用解向量法求解方程：
\[\left( {\begin{array}{*{20}{c}}
{{x_2} - {x_1}}&{ - ({x_4} - {x_3})} \\
{{y_2} - {y_1}}&{ - ({y_4} - {y_3})}
\end{array}} \right)\left( {\begin{array}{*{20}{c}}
\lambda \\
\mu
\end{array}} \right) = \left( {\begin{array}{*{20}{c}}
{{x_3} - {x_1}} \\
{{y_3} - {y_1}}
\end{array}} \right)\]
令向量：
u = (x2-x1, y2-y1) = AB向量
v = (x4-x3, y4-y3) = CD向量
w = (x3-x1, y3-y1) = AC向量
\[\det = \left| {\begin{array}{*{20}{c}}
{{x_2} - {x_1}}&{ - ({x_4} - {x_3})} \\
{{y_2} - {y_1}}&{ - ({y_4} - {y_3})}
\end{array}} \right| = - ({u_x}{v_y} - {v_x}{u_y}) = - cross(u,v)\]
最终求得参数 lamda 和 mu，把lamda mu带入参数方程即得交点
\[\left\{ {\begin{array}{*{20}{c}}
{\lambda = \left| {\begin{array}{*{20}{c}}
{{x_3} - {x_1}}&{ - ({x_4} - {x_3})} \\
{{y_3} - {y_1}}&{ - ({y_4} - {y_3})}
\end{array}} \right|/\det = - cross(w,v)/\det = cross(v,w)/\det } \\
{\mu = \left| {\begin{array}{*{20}{c}}
{{x_2} - {x_1}}&{{x_3} - {x_1}} \\
{{y_2} - {y_1}}&{{y_3} - {y_1}}
\end{array}} \right|/\det = cross(u,w)/\det }
\end{array}} \right.\]
继续分析：
因为 lamda的值 =（交点到起点A）/AB，
而 lamda的值 = cross(v,w)/cross(v,u) = (CD叉积AC)/(CD叉积AB) = (CA叉积CD)/(CD叉积AB) 。
所以
1 > lamda > 0 说明 交点在 AB 上；
lamda = 0 交点在A点；
lamda =1 交点在B点；
lamda >1 交点在AB延长线上；
lamda <0 交点在BA延长线上。
同理 mu 的值也能反应交点在CD线段上的各种情况。
所以可以通过 lamda 和 mu 的值，判断出交点的情况。只有两者都在（0,1)之间 也是真正的相交于线段之内。
源码
方法一判断是否相交
源码中调用 overlapSegSeg2d 函数之前已经排除了在端点在线段以及延长线上的可能，所以可以简单通过是否小于0判断是否相交。
static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d)
{
const float a1 = vcross2(a, b, d);
const float a2 = vcross2(a, b, c);
if (a1*a2 < 0.0f)
{
float a3 = vcross2(c, d, a);
float a4 = a3 + a2 - a1;
if (a3 * a4 < 0.0f)
return 1;
}
return 0;
}方法二计算交点坐标
ap 和 aq 即为AB点， bq和bq即为CD点，s和t即为lamda和mu
bool dtIntersectSegSeg2D(const float* ap, const float* aq,
const float* bp, const float* bq,
float& s, float& t)
{
float u[3], v[3], w[3];
dtVsub(u,aq,ap);
dtVsub(v,bq,bp);
dtVsub(w,ap,bp);
float d = vperpXZ(u,v);
if (fabsf(d) < 1e-6f) return false;
s = vperpXZ(v,w) / d;
t = vperpXZ(u,w) / d;
return true;
}进一步应用线段之间相交的交点所在位置
来判断线段与多边形之间的相交情况
// 应该是针对凸多边形
bool dtIntersectSegmentPoly2D(const float* p0, const float* p1,
const float* verts, int nverts,
float& tmin, float& tmax,
int& segMin, int& segMax)
{
static const float EPS = 0.00000001f;
tmin = 0;
tmax = 1;
segMin = -1;
segMax = -1;
float dir[3];
dtVsub(dir, p1, p0);
for (int i = 0, j = nverts-1; i < nverts; j=i++)
{
float edge[3], diff[3];
dtVsub(edge, &verts[i*3], &verts[j*3]);
dtVsub(diff, p0, &verts[j*3]);
// 面积
// n > 0 说明 p0 在 edgej->i 的 右边
const float n = dtVperp2D(edge, diff);
// d 约等于 0 ，说明 s 和 edge平行
const float d = dtVperp2D(dir, edge);
if (fabsf(d) < EPS)
{
// S is nearly parallel to this edge
// n < 0 说明 p0 在 edgej->i 的 左边 , 那么肯定不相交了
if (n < 0)
return false;
else
continue;
}
// 面积之比 即 高之比
// t 表示的是 （s与edge的交点 到 s的起点）的线段长度/ s的长度
const float t = n / d;
// n > 0 说明 i 在 dir 的 左边
if (d < 0)
{
// segment S is entering across this edge
// 更新的是 tmin 应该取最大值，因为是靠近，所以交点肯定是越远离起点越好 越远离起点 t值越大
// 最大的tmin 应该是 edge 与 s的交点在edge上 而非是edge的延长线上。
if (t > tmin)
{
tmin = t;
segMin = j;
// S enters after leaving polygon
if (tmin > tmax)
return false;
}
}
else
{
// segment S is leaving across this edge
// 更新的是 tmin 应该取最小值 因为是远离，所以交点肯定是越靠近起点越好 越靠近起点 t值越小
// 最小的tmax 应该是 edge 与 s的交点在edge上 而非是edge的延长线上。
// 如果 t 一直是 大于1 说明 终点在多边形之内 那么 segMax = -1 tmax = 1
// 如果 segMax 不等于 -1 ,那么 tmax 肯定是小于1
if (t < tmax)
{
tmax = t;
segMax = j;
// S leaves before entering polygon
if (tmax < tmin)
return false;
}
}
}
return true;
}参考
https://www.cnblogs.com/Duahanlang/archive/2013/05/11/3073434.html
https://blog.csdn.net/rickliuxiao/article/details/6259322